Bit packing and PFOR

Deep dive

How it works

In: an array of unsigned integers, in blocks of 128 · Out: per block a bit width b, 128·b packed bits and an exception list · State: none · Cost: O(n); about 0.5-1 cycle per integer with SIMD in L1/L2

1. Split the array into blocks of 128 values (delta- or FOR-transformed first if useful).
2. Plain bit packing: b = bits of the block maximum; write each value's b low bits consecutively.
3. PFOR: build a histogram of bit widths; for each candidate b, cost = 128·b + exceptions·(cost per exception); pick the cheapest.
4. Pack the low b bits of every value; store exception positions and their high bits (value >> b).
5. Decode: unpack all 128 values (branch-free, specialized per b), then OR the high bits into the exception slots.

values  3 1 6 2 900 5 0 7        b = 3 (900 is the exception)
packed  011 001 110 010 100 101 000 111     (900 & 7 = 4)
patch   pos 4: high = 900 >> 3 = 112  ->  4 | 112<<3 = 900

Layouts: horizontal (value i at bit i·b, shown above) or vertical/interleaved (SIMD-BP128: 4 lanes, value i in lane i mod 4) so each SIMD lane unpacks independently with the same shift sequence. FastLanes generalizes this to 1024-bit virtual registers and a transposed order that also makes delta decoding parallel.

Code

pub const BLOCK: usize = 128;

fn bits(v: u32) -> u32 { 32 - v.leading_zeros() }
fn mask(b: u32) -> u64 { (1u64 << b) - 1 } // b in 0..=32

/// Pack 128 values with `b` bits each into 4*b words (horizontal layout).
pub fn pack(vals: &[u32; BLOCK], b: u32, out: &mut Vec<u32>) {
    let (mut acc, mut n) = (0u64, 0u32);
    for &v in vals {
        acc |= (v as u64 & mask(b)) << n;
        n += b;
        if n >= 32 { out.push(acc as u32); acc >>= 32; n -= 32; }
    } // 128*b is a multiple of 32: nothing left over
}

pub fn unpack(words: &[u32], b: u32, out: &mut [u32; BLOCK]) {
    if b == 0 { out.fill(0); return; }
    for (i, o) in out.iter_mut().enumerate() {
        let (w, sh) = (i * b as usize / 32, (i * b as usize % 32) as u32);
        let mut x = words[w] as u64;
        if sh + b > 32 { x |= (words[w + 1] as u64) << 32; } // value straddles two words
        *o = ((x >> sh) & mask(b)) as u32;
    }
}

/// Patched frame-of-reference block.
pub struct Pfor { pub b: u32, pub packed: Vec<u32>, pub exc_pos: Vec<u8>, pub exc_high: Vec<u32> }

pub fn pfor_encode(vals: &[u32; BLOCK]) -> Pfor {
    let mut hist = [0usize; 33];
    for &v in vals { hist[bits(v) as usize] += 1; }
    let max_b = (0..=32).rev().find(|&i| hist[i] > 0).unwrap_or(0);
    // cost in bits; an exception costs 8 (position) + 32 (high part, stored unpacked here)
    let (mut best_b, mut best_cost, mut exceptions) = (max_b, BLOCK * max_b, 0);
    for b in (0..max_b).rev() {
        exceptions += hist[b + 1]; // values needing more than b bits
        let cost = BLOCK * b + exceptions * 40;
        if cost < best_cost { (best_b, best_cost) = (b, cost); }
    }
    let b = best_b as u32;
    let (mut low, mut exc_pos, mut exc_high) = ([0u32; BLOCK], Vec::new(), Vec::new());
    for (i, &v) in vals.iter().enumerate() {
        low[i] = (v as u64 & mask(b)) as u32;
        if bits(v) > b { exc_pos.push(i as u8); exc_high.push(v >> b); }
    }
    let mut packed = Vec::with_capacity(4 * b as usize);
    pack(&low, b, &mut packed);
    Pfor { b, packed, exc_pos, exc_high }
}

pub fn pfor_decode(p: &Pfor, out: &mut [u32; BLOCK]) {
    unpack(&p.packed, p.b, out);
    for (&i, &h) in p.exc_pos.iter().zip(&p.exc_high) { out[i as usize] |= h << p.b; } // patch
}

Complexity and constants

• Size: 128·b bits + 8-bit header per block, plus exceptions. Sorted doc IDs with delta: order of 2-8 bits/int for dense lists.
• Decode: specialized unpackers (one unrolled function per b = 0..32, generated code) avoid the division and branch in the generic loop above; with SSE/AVX2 vertical layout, about 0.5-1 cycle per integer or less when data is in L1/L2.
• PFOR patching is a scalar loop over a few exceptions per block; keeping exceptions ≤ ~10 % keeps it negligible.
• Random access with fixed b: value i is at bit i·b, one or two word loads, no decoding of neighbours.

Efficiency

• Cost: 128·b bits plus an 8-bit header per block, plus exceptions; sorted doc IDs with delta take order of 2-8 bits per integer. Decode with SIMD in a vertical layout is about 0.5-1 cycle per integer when the block is in L1/L2, order of billions of integers per second per core (Lemire and Boytsov 2015). Scalar FastLanes reports more than 100 billion integers per second (Afroozeh and Boncz, VLDB 2023). Bound: compute while data is cached, memory bandwidth for large scans.
• Levers:
  • one unrolled unpacker per b (0..32, generated) — no division or branch in the loop — all hot decode paths
  • vertical layout, 4 or 8 lanes — one shift/mask/store decodes 4 (SSE) or 8 (AVX2) values — bulk decode
  • choose b by histogram, not maximum — avoids a 30-50 % waste on skewed blocks — PFOR encoders
  • keep exceptions under about 10 % of a block — patching loop stays negligible — PFOR
  • D4 deltas or FastLanes transposed layout — parallel prefix sum — delta plus packing
• Naive → standard → state of the art:
  • varint · one data-dependent branch per byte
  • SIMD-BP128 or PFOR blocks · order of billions of integers per second
  • FastLanes layout with scalar code on 1024-value blocks · tens to over 100 billion integers per second

Implementation notes

• Generate the unpack kernels: 33 functions with constant shifts (compilers vectorize them); FastLanes and Lemire's libraries ship generated code.
• Vertical layout for SIMD: lane j holds values j, j+4, j+8, … so one vector shift/mask/store sequence decodes 4 (SSE) or 8 (AVX2) values at once.
• Delta + bit packing: decode is unpack then prefix sum; the prefix sum becomes the bottleneck, so use D4 deltas or FastLanes' transposed layout.
• Exceptions: NewPFD stores exception high bits compressed (Simple16/bit-packed); OptPFD picks b per block to minimize size; Lucene keeps up to a handful of exceptions per 128-int block.
• Tail block: the last partial block is often encoded with varint instead of padding.
• Choose block size by access pattern: 128 for skip-heavy posting lists (skip pointers per block), 1024+ for columnar scans.

Pitfalls

• Shifting a u32 by 32 is UB in C (and panics in Rust): b = 32 and b = 0 need special cases (use u64 masks as above).
• A single outlier in plain bit packing inflates the whole block; that is exactly what PFOR fixes.
• Reading words[w + 1] past the end on the last value: allocate one padding word or check bounds.
• Choosing b by maximum when values are skewed wastes 30-50 %; use the histogram.
• Unaligned or byte-granular storage of packed words defeats SIMD loads; keep blocks 16- or 32-byte aligned when possible.

Variants and alternatives

In production

Search engines: Lucene/Elasticsearch/OpenSearch postings (128-int FOR/PFOR blocks). Databases: DuckDB bitpacking compression, ClickHouse T64 codec. File formats: Parquet RLE/bit-packing hybrid (definition levels, dictionary indices; see the Parquet encodings spec), Apache ORC, Vortex/FastLanes-based formats. Libraries: Lemire's FastPFor and SIMDCompressionAndIntersection.

Implementations

Sources

• J. Goldstein, R. Ramakrishnan, U. Shaft, Compressing Relations and Indexes, ICDE, 1998. paper
• M. Zukowski, S. Héman, N. Nes, P. Boncz, Super-Scalar RAM-CPU Cache Compression, ICDE, 2006. paper
• H. Yan, S. Ding, T. Suel, Inverted Index Compression and Query Processing with Optimized Document Ordering, WWW, 2009. paper
• D. Lemire, L. Boytsov, Decoding billions of integers per second through vectorization, Software: Practice and Experience, 2015. paper · arXiv · code
• A. Afroozeh, P. Boncz, The FastLanes Compression Layout: Decoding >100 Billion Integers per Second with Scalar Code, VLDB, 2023. paper · code
• Apache Parquet documentation, Encodings (RLE/bit-packing hybrid, delta binary packed). docs