A prototype compression level above 9 that spends more CPU on match selection to
squeeze the output a little further. Branch base is upstream/develop at cb34e282.
Level 10 reuses deflate_slow with a lazy2 flag. When the lazy step is about to
commit the pending match, it looks one position further before deciding. Accepting
that later match costs two literals instead of one, so it has to gain more than the
pending match is worth.
The acceptance rule is cost-aware rather than a plain length comparison:
static inline int lazy_gain(uint32_t new_len, uint32_t cur_len, uint32_t new_dist, uint32_t cur_dist) {
return 4 * (int)(new_len - cur_len) + (int)zng_clz32(new_dist) - (int)zng_clz32(cur_dist);
}A length byte is worth about four bits and a distance costs its magnitude in extra
bits, so a shorter distance can offset a shorter match. That term is where most of
the gain comes from. A plain new_len > cur_len test (threshold 0) only reaches
-0.268% on Silesia against -0.310% for the cost rule at threshold 6.
The probe peeks at the hash chain head instead of inserting, so backing out costs nothing. The insert happens only on the accepted path, which keeps the rolling hash contiguous over the position that gets skipped.
Silesia, deflate level 9 vs level 10, best of 3 runs.
| file | L9 bytes | L10 bytes | ratio | time |
|---|---|---|---|---|
| nci | 2998374 | 2923936 | -2.483% | +20.6% |
| xml | 661887 | 655913 | -0.903% | +19.8% |
| webster | 12114318 | 12035739 | -0.649% | +21.0% |
| samba | 5406334 | 5381811 | -0.454% | +20.7% |
| reymont | 1826403 | 1818186 | -0.450% | +22.1% |
| dickens | 3859108 | 3843387 | -0.407% | +22.9% |
| osdb | 3667508 | 3662304 | -0.142% | +8.7% |
| mr | 3656167 | 3651900 | -0.117% | +22.2% |
| mozilla | 19033237 | 19036400 | +0.017% | +10.1% |
| ooffice | 3078277 | 3078811 | +0.017% | +8.7% |
| sao | 5318086 | 5319425 | +0.025% | +5.7% |
| x-ray | 5957207 | 5959780 | +0.043% | +12.4% |
| total | 67576906 | 67367592 | -0.310% | +15.9% |
Text and structured data pay off. The four regressions are all binary or numeric data where the extra literals rarely buy anything back.
Total Silesia delta and the worst single-file regression per threshold.
| threshold | total | worst regression |
|---|---|---|
| 0 | -0.268% | x-ray +0.189% |
| 2 | -0.293% | x-ray +0.130% |
| 4 | -0.317% | x-ray +0.123% |
| 6 | -0.310% | x-ray +0.043% |
| 8 | -0.291% | x-ray +0.010% |
| 12 | -0.228% | mr +0.007% |
| 16 | -0.183% | mozilla -0.017% |
| 24 | -0.141% | ooffice +0.001% |
Threshold 4 gives the best total, 8 removes the regressions almost entirely, 6 is the balance point and is what the patch ships.
Searching a shallower chain for the second probe was also tried, shifting
max_chain_length right by 1 to 3. Ratio was unchanged and time only moved from
+16.0% to +14.8%, so the cost is the probe call itself and not the chain depth.
That matches level 9 already being past the point where a deeper chain pays.
The probe was later merged directly into level 9 on the working stack (develop + open PRs + block splitter + TOO_FAR gate + match pricing), where it compounds with the other match-selection work: silesia ratio 3.1531 to 3.1664 (+0.42%) at +16% time.
The silesia-only validation above hid a failure mode. On match-dense data with
degenerate chains the second search doubles the worst case: the literals synthetic
data type went 4.2ms to 41ms (10x) for zero ratio change, and dna +42% for +0.29%.
The fix is a per-block self-tuning gate: count probes and accepted probes, and stop
probing the block once acceptance proves rare.
(s->lazy2_probes < 256 || s->lazy2_hits * 16 >= s->lazy2_probes)With the gate, literals and dna return to full speed keeping their small ratio
gains, and silesia keeps +0.35% ratio at +11% time. Any future use of this patch
should include the gate, and validation should include literal-heavy and
degenerate-chain inputs, not just silesia.
- 70/70 ctest including
gtest_zlib. - 2000 fuzz iterations over generated data with random input and output chunk sizes.
- Chunked round-trips over all 12 Silesia files at chunk sizes 1, 7, 113, 4096, 65536.
- Level 9 output byte-identical to pristine
upstream/develop, so the change is inert below level 10.
One bug was worth recording. The first version corrupted streams under chunked I/O
only. sym_buf lives inside pending_buf, and the two-literal path tallied its
second symbol after a FLUSH_BLOCK_ONLY that could not drain, so the symbol write
landed on compressed output that had not been handed to the caller yet. Every
encoder-side invariant still held, which is what made it slow to find: symbols
replayed correctly against the input, frequencies matched the symbol buffer,
distances were in range, and blocks tiled the stream exactly. The patch now emits
the first literal exactly as the single-literal step does and falls back to plain
lazy matching if the symbol buffer fills between the pair.
deflateInit2 and deflateParams now accept level 10, which diverges from zlib in
ZLIB_COMPAT builds where zlib returns Z_STREAM_ERROR. Gating it behind
!ZLIB_COMPAT is the conservative option.
Apple M5, 10 cores, 32 GB, macOS 26.6.2, Apple clang 21.0.0.
Release build, -D BUILD_SHARED_LIBS=OFF -D ZLIB_COMPAT=ON -D WITH_MAINTAINER_WARNINGS=ON.