Fabian Giesen

The post surveys existing approaches to parallel Huffman decoding—multi-stream, interleaved (e.g. GDeflate), and speculative brute force—and explains why each carries costs like gather-heavy access, magic interleave constants baked into wire formats, or discarding 80%+ of work. PivCo-Huffman sidesteps these by recasting decoding as list merges reducible to prefix sums, scaling to any vector width. The bulk derives merge kernels for AVX-512 VBMI2, SSE4.2/AVX2, and NEON, trading lookup-table size against instruction count; results are mainly on high-end hardware.

The author explains that ryg_rans is a toy demonstration of rANS—like a hardware-store board displaying fastener options—not a production library, and that its static byte model, alias-table variant, multiple SIMD interleaving variants, and bitstream format are all unfit for real use. He gives concrete recommendations: 32/16 or 64/32-bit state renormalization, two-state implicit interleaving, forward modeling with backward encoding, and adaptive EMA models, preferring tANS when probabilities are static.

The article argues that mainstream CPUs—whether strongly or weakly ordered—do not literally obey their memory models; they optimistically reorder accesses and use a "trust but verify" scheme, rolling back and retrying when contention is detected. The real distinction is that strongly ordered machines track metadata for every in-flight access and retry more often under contention, while weakly ordered ones have more legal orderings. Empirically, large-scale ARM and x86 servers behave similarly, so the author advises contending less rather than contending faster.