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 Implementation | Throughput (ints/sec) | Cycles / int | Branch Miss Rate |
|---|---|---|---|
| Scalar LEB128 + scalar prefix delta | 410M / s | 7.80 | 4.12% |
| Masked VByte (SSSE3 pshufb) | 2.45B / s | 1.31 | 0.08% |
| StreamVByte + AVX-512VBMI permute | 6.82B / s | 0.47 | 0.01% |