Stream VByte

Deep dive

How it works

In: an array of u32 · Out: a control stream (⌈n/4⌉ bytes) followed by a data stream of 1-4 bytes per value · State: none (a 4 KB shuffle table, built once); the decoder must know n · Cost: O(n); one table lookup and one 16-byte shuffle per 4 values

1. Group values in 4s. For each value, length L = bytes needed (1-4); code = L − 1 (2 bits).
2. Control byte = codes of the 4 values (value 0 in bits 0-1). Control stream: ⌈n/4⌉ bytes, then the data stream.
3. Data stream: each value's L low bytes, little-endian, concatenated.
4. Decode a group: c = control byte; load 16 bytes at the data cursor; pshufb with shuffle[c] (mask bytes 0x80 produce zero); store 4 u32; advance by length[c] (4-16).
5. The last partial group and the last < 16 bytes of data are decoded with scalar code.

values   5      300        70000          1
lengths  1      2          3              1      control = 0b00_10_01_00 (value 0 in the low 2 bits)
data     05 | 2C 01 | 70 11 01 | 01       (7 bytes)
shuffle  [0,80,80,80, 1,2,80,80, 3,4,5,80, 6,80,80,80]

Code

/// Layout: [control bytes: ceil(n/4)][data bytes].
pub fn encode(vals: &[u32]) -> Vec<u8> {
    let mut out = vec![0u8; (vals.len() + 3) / 4];
    for (i, &v) in vals.iter().enumerate() {
        let len = ((32 - (v | 1).leading_zeros() + 7) / 8) as usize; // 1..=4
        out[i / 4] |= ((len - 1) as u8) << (2 * (i % 4));
        out.extend_from_slice(&v.to_le_bytes()[..len]);
    }
    out
}

fn read_one(buf: &[u8], pos: &mut usize, code: u8) -> u32 {
    let len = (code & 3) as usize + 1;
    let mut b = [0u8; 4];
    b[..len].copy_from_slice(&buf[*pos..*pos + len]);
    *pos += len;
    u32::from_le_bytes(b)
}

pub fn decode_scalar(buf: &[u8], n: usize) -> Vec<u32> {
    let mut pos = (n + 3) / 4;
    (0..n).map(|i| read_one(buf, &mut pos, buf[i / 4] >> (2 * (i % 4)))).collect()
}

/// shuffle[c]: pshufb mask for control byte c (0x80 = write zero); length[c]: data bytes used.
pub fn tables() -> (Box<[[u8; 16]; 256]>, [u8; 256]) {
    let (mut shuffle, mut length) = (Box::new([[0x80u8; 16]; 256]), [0u8; 256]);
    for c in 0..256 {
        let mut off = 0u8;
        for k in 0..4 {
            let len = ((c >> (2 * k)) & 3) as u8 + 1;
            for j in 0..len { shuffle[c][4 * k + j as usize] = off + j; }
            off += len;
        }
        length[c] = off;
    }
    (shuffle, length)
}

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "ssse3")]
pub unsafe fn decode_ssse3(buf: &[u8], n: usize, shuffle: &[[u8; 16]; 256], length: &[u8; 256]) -> Vec<u32> {
    use std::arch::x86_64::*;
    let mut out = vec![0u32; n];
    let mut pos = (n + 3) / 4;
    let mut g = 0;
    while g < n / 4 && pos + 16 <= buf.len() { // the 16-byte load must stay inside the buffer
        let c = buf[g] as usize;
        unsafe {
            let data = _mm_loadu_si128(buf.as_ptr().add(pos) as *const __m128i);
            let mask = _mm_loadu_si128(shuffle[c].as_ptr() as *const __m128i);
            _mm_storeu_si128(out.as_mut_ptr().add(4 * g) as *mut __m128i, _mm_shuffle_epi8(data, mask));
        }
        pos += length[c] as usize;
        g += 1;
    }
    for i in 4 * g..n { out[i] = read_one(buf, &mut pos, buf[i / 4] >> (2 * (i % 4))); } // scalar tail
    out
}

On ARM the same loop uses vqtbl1q_u8 (NEON table lookup) in place of _mm_shuffle_epi8.

Complexity and constants

• Per group of 4: 1 control byte load, 2 table loads (mask, length; both L1), 1 unaligned 16-byte load, 1 shuffle, 1 store, 1 add. No branches except the loop.
• The serial dependency is only the data cursor (pos += length[c]), about 5-6 cycles per group (load-to-use latency), so throughput is in the range of ~1 value per cycle or better; the paper measured billions of values per second on one core.
• Encoding is also branch-light and vectorizable (compute lengths with lzcnt, build control bytes, compact with a shuffle).
• Size vs varint: 8 payload bits per data byte + 2 control bits per value, vs 7 payload bits per byte. Stream VByte is 0.25 bytes larger for values < 128 and smaller for 128-255, 2^14-2^16, 2^21-2^24 and 2^28-2^32.

Efficiency

• Cost: per group of 4: one control-byte load, two table loads (mask and length, both L1), one unaligned 16-byte load, one shuffle, one store, one add; no branches except the loop. The only serial dependency is the data cursor (about 5-6 cycles per group), so throughput is about 1 value per cycle or better; the paper reports billions of values per second on one core, about 2x Masked VByte. Size: 1.25-4.25 bytes per value. Bound: the cursor dependency, then L1 bandwidth.
• Levers:
  • pad the data stream by 16 bytes — drops the end-of-buffer check from the SIMD loop — decoders you control
  • delta variant (svb_delta) — SIMD prefix sum fused into decode — sorted lists
  • 0124 variant — zero values cost no data bytes — sparse counters
  • checkpoints every k groups — random access without decoding from the start — long arrays
  • NEON vqtbl1q_u8 instead of pshufb — same loop on ARM — AArch64
• Naive → standard → state of the art:
  • varint · one data-dependent branch per byte
  • Masked VByte / Group Varint · SIMD or inline control byte
  • Stream VByte · branch-free, about 2x Masked VByte

Implementation notes

• Pad the data stream with 16 bytes so the SIMD loop never needs the "16 bytes remaining" check; the reference library uses a scalar tail instead.
• Delta variant (svb_delta): decode, then SIMD prefix sum within the 4 lanes plus a broadcast of the previous last value; for sorted lists.
• 0124 variant: codes for 0, 1, 2, 4 bytes, so zeros cost no data bytes; good for sparse counters.
• Random access: store a checkpoint (data offset) every k groups; the offset of a group can also be computed by summing length[] over control bytes (SIMD popcount-like sums).
• AVX2: decode 8 values per step using two control bytes and two 128-bit lanes; gains are modest because the cursor dependency dominates.

Pitfalls

• Reading 16 bytes past the end of the buffer in the SIMD loop: a segfault at page boundaries, rarely in tests. Bound the loop as above or pad.
• Forgetting that value 0 still needs 1 byte (v | 1 trick) in the standard format.
• Storing control bytes interleaved with data (Group Varint style) changes the format; both sides must agree.
• Using it for tiny values where bit packing is 2-4× smaller.

Variants and alternatives

In production

Lemire's streamvbyte C library is used by RediSearch (search), StarRocks and UpscaleDB (databases), Facebook Thrift (serialization) and tilemaker (map tiles), per its README. Group Varint, the design it vectorizes, is used in Google's web search serving and Meta's folly.

Implementations

Sources

• D. Lemire, N. Kurz, C. Rupp, Stream VByte: Faster Byte-Oriented Integer Compression, Information Processing Letters, 2018. paper · arXiv · code
• J. Plaisance, N. Kurz, D. Lemire, Vectorized VByte Decoding, arXiv:1503.07387, 2015. arXiv · code
• A. A. Stepanov, A. R. Gangolli, D. E. Rose, R. J. Ernst, P. S. Oberoi, SIMD-Based Decoding of Posting Lists, CIKM, 2011. paper
• J. Dean, Challenges in Building Large-Scale Information Retrieval Systems, WSDM keynote, 2009.