Bit-Packed Integer Arrays and Vectorized Decoding

An array of integers smaller than 2^32 wastes bits when stored as 32-bit words. A field that takes values from 0 to 12 needs 4 bits; storing it in 32 bits spends 28 bits per element on zeros. Bit packing stores k-bit values back to back in a bit stream, which cuts the array’s size by a factor of 32/k and, on a memory-bound scan, cuts the runtime by the same factor. The saving is paid for at decode time, and the cost of that payment is the subject worth understanding.

The packing arithmetic

With a fixed width k, element i occupies bits i·k through i·k + k − 1 of the stream. Reading it means locating the 64-bit word that contains bit i·k, shifting right by the bit offset, and masking off the bits above k. When the value straddles a word boundary, two words are needed and the low part must be shifted into place and combined.

/* Fixed-width k-bit decode, k in [1, 32]. */
static inline uint32_t get_bits(const uint64_t *buf, size_t i, unsigned k) {
    size_t bit = i * k;
    size_t w = bit >> 6;              /* word index */
    unsigned off = bit & 63;          /* bit offset within the word */
    uint64_t v = buf[w] >> off;
    if (off + k > 64)                 /* straddles the word boundary */
        v |= buf[w + 1] << (64 - off);
    return (uint32_t)(v & ((1ULL << k) - 1));
}

For k a divisor of 64 — 1, 2, 4, 8, 16, 32 — no value straddles a word, so the branch disappears and the decode is a load, a shift, and a mask. Those widths are the ones with fast paths, which is why formats that support arbitrary widths also carry the width as metadata so the decoder can specialize.

The branch in the general case is the real cost. For k = 5, a 64-bit word holds twelve values with four bits left over, and the bit offsets of successive elements advance by five modulo 64, so the pattern of straddles repeats every 64 elements and about one element in sixteen crosses a word boundary. A branch taken that often is a misprediction waiting to happen if the branch predictor cannot learn the period. Unrolling by the number of elements per word — twelve for k = 5 — makes the straddle position a compile-time constant within the unrolled body and removes the branch entirely.

Encoding has the mirror problem: a value that straddles must be split across two words with read-modify- write on both, and two threads writing adjacent elements of the same word contend on the word rather than on the elements. Packing is therefore usually done sequentially, or in blocks aligned to word boundaries, so that each block’s final partial word is private to the writer.

Why the saving is real on a memory-bound scan

A scan over 100 million 32-bit values reads 400 MB. Packed at 5 bits per value, the same values occupy 62.5 MB. If the scan’s cost is dominated by fetching bytes from DRAM, the packed version moves about a sixth of the bytes (the ratio is 6.4 to 1) and, in the ideal case where nothing else becomes the bottleneck, takes a proportionally shorter time. If the scan is dominated by the decode arithmetic, the packed version can be slower, because the decode is several instructions per element against a single load for the unpacked array.

The regime where packing wins is therefore the one where the working set exceeds the last-level cache and the decode is cheap enough to hide under the memory latency. That regime is the common one for inverted indexes, posting lists, and column stores, which is why those systems pack. For an array that fits in L2, the unpacked version is usually the faster of the two: the bytes are already in cache, and the extra shift and mask per element is pure overhead. The cache behaviour that separates these two regimes is the one described in Sequential Scans, Hardware Prefetch, and the Page Walk.

There is a second, quieter benefit. A packed array’s line holds more values than an unpacked one’s, so a loop that scans and discards is less sensitive to the fraction of each line it uses. A 64-byte line is 512 bits, which holds 102 five-bit values against sixteen 32-bit values; the line count for a given number of values drops by a factor of about six, and the prefetcher has fewer lines to keep in flight. The same stride-versus-line reasoning, applied to records rather than bit fields, appears in Array of Structs or Struct of Arrays.

SIMD decoding with byte shuffles

The vectorized approach takes the bit stream apart in fixed-size groups and uses a shuffle to place bytes where they belong. The pshufb instruction on x86-64 (introduced with SSSE3) permutes the bytes of a 128-bit register according to a mask held in another register, with a mask byte of 0x80 producing a zero. That single instruction can gather the bytes of several packed values into the low half of their destination lanes, after which a shift and a mask per lane place each value’s bits correctly.

The shuffle is a byte permutation, so it can move whole bytes and nothing finer. A value of k bits that straddles a byte boundary in the packed stream must have the two contributing bytes brought into the same lane, and the mask determines which byte of the source lands in which position of the result. For a group of 128 bits holding 128/k values, the mask is a compile-time constant per k, generated once as a table with one entry per width. A width whose values do not share a common byte alignment needs a second step, because the low bits of the value may begin partway through a byte; that is what the per-lane shift after the shuffle is for, and it is why the shift amount is part of the mask table rather than a single constant.

/* One 128-bit group: align bytes with pshufb, then shift and mask per lane. */
static inline __m128i unpack8(__m128i packed, __m128i shuffle,
                              __m128i shift, __m128i mask) {
    __m128i aligned = _mm_shuffle_epi8(packed, shuffle);   /* pshufb */
    return _mm_and_si128(_mm_srlv_epi32(aligned, shift), mask);
}

The _mm_srlv_epi32 variable shift requires AVX2: it shifts each 32-bit lane by its own count, which SSE cannot express. A decoder restricted to SSSE3 must instead use a fixed shift count per mask table entry, which works because every group of the same width has the same bit offsets. The width dependence is why decoders carry separate code paths for SSSE3, AVX2, and AVX-512, and why the same compressed stream decodes at different speeds on different generations of the same architecture.

The mask table is the part that must be exact. A shuffle mask that places a byte in the wrong lane produces values that are individually plausible, since they are the right bytes shifted, and the error appears only as a wrong value in the output, not as a crash. This is the failure mode that makes hand-written unpacking code worth testing against a scalar reference on random inputs.

Delta and frame-of-reference before packing

Packing a field whose values span a wide range does not help: if the values are uniformly distributed over 32 bits, the width is 32 and nothing is saved. Compression comes from making the values small first. Two transformations do most of the work.

Frame of reference subtracts the minimum of a block from every value, so a block of values in [1000000, 1000255] becomes values in [0, 255] and packs at 8 bits instead of 20. The block’s reference value is stored alongside the packed data.

Delta encoding stores the difference between consecutive values rather than the values themselves. For a sorted list of identifiers, the differences are small even when the identifiers are large. The first value of a block is stored in full and the rest as deltas, so the width is determined by the largest gap in the block rather than by the largest identifier.

Both transformations make the width a per-block property, which means the decoder must read a header per block before it can choose a decode path. That header read is a dependent load, and a block small enough to keep the header overhead low is also small enough that the decoder cannot amortize the setup. Blocks of 128 to 256 values are the usual compromise; the trade is between header overhead and the probability that one outlier forces a wider block than the rest of the values need.

The failure modes worth knowing

Width zero. A block whose values are all equal after frame-of-reference has a largest difference of zero, so zero bits are needed per value. The general decode path does not survive this: (1ULL << 0) - 1 is zero, so the mask is zero and the decode returns zero for every element, which is correct only when the block’s reference value is itself zero. For any non-zero reference the decoded values are all reference plus zero, which is the reference repeated — correct only by coincidence of the encoder having chosen that reference. Encoders therefore special-case width zero and emit a run-length block carrying only the reference and the count, and decoders branch on the width before entering the bit arithmetic.

Shift by the word size. In the general decode, buf[w + 1] << (64 - off) with off = 0 shifts by 64, which is undefined behaviour in C. On x86 the shift count is masked to six bits, so the shift by 64 becomes a shift by zero and the straddle branch silently produces a wrong value rather than a trap. Widths of 64 need their own path, not the general one.

Signed values. Packing a signed integer into k bits requires either a bias or sign extension on decode. In two’s complement, −1 in k bits is all ones, so a decoder that masks without sign-extending returns 2^k − 1 where the encoder wrote −1. The decoded value is never negative, and every negative input arrives as a large positive number, which shifts the whole negative half of the range rather than producing a small error. The usual fixes are to bias the values into the non-negative range before packing, or to sign-extend the top bit after the mask.

Unchecked widths. A width read from an untrusted stream can exceed the word size. Every decoder that accepts external data must validate the width before computing i * k, because the multiplication itself can overflow the index type and the subsequent load can address outside the buffer.

The packing decision is a decision about where the bottleneck is. For an array whose scan is bound by bytes, the memory layout argument that favours the split layout applies with the same force: fewer bytes per element means fewer lines touched per element. For an array that fits in cache, the arithmetic is the cost and the packing is a loss. The same trade appears in reverse when the values are records rather than integers and the packing is done by choosing a smaller element type instead of a bit width.