Re:Parallelising Huffman decoding and x86 disassembly by syn...
by dougall on Saturday July 30, 2022 @08:25PM
(#32291790)
Yep. 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-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), so still <10% of available memory bandwidth.
Re:Parallelising Huffman decoding and x86 disassembly by syn...
by mananaysiempre on Saturday July 30, 2022 @01:59PM
(#32288852)
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.
Re:Parallelising Huffman decoding and x86 disassembly by syn...
by wolf550e on Saturday July 30, 2022 @06:15PM
(#32290901)
Modern 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-o...
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.