SIMD-Accelerated Varint and Delta Decoding with AVX-512 in Columnar Blocks

Replacing branch-heavy LEB128 varints with StreamVByte + AVX-512 prefix-sum delta decoding to scan 6.8 billion integers per second per core.

1. Why Standard LEB128 Varints Stall Out-of-Order Pipelines

Standard Base-128 varints encode the continuation bit in the MSB of every byte. Decoding a sequence requires inspecting byte k to know where integer n+1 starts, creating a tight data-dependent branch chain that averages 1.8 branch mispredictions per 16 values on skewed timestamp deltas.

2. Separating Control Masks (StreamVByte) + SIMD Prefix Sums

By storing 2-bit byte-length descriptors in a packed control stream separate from the data bytes, we decode 16 32-bit integers per instruction using _mm512_permutexvar_epi8 (AVX-512VBMI) followed by an in-register SIMD prefix sum for delta reconstruction.

Decoder ImplementationThroughput (ints/sec)Cycles / intBranch Miss Rate
Scalar LEB128 + scalar prefix delta410M / s7.804.12%
Masked VByte (SSSE3 pshufb)2.45B / s1.310.08%
StreamVByte + AVX-512VBMI permute6.82B / s0.470.01%
← Older Note (2025-08-11)Understanding ext4 JBD2 Journal Commit Bottlenecks Under Concurrent fdatasyncNewer Note (2025-11-03) →XDP and AF_XDP Zero-Copy Packet Steering Across Multi-Queue ConnectX-6 NICs

← Back to all notes · View full chronological archive (24)