Repository navigation
deflate: decode, then encode, faster than libdeflate on the hosted runners #13
Description
The owner's goal, 2026-09-27: stdx's DEFLATE decoder faster than libdeflate on GitHub's hosted runners, then each encoder level. Decision 14 expected 1 MiB decoding to match libdeflate at best; this issue aims past that.
Where it stands. Bench run 36267746852 at 7aa0098, reports bench/results/2026-09-26-deflate-encoder-search-*.md, 38 corpus files:
- gzip decoding of zlib level 6 streams: stdx runs at a median of 0.74 of libdeflate's speed on an AMD EPYC 9V45 and 0.70 on the Neoverse N2, and is faster on 7 of 38 files on each. The wins are the four 1 KiB bodies and grammar.lsp on both runners, with kennedy.xls and xargs.1 (1.001) on the EPYC and xargs.1 and json-16k on the N2. The largest losses are asyoulik.txt (0.55) and alice29.txt (0.57) on the EPYC, and nci and ooffice (0.64) on the N2.
- gzip encoding speed over libdeflate's: level 1 at 0.53 on x86-64 and 0.49 on aarch64, level 6 at 0.45 and 0.47, level 9 at 0.79 and 0.73.
- Ratio over libdeflate's: 0.904 at level 1, 1.000 at level 6, 0.989 at level 9.
Target.
- Decoding: a median above 1.00 of libdeflate's speed on
ubuntu-24.04and onubuntu-24.04-arm, over all 39 corpus files,shuffled/dickens-1mamong them. - Then encoding: each of levels 1, 6 and 9 above 1.00 of libdeflate's speed at the same level, at a ratio no worse than libdeflate's.
Every file where stdx still loses is listed, on each runner.
Rules that bind the work.
- libdeflate is a baseline only. Nobody reads its source, or any other implementation's (non-negotiable 5, decision 9). The work comes from RFC 1951 and from measurements.
- Numbers come from the runners (decisions 10 and 20):
bench.ymlwithbenchmark=deflatefor the ratios, andbenchmark=profilefor cycles, instructions and branch misses per octet. The N2's counters judge a decoder change; the M1 Pro only filters. The x86-64 runner draws an AMD or an Intel CPU at random, so only ratios within one job compare. - Fast paths follow decision 16.
@setRuntimeSafety(false)needs an A/B and the owner's ruling. Assembly for DEFLATE needs a decision entry, as decision 23 is for Zstandard, and the owner's ruling before any is written. - A change that does not beat the 5% noise floor leaves with its code. Each performance commit carries the comparison with libdeflate and zlib-ng, and each new check its mutations.
- No regression on the owner's M1 Pro: each performance commit is measured on the Mac against main first.
The check. bench-deflate on both runners in one run: the median of stdx over libdeflate above 1.00 over the 39 files for decoding, then per encoder level for speed with the ratio held, the losing files listed. differential-deflate and differential-encode pass, the fuzzer runs, and every new check reports its mutations. Each result goes into design §8, under steps 7 and 9.
Activity
test(deflate): copy two chunks before the length's test, on Intel
test(bench): draw Intel runners and profile decoding there
test(deflate): load a match's first chunks in halves, on Intel
test(bench): draw Intel runners and profile decoding there
test(bench): draw Intel runners and profile decoding there
c4milo commentedon Sep 28, 2026
Target 1, decoding: met. Landed on main as 7c29419 to 11b5b8a. Medians of stdx's gzip decode speed over libdeflate's, 39 files, zlib level 6:
ubuntu-24.04-armubuntu-24.04ubuntu-24.04ubuntu-24.04Runs 36478169575 (N2 and EPYC) and 36478163045 (Intel: a temporary workflow that kept only the Intel CPUs its jobs drew). Against zlib-ng: 1.40, 1.20 and 1.30 to 1.33.
Where stdx still loses, below 1.00 of libdeflate:
What moved it, with each step's runs: design §8 step 7, the entry "Issue 13, checked on 2026-09-28". The common loop runs in assembly under decision 29, numbered after main's 27 and 28. CI passed on all three runners: run 36489727777.
Next: the files above, then encoding. The median target is met, but stdx still loses 13 to 18 files per CPU, so the decoder work goes on with them first. The lead is the branch between combined and plain table entries in blocks that mix both: on a Xeon 8370C, those files ran 4 to 9% faster with S11 off, while text ran slower.
For target 2, at the same commit stdx encodes at 0.54 of libdeflate's speed at level 1 on the EPYC and 0.49 on the N2, 0.50 and 0.47 at level 6, and 0.83 and 0.72 at level 9. Its ratio is 0.909 of libdeflate's at level 1, 1.000 at level 6 and 0.990 at level 9 (run 36478169575).
test(bench): draw Intel runners and profile their losing files
feat(bench): time stdx's gzip decoding built for x86-64-v3 as well
ci: time both decoders on synthetic streams, one statistic at a time
ci: time both decoders on synthetic streams, one statistic at a time
perf(deflate): keep x86-64 tables plain under a 4/5 combined share
perf(deflate): load a match's first chunks before storing any
perf(deflate): keep x86-64 tables plain under a 5/6 combined share
feat(bench): time stdx's gzip decoding built for x86-64-v3 as well
c4milo commentedon Sep 29, 2026
Second round, 2026-09-29, for the files that still lose. The median target held; the owner asked for every file and ruled the constraints in decision 34 (smaller gains may stay, a 12-bit table measured, x86-64 also benchmarked at v3), and then kept the clean-room rule: libdeflate stays a black box.
Method. Raw DEFLATE streams whose symbol statistics vary one at a time (literal code lengths, run lengths, distances, lengths, plain share, near sources, random distances, mixes), decoded by libdeflate and by stdx in one program on each runner CPU drawn. Runs 36504398125, 36505458044, 36506506249, 36507428104, 36508216806.
Found.
Landed (f4c60e3): the aarch64 lookup before the refill: N2, six jobs, sao, osdb, samba and mozilla +1 to 3%, no file down; and the x86-64-v3 report in
bench-deflate(stdx built for v3 runs 1.1% faster at the median on an EPYC 7763, the small bodies 4 to 8%).Measured and not kept. The x86-64 early lookup (Intel text −2 to 6%, ooffice −3.6% on a 9V74); four literals per refill (loses to it everywhere); a rolling copy and a loads-first copy for distances 17 to 31 (2.5× on the streams, 0.985 and 0.991 on the N2 corpus: those distances are 3 to 9% of a file's matches, and a branch taken that rarely is mispredicted nearly every time it is taken); plain tables for blocks under a combined-share threshold on x86-64 (at 7/8, 4/5 and 5/6: nci +3 to 10% and ptt5 +2.5 to 4% on Intel, but css-1m −5% on an EPYC 7763 and, at 5/6, osdb −2.9% and a median of 0.995 on the Intel 8573C); the per-block 12-bit table (css-1m and html-1m +3 to 7%, text −2 to 4% on AMD, nci −3% on the N2).
Standing at f4c60e3, from the A/B jobs' baselines: N2 1.090 to 1.094 of libdeflate, faster on 28 or 29 of 39, behind on ooffice 0.90, nci 0.90, mozilla 0.91, ptt5 0.94, osdb 0.95, sao 0.96, samba 0.96, dickens-1m 0.97; EPYC 7763 1.015 to 1.026 (24 or 25); EPYC 9V45 1.032 (21; ptt5 0.86, nci 0.88, css-1m 0.89, html-1m 0.90); Intel Xeon 8573C 0.984 and 0.997 (18 or 19; ptt5 0.84, css-1m 0.87, html-1m 0.87, nci 0.89). On the N2 the remaining gap on the literal-heavy files is the branch misses of S11's combined-or-plain entry and of the literal runs; on Intel it is the plain share of the HTTP bodies. Details in design §8 step 7.
c4milo commentedon Sep 29, 2026
The encoder, 2026-09-29: fast loops and decision 36
Seven commits on main, 6ed7806 to 5e36c10: design §8 step 9's entry of 2026-09-29 and decision 36 hold the record.
Speed with the same output (run 36556604513, main and 8eae6af in one job; stdx's gzip encoder over libdeflate's, the median of 39 files, and stdx over its own before):
The symbol writer stores 8 octets at once and runs on local state; the chain walk hoists its checks; the greedy and lazy levels decide the positions with the whole lookahead ahead in loops that keep their state in locals.
Size, from a comparison of libdeflate's output symbols with stdx's (decision 36, run 36559451595; output over libdeflate's, the 39 files' median):
Level 1 makes the positions a match of 8 octets or fewer covers heads too; the lazy step compares its two matches by length less a distance penalty. Their cost on the runners: level 1 at 0.91 to 0.93 of its speed (text 0.80 to 0.88, E.coli 0.68 to 0.73); level 6 json-1m at 0.75; level 9 json-1m at 0.63 to 0.66.
What stands between level 6 and libdeflate: the chain walk, about 10 cycles a candidate (two dependent loads) at 2 to 5 candidates an octet. Refused at equal memory: bucketed heads, an 8-octet second table, a shorter lazy length, the penalty inside the walk. A 64-candidate budget would trade 0.3 to 0.6% of size for 12 to 27% of time; not ruled. The 1 KiB files stay the slowest against libdeflate at every level (0.34 to 0.45 on the N2).
c4milo commentedon Sep 29, 2026
Level 6's budget, 2026-09-29: 64 candidates with a cut of 16, measured at the owner's request and adopted (8847786; decision 36 records it). Run 36568474837, main and the budget in one job: level 6's speed over libdeflate's from 0.58 to 0.66 on the N2 and from 0.57 to 0.64 on the EPYC 7763, stdx at 1.12 and 1.15 times its own speed at the median with no file slower (E.coli 1.7, reymont 1.3, json-1m 1.3). Output over libdeflate's stays at the median (0.999 to 1.000); per file a median 0.15% larger, 16 of 39 files over 0.2%, the worst E.coli 1.6%, reymont 1.2%, xml 1.1%. Levels 1 and 9 unchanged. Reports:
bench/results/2026-09-29-deflate-encoder-budget-*.md.c4milo commentedon Sep 29, 2026
Level 6's chain walk, 2026-09-29: after a taken match the lazy step's two searches now walk their chains in one loop, so their dependent loads overlap (7f262fa,
best_pair; design §8 step 9's entry). Output is identical on every file. Run 36594809955, main and the change in one job: level 6's speed over libdeflate's from 0.66 to 0.69 on the N2 and from 0.62 to 0.67 on an EPYC 9V74, stdx at 1.07 and 1.06 times its own speed at the median, the text files 1.12 to 1.16, E.coli 1.12 and 1.35, the four 1 KiB files 0.98 to 0.99. Compression unchanged: 35.8%, 29.4% and 29.2% of the input at levels 1, 6 and 9 (medians), 1.055, 1.000 and 1.010 of libdeflate's output.Measured and not kept: the pair at level 9 (kennedy.xls 0.87 on both runners, run 36586101645), and a prefetch of the head the step inserts next (a wash, run 36586241515). Level 6 stands at 0.67 to 0.69 of libdeflate's speed at equal size; what remains is the walk's own latency, two dependent loads a candidate, which only a structure with more state would shorten.
c4milo commentedon Oct 17, 2026
The encoder, 2026-10-17: where each level stands against libdeflate. This comment covers the encoder only. Main is 2038eea, and its encoder code is the code of f0ff50d.
The numbers come from runs 38298500583 and 38298503481. Each job ran main (1e300a2) first and then f0ff50d. The tables read the second program of run 38298503481, which drew a Neoverse N2 and an AMD EPYC 7763. The N2's other job gives the same counts. The other x86-64 job drew an EPYC 9V45, whose second program ran faster for libdeflate too, so it is not used here. Sizes are gzip members.
Rows slower than libdeflate, as stdx's speed over libdeflate's:
Rows larger than libdeflate's:
What landed after the last comment. Design §8 step 9 holds each change with its runs.
Next. The owner chose level 6 on x86-64 as the next gap on 2026-10-17.