Hellishly Slow Level 13 DEFLATE Compression

Why DEFLATE

DEFLATE remains worth optimising because its decoders are already everywhere: HTTP content encoding, ZIP archives, PNG internals, software distribution, backup tools, and embedded formats still use the same LZ77 plus Huffman design. The decoder contract is fixed, but the encoder still chooses matches, block boundaries, and Huffman tables; better choices improve size without changing compatibility.

The baseline is libdeflate level 12, one of the strongest practical DEFLATE encoders. The level 13 implementation was contributed upstream as pull request.

Level 13 Mechanics

Level 13 keeps libdeflate’s near optimal parser, but makes its choices more expensive. It searches the full 32 KiB DEFLATE window, permits 15 optimisation passes, and applies static Huffman optimisation to blocks up to 50'000 input bytes. No format extension is involved.

For text like data, level 13 delays block size commitment. It samples up to 64 KiB from the current block start; if the sample contains no NULL byte and at most 97 distinct byte values, the soft block size rises from 300'000 to 1'000'000 bytes. The assumption is simple: a stable byte distribution lets one Huffman table cover more data.

The parser broadens the minimum cost search. It can choose the cheapest offset for each match length, estimate initial Huffman costs from literal and match length statistics, estimate offset slot frequencies from cached matches, and compare measured dynamic Huffman cost against static Huffman and literal only encodings.

Block splitting is also delayed. The compressor stores up to nine split candidates with parser state, then scores the full block and a bounded shortest path over candidate intervals. A single split can win on cost; a multi split path must beat the full block by at least 512 bits. The selected parse is cached for final flushing.

The slowness is bounded. Search passes, split candidates, and block sizes are capped, so level 13 cannot enter an unbounded optimisation loop like turtledeflate or broader file optimizers such as ECT.

Regression Policy

Development used a zero compression regression policy against the Silesia corpus: many approaches were tried, but only changes that strictly decreased at least one compressed file, without increasing any other compressed file, survived into the final level 13 configuration.

The Silesia corpus is small enough for repeated development, but mixed enough to punish single file tuning: it contains text, binaries, databases, images, and structured data.

Silesia Results

Level 13 saves 86'990 bytes across the corpus, a 0.134% reduction, and adds 1'641'401 ms of runtime. The strongest relative result is nci at 0.296%; sao changes by only 0.004%.