ANS is super fast and trivially parallelizable, faster than Huffman or especially arithmetic encoding, and is superior to Huffman at least as far as compression ratios are concerned (symbol probabilities are not restricted to powers of 2, but unlike arithmetic encoding one is usually limited to something close to multiples of 2^-9 to 2^-13 for symbol probabilities, the limitation being due to required table sizes for rANS or tANS in high speed memories or in L1 cache).
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.
When decoding a large data block (ie. Megabytes), it really doesn't matter if a few tens of bytes get decoded twice to find a sync point.
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.
Before I gave up compression as a hobby my last big observation was that many algorithms are trying to juggle several concerns at once and wouldn’t it be better to double down on the bzip2 (of for that matter, optimizing compiler) strategy of making multiple passes. That’s not strictly speaking parallel decoding but it can be modeled by coroutines or streams, and involve quite a few cores if you so choose.
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.
Does parallelizing Huffman decoding on a modern CPU actually speed up 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.
It would be, if only you could load the CPU properly. Huffman decoding is highly serialized—an iteration per symbol in the FSM implementation is somewhat better than the loop iteration per bit in the naïve one, but every iteration still depends on basically everything in the previous one; you’re using a fraction of the scalar processing power of the core. Thus modern compressors resorting to format-incompatible tricks like interleaved streams, but how much to interleave depends on which class of CPU you’ll want to decode on.
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.
Shameless self promotion aside, I think the patent application includes some helpful diagrams to understand what is being done here - specifically page 25/26.
Hmm, yeah, this is a bit different, and probably a bit better for Huffman codes (though worse for my x86 use-case, where it's beneficial to know which parts of the subsequent streams are valid before decoding of the preceding stream completes) - I'll hopefully try it out in 16 years.
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.
14 comments
[ 2.9 ms ] story [ 43.2 ms ] threadWouldn'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.
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.
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.
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.