Is good data compression an inherently single threaded task?
On one hand, the best lossless data compression programs nowadays are single-threaded. Those which support multiple cores always seem to sacrifice a tiny bit of compression ratio compared to their single core settings. It seems that, to achieve the best compression, an algorithm should calculate the next output bit or byte from the entirety of the previous input context, which seems like an inherently serial computation.
On the other hand, the Burrows-Wheeler suffix sorting stage of bzip2 seems very parallelizable, so we imagine a parallelizable extended Burrows-Wheeler compression program in which the whole input is always treated as one (possibly very large) block. Sorting probably does not achieve linear speed up with number of cores.
Inspired by Brotli, which compresses well, but is very slow, and does not (yet) offer multicore compression.
No comments :
Post a Comment