Parallelising Huffman decoding and x86 disassembly by synchronising prefix codes
dougallj.wordpress.com
dougallj.wordpress.com
https://patentimages.storage.googleapis.com/ef/d2/2c/b54bbdf...
Shameless self promotion aside, I think the patent application includes some helpful diagrams to understand what is being done here - specifically page 25/26.
The authors of this repo/paper use the self-synchronizing property of almost all Huffman codes to implement parallel Huffman decoding on the GPU at ~10 GB/s. In practice, I haven't found this to be useful to do Huffman decoding on the CPU, since the GPU round-trip outweighs the speed of the GPU. But if your data is already on the GPU, this is a really cool way to to Huffman decoding.
I would assume that the memory read and write bandwidth of a CPU would be the limiting factor for any vaguely efficient implementation, not the actual processing.
But Huffman decoding also isn't even close to these numbers. Single stream decoding runs at about 6 cycles per byte, so you could maybe hit 533MB/s. By using instruction-level-parallelism on a single core I was able to reach 3.7GB/s (https://twitter.com/dougallj/status/1515260172783919105), so still <10% of available memory bandwidth.
An obvious solution would appear to be to simd-decode with say 16 lanes, each starting decoding 1/16th of the input data. When each decoder gets to the end of its chunk, continue a little further. Then use non-simd code to verify that every chunk has reached a sync point with the following point and splice together all the decided data.
And these days we are not as concerned about memory usage as we were when computer with modems might have only 384K of RAM, so a block structure with a length prefix is not such a bad strategy. Though should your blocks all be the same size or should you start a block every time the window needs to be reset? One is smaller, but the other has more predictable performance.
Wouldn't they also self synchronize but after far more bits?
Parallelizing ANS would be huge.
Notable uses of ANS: zstandard, JPEG XL. Apple and Dropbox also use it.
It is fast because it can be machine word oriented (you can read/write whole machine word sizes at a time, not arbitrary/variable bit length sequences), and as a result you can interleave any number of independent (parallel) encoders in the same stream with just a (parallel) prefix sum to figure out where to write state values (as whole machine words) when renormalization needs to occur in individual encoders. It is super SIMD friendly as a result (see https://arxiv.org/pdf/1402.3392.pdf).
I for one got up to 400 GB/s throughput on A100 GPUs in my implementation (https://github.com/facebookresearch/dietgpu), which to my knowledge is/was the fastest entropy coder out there on a commercially available hardware platform, so fast that we're using it to losslessly compress data before sending over PCIe/NVLink/Infiniband/etc during large scale neural network training while still being a win. Nvidia's nvCOMP library also recently added similar techniques.
ANS can also self-synchronize as well, but chunking data into fixed >=4 KiB segments has fairly minimal compression size overhead (you need an index to tell you where each variable sized compressed chunk begins) and is faster.