A deep technical exploration of the PivCo-Huffman algorithm, which transforms Huffman decoding from a serial process into a sequence of parallelizable list merge operations. The post explains why traditional Huffman decoding is hard to parallelize, how PivCo-Huffman reframes it as a prefix-sum/merge problem, and then dives into efficient SIMD implementations of the core merge primitive across AVX-512, SSE4.2/SSSE3, AVX2, and ARM NEON. Key insights include using precomputed 2KiB shuffle index tables for 8-byte chunks, a clever index encoding trick to handle 16-byte chunks with a single ADD instruction, and a near-optimal NEON implementation using 2-register TBL with absolute difference (VABD) to combine index vectors in one instruction.
Table of contents
Enter PivCoThe merge operationThe basic approach: 8 bytes at a timeTowards 16 bytes at a timeThe NEON specialRelated28 Impressions