General-purpose compression: the last pass

What does the final zip-like pass do, and what does it destroy?

This stage knows nothing

Every stage so far knew something. Serialization knew the schema. Lightweight encoding knew the type and looked at the distribution. This stage knows nothing. It sees a byte stream with no types, no field boundaries, and no idea that value 7 is different from value 8.

That ignorance is both the loss and the whole point.

• What it loses is obvious: typed comparisons, random access, aggregation on the encoded form, everything that made the previous stage useful to a query engine.
• What it gains is less obvious, and it is the reason this pass survives at the end of the pipeline: it can see redundancy that exists nowhere inside a single value. The string https://api.internal.example.com/v2/ may appear forty thousand times across three different columns. Every type-aware codec misses it, because that redundancy is not a property of any one column's distribution. It is a property of the byte stream, and only something that reads the byte stream can find it.

The new constraint defines the stage: the output is not addressable. Until now every encoded form was still a data structure. You could index into it, compare inside it, skip over it. A compressed block is one indivisible object. To read one byte, you produce all of them.

Those three things being the same number is the whole design problem of this article.

---

Two kinds of redundancy, therefore two mechanisms

In an untyped byte stream, redundancy comes in exactly two forms.

• Repetition. The same substring occurred before, so replace it with a reference to the earlier copy. This is match modelling, the LZ family (LZ77 and its descendants).
• Skew. Symbols are not equally likely, so spend fewer bits on the frequent ones. This is entropy coding.

They are independent, and neither includes the other. LZ output still contains skewed literals, match lengths and offsets. Entropy coding alone cannot see a repeat longer than one symbol. So every serious general-purpose codec combines both. The long list of codec names is just the occupied corners of a 2×2 table:

The top-left corner is not a weakness. It is a deliberate sacrifice of 20–30% ratio for a 3–5× gain in speed. As the break-even rule from Bytes become an output showed (D/B > r/(r−1)), that is often the right trade. Once you read the landscape this way, you do not need to memorize the names.

After lightweight encoding: does a last pass belong at all?

After good lightweight encoding, a general-purpose codec typically adds only 1.2–1.5×. Put r = 1.35 into D / B > r / (r − 1): the right side is 1.35 / 0.35 ≈ 3.86. So you need a decode speed almost four times the bandwidth of your pipe to break even.

• On object storage, B per connection is about 80 MB/s. A decoder at 1 GB/s is about 12× the bandwidth. Trivially satisfied.
• On local NVMe at 3–7 GB/s, you need 3.86 × (3 to 7) = 12–28 GB/s of decode speed. That is several cores doing nothing else.

The question is not "which general-purpose codec?" but "does one belong in the pipeline at all?" The answer depends on where the data is stored, not on what is in it.

---

Entropy coding: where the floor is, and why the coder stopped mattering

Shannon's result says the best length for a symbol with probability p is −log₂ p bits. Averaged over all symbols, this gives the entropy H(p). This section is about how close real coders get to that floor, and what they charge.

Huffman coding

Huffman coding gives each symbol a code of a whole number of bits (frequent symbols get short codes). The rounding to whole bits is its whole story.

Gallager proved that Huffman's total redundancy is at most pmax + 0.086 bits per symbol (pmax is the probability of the most likely symbol). This is the exact statement of the failure: Huffman is near-optimal on flat distributions, and worst exactly where compression matters most, on skewed ones.

The classical fix is to code blocks of symbols (pairs or triples), so the rounding loss is shared across more probability. It works, but the alphabet grows as nᵏ for tuples of width k. This is the "fixed cost sets a natural batch size" idea in an unusual form: the fixed cost is the fractional bit you must round up, and the batch size is the tuple width. It is the first case where the fixed cost is measured in fractions of a bit, not in time.

Arithmetic coding

Arithmetic coding removes the rounding. It represents the whole message as one number in the interval [0, 1), which is split in proportion to the symbol probabilities. The total overhead is under two bits for the entire message, so the per-symbol overhead goes to zero. The price is a multiply and a divide per symbol, and a strictly serial dependency: roughly 100–200 MB/s.

A claim that is easy to get wrong: deflate uses Huffman, not arithmetic coding, for patent reasons and because of the CPU budget of 1993, not for technical reasons. Arithmetic coding was covered by patents during most of the period when today's common formats were standardized. When you see Huffman in a format specification, you are usually looking at the result of intellectual-property law. That is an economic accident that looks like a design decision.

ANS and FSE

ANS (asymmetric numeral systems) and its table-based form FSE (finite state entropy) changed the field. They are the reason ZSTD replaced almost everything instead of just competing. ANS reaches arithmetic-coding ratios with a table-driven state machine. The coder state is one integer. Encoding changes the state and emits bits. Decoding is a table lookup and a shift. It has no branches, no multiplication in the hot path, and runs at 1–2 GB/s.

Two properties matter in practice.

• ANS is LIFO (last in, first out): you encode in one direction and decode in the other. So the block must be fully buffered. This ties ANS to block-based formats and rules out true streaming.
• Because the state is only an integer, you can run several interleaved ANS streams in one thread and decode them in parallel to keep the CPU pipeline full. This uses instruction-level parallelism (a CPU executing several independent instructions at once) to solve a compression problem, and it is where the GB/s come from.

So the honest reason for ZSTD's dominance is: FSE replacing Huffman, a better match finder, a larger default window, and careful implementation. It is not tuning, and not magic.

The coder is solved; the model is not

This number changes how you should think about the whole stage. On English text:

The gap between the first row and the last is 4×, and it is all model, not coder. Any of the three coders above gets within a few percent of what the model says. None can close the gap from 4.3 to 1.1.

This is what assuming independence costs, as a measured number. An order-0 model is exactly the assumption that symbols are independent. On English text, that assumption costs a factor of four. The cost of assuming independence is not a vague risk. It is a number you can compute by comparing your model's order with the true conditional entropy.

Why does nobody collect this gain? Context-mixing models run at 100 KB/s–1 MB/s. That is three to four orders of magnitude slower than ZSTD, for roughly 2× more ratio. The last 2× of ratio costs about 1000× the CPU. The exchange rate is harsh. So data pipelines sit permanently at the cheap end of a curve that everybody knows is not the ceiling.

---

The LZ family

LZ77 slides a window over the input. At each position it emits either a literal (the byte itself) or a (offset, length) reference: "copy length bytes starting offset bytes back." Three parameters define any member of the family.

Window size. How far back a match may reach. Deflate: 32 KB. LZ4: 64 KB. Brotli: up to 16 MB. ZSTD: 8 MB by default at high levels, and configurable far beyond that.

Match-finding effort. The method used to look for matches: hash chains, binary trees, or optimal parsing over a suffix structure. This is where the compression level lives, almost entirely.

Minimum match length. Below it, the reference token costs more than the literals it replaces. LZ4's minimum of 4 follows from its token size of about 3 bytes.

Window and block together limit what can be found

The derivation with the most practical consequence is this one: the redundancy a codec can find is bounded by min(window, block). A match cannot cross a block boundary, because blocks are compressed independently. It also cannot reach further back than the window.

Same data, same codec, two orders of magnitude of difference, decided only by framing. "Small files compress badly" is not a rule of thumb. It follows from the window having nothing in it. It is the same structural fact that made small files a serialization problem, returning with a different cost.

Why compression is slow and decompression is fast

The speed gap can be derived. Compression must search: it compares many candidates at each input position. Decompression only follows: read an offset, copy from a known place. Searching is unbounded work that you choose to spend. Copying is fixed work. So decompression is structurally 5–300× faster than compression, and (the important part) roughly independent of the level, because the level only controlled how hard the encoder searched.

Typical numbers on mixed text-and-binary data, one core:

Read the zlib -6 row and the ZSTD -3 row together. They carry a correction that should be stated plainly: ZSTD is not a trade-off against gzip. It strictly dominates it. It gives the same ratio at five to eight times the compression speed and three to four times the decompression speed. Strict domination (better on every measure) is rare in engineering. It means there is no technical reason for deflate to remain anywhere except where the wire format forces it: HTTP, gzip files, and Parquet files written by older writers. If you choose gzip today, you chose worse on every axis.