Bit Packing and Frame-of-Reference Blocks

Byte-aligned codes pay a fixed tax: every integer occupies a whole number of bytes, so a gap of three consumes eight bits when it needs two. Bit packing removes that tax by storing a block of integers at a uniform width in bits, chosen per block to fit the largest value it holds. The scheme is the default in modern index formats for one reason beyond space: a fixed-width block can be decoded with straight-line code and, on machines with vector registers, several values per instruction.

The design has three knobs — block length, how the width is chosen, and what happens to values that do not fit — and each of them is a real trade rather than a formality.

Frame of reference: subtracting the block minimum

Consider a block of 128 postings gaps. If the gaps are all under 16, storing each in four bits gives 64 bytes for the block, against 128 for vByte. The width is chosen after inspecting the block, so the decoder needs to know the width before it can decode, which means the block carries a few bits of header.

Gaps are already differences, so a block of gaps has a minimum near zero and a maximum set by the densest sparse patch. A block of document identifiers, by contrast, has a minimum near the block’s starting point and a range that may be much narrower than the absolute values. Frame of reference exploits this: subtract the block minimum from every value before packing, and store the minimum separately. Identifiers clustered in a narrow band — a block from a list of a static collection, for instance — then pack into the width of the range rather than the width of the identifier space.

The combination used in practice is delta encoding within a block and frame of reference at the block boundary: the first value participates in the previous block’s chain, and the interior values are gaps. Whether the minimum subtraction adds anything depends on whether the gaps themselves are being packed, in which case the minimum is usually zero or one and the subtraction is a no-op that costs a stored field. Implementations that pack absolute identifiers use frame of reference and get a genuine saving; implementations that pack gaps often skip it.

Choosing the width and the block length

Width per block is computed as the position of the highest set bit of the block maximum, so a maximum of 1000 needs ten bits. Two regions of the block can differ wildly, and a single width is set by the worst case in the block. This is the fundamental cost of uniform-width packing: a block whose values are mostly 1 with one value of 100,000 pays 17 bits for all 128.

The waste is bounded by the block size and the value distribution. If the largest value is more than a small factor above the median, widening the block wastes space; if it is close, the saving over per-value codes is real. The standard response is to shrink the block so outliers affect fewer neighbours. With blocks of 128 postings, one outlier wastes 127 × (w − w_typical) bits; with blocks of 32, it wastes 31. But smaller blocks mean more headers and more frequent width changes, and the skip/offset array grows in proportion.

Block lengths in use cluster at powers of two between 32 and 256. Powers of two matter because the decoder’s unrolled loop, the byte alignment of the packed payload, and the correspondence between a posting index and its block all become shifts and masks rather than divisions. A block of 128 values at width w occupies exactly 16w bytes, which aligns to a cache line at widths of 4, 8, 16 bits and does not at others.

A block that is byte-aligned is not required but is convenient: some formats pad the last partial byte of a block so blocks start on byte boundaries, others allow a block to end mid-byte and let the next block begin there. The padded form wastes up to seven bits per block; the unpadded form makes random access arithmetic depend on the widths of all preceding blocks unless an offset array is kept.

Straight-line decoding

The point of a fixed width is that the decoder has no data-dependent control flow. Decoding 128 values of width w reads a stream of bits and emits a stream of integers, and the number of bits consumed is known from the header:

/* Decode n values of `width` bits from packed, byte-aligned, LSB-first. */
void unpack(const uint8_t *packed, unsigned width, int n, uint32_t *out) {
    uint64_t buf = 0;
    unsigned have = 0, pos = 0;
    for (int i = 0; i < n; i++) {
        while (have < width) {              /* refill; loop is width-bounded */
            buf |= (uint64_t)packed[pos++] << have;
            have += 8;
        }
        out[i] = (uint32_t)(buf & ((1ULL << width) - 1));
        buf >>= width;
        have -= width;
    }
}

The refill loop is data-independent given a fixed width, so the branch predicts perfectly once the width is known. Still, it is a loop. The faster form peels the refill out: for widths that divide 64, a 64-bit load supplies several values before any refill is needed, and the compiler can unroll the whole block into a fixed sequence. This is why the useful widths are the ones with a fixed unrolled shape — 1, 2, 4, 8, 16, 32 bits in particular, where a block of 128 turns into a known number of word loads with shifts and masks.

Vectorised decoders go further and process a whole block with a shuffle against a per-width mask table, producing several integers per vector instruction. The dependency chain is the shift-and-mask sequence, and because each vector lane is independent, the pipeline fills. The catch is that the vectorised path requires the block to be byte-aligned and the width to be one of a small set, which pushes format design toward widths that have fast kernels. Widths like 3, 5, 6, 7, 9, 11 are legal but fall back to scalar decoding, and the fallback may erase the space advantage of the narrower width.

Patched frames and the exception problem

A block where one value is much larger than the rest is the recurring problem. Two strategies exist.

The first is to split the value: encode it at the block’s chosen width with high bits stored separately. This is the “patched frame of reference” idea. Choose the width from a percentile or from a small multiple of the block’s average rather than from the maximum, then record exceptions in a side array. Each exception needs its position within the block and its high bits, so an exception costs more than one extra unit of ordinary width but applies to few values.

The second is to forbid the problem by choosing a larger width and paying uniformly. For blocks of 128 with one outlier, that is roughly 127 times the excess bits, which exceeds the cost of a handful of exceptions once the outlier is more than a factor of about two above the rest. In practice the crossover is not a stable constant: it depends on how many exceptions and how wide the side entries are.

Patched schemes add a decode complication. The main loop produces a value for every position, and the patcher then overwrites some of them, requiring either a bounds check per position or a second pass. Implementations that care about decode throughput find the second pass or the branch costs more than the space it saves, and use a plain maximum-derived width. Implementations that care about space, typically those storing the index on a medium with scarce bandwidth, accept the extra work.

Where bit packing stops scaling

The scheme’s cost per encoded value is the block maximum’s bit width, so it is sensitive to the distribution’s tail. For a heavy-tailed gap distribution, widening the block to fit the tail wastes bits over the body, and the block size must shrink to isolate the tail. At small block sizes, the header, the width-change overhead and the offset array stop being negligible, and the format approaches a per-value code in cost while keeping a fixed-width decoder.

Then there is the decode-side arithmetic. Bit-packed decoding is fast per block but requires the whole block to be located; a query that seeks to one identifier decodes the entire block containing it, not just the value. With blocks of 128, a seek into a list of a million postings decodes 128 values to use a few, which is why bit-packed formats are paired with a coarse skip array whose records are block-granular and why conjunctions of short lists sometimes prefer the byte-aligned code with finer-grained skipping.

The closer-to-optimal alternatives for monotone sequences are Elias-Fano and the Golomb family, both analysed in Elias-Fano for monotone sequences and Golomb-Rice coding postings gaps. They win on space for skewed distributions and lose on decode simplicity, which is the axis that separates index formats designed for disk bandwidth from those designed for in-memory query throughput. The choice between bit packing and the byte-aligned baseline described in delta encoding with variable bytes is the same axis at a smaller scale.