3 ms·
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 l
by londons_explore 4y ago
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.
- mananaysiempre 4y agoIt 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.
- foota 4y agoA single core is able to load less memory per second than the whole cpu because there is a limited number of resources per core for loading memory.
- wolf550e 4y agoModern compression formats are optimized for decoding huffman streams in parallel. See for example Fabian Giesen explaining about RAD's codecs and also about Yann Collet's zstandard: https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-oodle-data-huffman-coding/ https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-o...
- deleted 4y ago[deleted]
- dougall 4y agoYep. The M1 Max has a single-core memory bandwidth of 102GB/s, and an all-core bandwidth of 224GB/s, so splitting work across cores gives you more bandwidth: https://www.anandtech.com/show/17024/apple-m1-max-performance-review/2 https://www.anandtech.com/show/17024/apple-m1-max-performanc... 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 https://twitter.com/dougallj/status/1515260172783919105), so still <10% of available memory bandwidth.