Rebased onto upstream/develop (6cfa7d52) and re-measured. Upstream has since introduced
MAX_LEN_ROOT_BITS, so the change is now a one-macro bump plus ENOUGH_LENS, with a second
commit adding an adaptive gate.
Apple M5, 4 P-cores + 6 E-cores, 32 GB, macOS 26.5.2, Apple clang 21.0.0.
Release build, BUILD_SHARED_LIBS=OFF, WITH_MAINTAINER_WARNINGS=ON.
All figures are CPU time, medians of 7 repetitions, --benchmark_cooldown=5.
Google Benchmark's within-run CV badly understates run-to-run variance on this workload. Two identical runs of the same binary with the same environment differed by up to 3.96%, while the reported CV was 0.07%. Treating CV as the error bar produced two confident findings that were both pure artifact and vanished on re-measurement.
Everything below therefore uses one binary with the root size selected at runtime, so both arms execute byte-identical code at identical addresses and the code-layout confound is gone. Runs are bracketed A-B-A so the two matching arms give a real error bar, and deltas are corrected against benchmarks that provably cannot be affected by the change.
Results that did not resolve above their own drift are omitted rather than reported as small wins or losses.
Control-corrected against sao and x-ray, which keep the smaller root in both arms and so
measure pure per-pass bias. Only files that resolved beyond their own A-vs-A drift are listed.
| file | root=11 | gated | drift | blocks kept at root=11 |
|---|---|---|---|---|
| osdb | -10.22% | -10.69% | 1.30% | 100% |
| mr | -7.17% | -6.45% | 0.16% | 75% |
| mozilla | -2.00% | -1.67% | 0.34% | 73% |
| ooffice | -1.32% | -2.09% | 0.94% | 88% |
Geomean across all 12 Silesia files is -1.51% unconditional and -1.85% gated.
The original PR figures reproduce on the rebase and are, if anything, slightly understated. osdb was reported at -9.4% and measures -10.22%. mr was reported at -5.7% and measures -7.17%. mozilla was reported at -1.9% and measures -2.00%.
A clean rebuild without the runtime switch reproduces this independently, at osdb -10.71% and mr -5.30%.
Measured by counting second-level length lookups at root=10 versus root=11. The difference is exactly the number of symbols decoded through an 11-bit code.
| data type | symbols decoded at 11 bits |
|---|---|
mixed |
2.609% |
realistic_rgb |
0.125% |
literals |
0.077% |
short_match |
0.063% |
text |
0.050% |
dna |
0.002% |
random emits only stored blocks and striped_rgb tops out at 4-bit codes, so neither can be
affected at all.
Of the synthetic benchmark data types, mixed is the only one with enough 11-bit traffic to win,
at -7.28% at 1 MB and -3.22% at 128 KB. literals is the only measurable cost at
+0.61%, which tracks its 29 dynamic blocks per megabyte rather than anything about its
alphabet. Every other synthetic data type sits inside the noise floor.
Real-world data is very different from the synthetic set here. Silesia blocks carry far more code
space above 10 bits than any generated type except mixed, which is why the corpus shows wins the
synthetic benchmarks mostly cannot.
The second commit decides per block whether the larger root table is worth building, using the code space sitting above the smaller root:
if (type == LENS && root == MAX_LEN_ROOT_BITS) {
unsigned space = 0;
for (len = root; len <= MAX_BITS; len++)
space += (unsigned)count[len] << (MAX_BITS - len);
if (space < ROOT_GROW_MIN_SPACE)
root--;
}count[] is already built by inflate_table, so this is a handful of adds on values in registers.
An existence check on the code-length alphabet, asking merely whether a code longer than 10 bits
is possible, does not work. dna contains two 11-bit codes and would pass, yet decodes them
0.002% of the time. Weighting by code space separates the two cases, and per block it predicts
the measured 11-bit traffic well, computing 2.62% for mixed against 2.609% measured.
On Silesia the gate keeps root=11 for 100% of osdb's blocks, 82% of nci's, 75% of mr's and 73% of
mozilla's, and disables it entirely for sao and x-ray.
Honest status of the gate. It fully preserves the large wins and costs nothing where it triggers, but no individual file shows a benefit that resolves above the drift. Its justification is that it bounds the worst case on data holding long codes it rarely decodes, which is a property of the input rather than of this corpus. It should not be described as a measured speedup.
inflate_state grows 4032 bytes, since ENOUGH_LENS must be 2340 whether or not any given block
uses the larger root. The gate does not recover that, and only lazy allocation of the extended
table would.