fast-brotli-wasm

Why quality 11 was the slow part

Calling brotli-wasm's compress() without options means quality 11, the highest setting, so that is what a caller gets by default. Nodepod's zlib polyfill takes the default. Qualities 10 and 11 work differently from the rest. They use a binary-tree match finder and then search for the cheapest way to write each block, in the manner of Zopfli: for every position they gather candidate matches, price each choice in bits with a cost model, and keep the cheapest path through the block. Quality 11 tries more start positions and longer matches than quality 10. Lower qualities skip most of that work, so the time per byte rises steeply near the top. The quality sweep below shows where.

Decompression has no such search. There is one correct output and the decoder only has to produce it, so it is already fast, and there is less to gain.

One rule: the same bytes

Making an optimizer faster usually means letting it decide differently. That is not allowed here. Code that hashes compressed output, keys a cache on it, or compares it with a fixture would notice a different, if valid, file. So the encoder keeps every decision it makes, including the tie-breaks between equal costs and the floating-point arithmetic that produces those costs. What changed is how the numbers are computed and how much of the work is skipped, and work is skipped only where the source shows it cannot change the result.

Finding matches, splitting blocks, grouping histograms

The match finder compares bytes 16 at a time with WebAssembly SIMD and visits candidates in the same order with the same checks. The static dictionary lookup does the same. Block splitting evaluates its per-symbol costs with SIMD, following the scalar loop's rule for which histogram wins. Histogram clustering tracks which bins are nonzero, computes the cost of a merged pair without building the merged histogram, and stops as soon as it knows the pair is not below the limit.

Work that never needed doing

The encoder's ring buffer is 8.3 MB at the default window, and at quality 10 and 11 the match finder allocates a forest of 32 MB. The original clears both. The rewrite does not, because every byte that is read has already been written, and it zeroes only the few bytes past the data that can be read early. When the caller passes the whole input, as compress() does, the forest is sized to the input instead of the window. That cost does not depend on the input size, so it is the likely reason the smallest inputs gain the most. Two pieces of code are compiled out because brotli-wasm only ever sets the quality: the per-metablock logging, and the stride and prior evaluators that only that logging runs.

What the sweep shows

Look at two columns. On the default input, time stays within a small range up to quality 9 and then jumps at 10 and 11, where the Zopfli-style search starts. Size keeps shrinking past 9, but by a few percent, not by anything like the factor that time grows. That is the trade quality 11 makes, and it suits data that is compressed once and read many times. Try the other inputs: the numbers move, the shape should not.

The speedup is not confined to the top. Faster match finding and less clearing of memory help every quality, and the speedup column shows it. The recorded results below say the same: 2.7x at quality 1 and 2.4x at quality 5 on 1 MB, and about 3x at quality 11.

A new decoder

decompress() runs a decoder written for wasm. It writes straight into one output buffer, and since that buffer holds the whole history, there is no ring buffer and no wrap handling. A 64-bit bit reader refills without branches from an 8-byte load. The tables it builds are fused: one lookup returns the symbol and its decoding information together, such as command lengths and distance parameters. Matches are copied in 16-byte SIMD chunks.

Its contract is narrow. It returns a result only for inputs on which the reference decoder returns the same bytes. Every error, and the few legal streams whose reference behaviour depends on its internal 4 KB chunking or that use large windows, go to the reference decoder, so error messages come from the original code path. It also mirrors the reference decoder's quirks, such as ignoring bytes after the last meta-block. Streams (DecompressStream) still use the reference decoder, which is why they gain 1.5x where decompress() gains about 2x.

Why the wasm is smaller

693 KB (228 KB brotli) against 1.01 MB (385 KB brotli), a third smaller as it sits on disk and roughly 40 to 46 percent smaller after brotli or gzip. Three changes account for it.

• No serde and no float formatting code. Options are parsed by a small parser built for size, and the one place that needs a formatted float leaves it to JavaScript.
• No metablock logging or its evaluators, as above.
• The encoder's four big lookup tables, 518 KB in all, are not stored. They are kept packed in 115 KB and rebuilt the first time an encoder is created. test/tables.mjs checks the rebuilt tables against brotli-wasm's own, entry by entry. The rebuild is part of first-call time: in Node, require() plus the first compress() takes 12.7 ms against 22.8 ms for brotli-wasm.

Where the speedup stops

At quality 11 the gain settles near 3x from a few tens of kilobytes upward. A native x86 build of the same encoder is no faster than the wasm, so the remaining time is the algorithm itself, not the platform. Faster versions exist, such as reordering relaxations across queue entries, but they can change tie-breaks and so the output, which this package does not allow. Other attempts gained nothing: probing the distance cache out of line, 16-byte queue entries, prefix tables for the dictionary, and prefetching. The dead ends are written down, and fast-pako's deflate stops near 2x for the same reason.

What is different

The wasm is built with SIMD (simd128), so it needs an engine that supports it; current Chrome, Firefox and Safari do. In browsers it is fetched from next to the JavaScript, as brotli-wasm's is. In Node, require() is synchronous and needs Node 20.19 or later. Stack traces inside panic reports differ from brotli-wasm's, since the frames are different code; the messages are the same.

The claim that the output is identical rests on tests rather than on the source alone. The compressor was compared with brotli-wasm at qualities 0 to 11 on 4,892 and 18,116 files from the pnpm store, the decoder in 290,446 checks that include corrupt streams and their errors, and the options parser in 25,655. How we check lists them all.