News for hackers. Stuff that matters.
Re:Parallelising Huffman decoding and x86 disassembly by syn... by londons_explore on Saturday July 30, 2022 @01:45PM (#32288737)
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.

Re:Parallelising Huffman decoding and x86 disassembly by syn... by hinkley on Saturday July 30, 2022 @02:47PM (#32289254)
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.