Model
Patched frame of reference
The cost of the block is set by its maximum, so a few outliers decide the width of everything; patching moves them aside.
- Width
- the chosen width
- Exceptions
- the number of exceptions
- Full width
- the bits for a full value
- Position width
- the bits for a position inside the block
Worked examples, recomputed
Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.
- 128 values in a 256-wide range → 1,056 bits
- one outlier forces 31 bits: ≈ 3.9× worse
- PFOR with w = 8 and one exception → 1,062 bits
- 3,968 ÷ 1,062 ≈ 3.7× smaller
Where it appears
Each mechanism states it in its own names. The general symbol each name stands for is shown with it.
- Encoding, Serialization & Compression
What do we turn our values into when we turn them into bytes, and what does that choice cost?