IMPORT: slz/uslz: defer the output bookkeeping to a checkpoint
Every emitted byte went through _PUT_UPDT(), which incremented five separate
counters by the same length (dec_bsize, dec_total, index, crc_flush and
distance_avail) and tested three limits, plus a fourth test on dec_bsize
before each symbol and a rollover test per loop iteration. For a literal
that is about ten operations and four branches around a single store, and
crc_flush lives in the state structure, so it was a read-modify-write
through memory which could never stay in a register.
Those counters are all the same position expressed in different units,
so we now only maintain the output pointer <out> and compare it against
a precomputed limit <out_lim>, the closest of the three points where
something actually has to be done:
- the end of the ring, where <out> wraps back to <out_base> ;
- the end of the current checksum batch ;
- the point where the decoded block fills the caller's buffer.
When <out> reaches <out_lim> we reach a single "checkpoint" which accounts
for the bytes produced since the previous one, checksums them while they
are still hot in the cache, wraps the ring, reports a full buffer if
needed, recomputes the limit and jumps back to whichever of the three
emitting sites called it. Emitting a literal is now a store and a single
pointer increment, and the counters move at most once every CRC_BLOCK
bytes. The emitting loops have to compare against something to know when
to stop anyway, so the test on <out_lim> is not an added cost.
This comes with multiple benefits:
- distance_avail is no longer needed. It was min(dec_total, out_max)
and was only ever compared against a distance, which never exceeds
32kB while the ring is at least that large, so "have we produced at
least <distance> bytes" is exactly "has the ring wrapped, or is the
distance within the current position". A <wrapped> flag gives the
first half and the match copy already computes the second, so the
check became free.
- crc_flush was removed from the state. Rather than carrying pending
bytes across calls, the return paths now flush the checksum, which
continues to guarantee that on entry the ring position is exactly
dec_total % out_max with nothing pending. That is what makes the
whole thing work, and it also removes by construction the overflow
that this field had to take care of.
- the match copy is now driven by <out_lim>: since the destination
can no longer wrap in the middle of a chunk, the four interleaved
copy phases collapse into two cases, the match starting in the
upper part of the ring or below the current position. A match no
longer has to fit entirely in the remaining space either, it is
emitted in as many chunks as needed, so USLZ_DECODE_E_OUT_BUFFER
is now unreachable.
- the stored block copy becomes a plain loop bounded by the input,
the remaining block length and the limit.
- the rollover check on dec_total moves to the checkpoint, the only
place where the value changes now.
Measured with tests/codepad.sh, decompressing silesia in slz or in
gzip forms now shows:
before after
silesia.tslz 0.8762 s 0.7837 s -10.6 %
silesia.tgz 1.5175 s 1.3875 s -8.6 %
And as a bonus, the code is now smaller (measured on x86_64):
src/uslz.o 14078 -> 12574 (-1504)
tests/uslztest.sh remains at 1764/1764.
This is libslz upstream commit
716793740ca6347a95e3e90c86d2a9c7dc46ec2c