7 ms·

Massive Speed Gains via Parallelized BZIP2 Compression

43 points by SnowLprd 14y ago

th0ma5 14y ago
Since our move to multicore over faster processors, I'm sure we'll see a lot of this sort of thing, that is, people suddenly realizing that their code will be some multiple faster if they can find a way to do operations in parallel. I imagine that the compression itself might be slightly less optimal however since similar blocks that could be compressed are on different threads? I didn't dig into how this might or might not be a concern with this project, however. Long of the short of it, however, parallel is the reality. In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable?
- malkia 14y ago
  "In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable?" - it could. that's what is done, but for LZ type compressor bigger dictionary (e.g. avoiding splits is for the better) - one more reason why there is .tar -> .tgz (or .tbz), while .zip compresses individually. It would be even better if files are arranged in such way that contentwise they are similar one after each other. I'm not compression expert, just average user since the early days of what we used to call it back in the day "solid" compression.
- wtetzner 14y ago
  >In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable? It doesn't seem unlikely that that's what they're doing, considering you can't pipe data to it on stdin.
- CJefferson 14y ago
  bz2, out of all current compression methods, is particularly parallisable, as it has already split the files up into 900k (or smaller) blocks, and compressed each individually (well, run BWT on each seperately at least).
- stcredzero 14y ago
  Since our move to multicore over faster processors, I'm sure we'll see a lot of this sort of thing, that is, people suddenly realizing that their code will be some multiple faster if they can find a way to do operations in parallel. Reimplementation of things like compression algorithms seems very math/algorithm-heavy and thus amenable to functional programming. How about the Haskell/OCaml guys re-implement a bunch of Un^x style utilities for us?
  - th0ma5 14y ago
    in theory gnu parallel can be used to automate an idea in place like xargs
wmf 14y ago
BTW, bz2 is kinda over. Check out xz and the parallel version pxz.
- vasi 14y ago
  I've also got my version of parallel xz: https://github.com/vasi/pixz https://github.com/vasi/pixz It doesn't require use of large temporary files like pxz, and the xz files it produces can also be decompressed in parallel.
  - LogicX 14y ago
    Looks worth trying out -- Can I suggest adding installation packages for: brew ubuntu (at least through launchpad)
  - ak217 14y ago
    vasi, thanks very much for writing pixz, I've had a great experience working with it and it sped up my code very significantly. The only thing I wish for is more documentation and inclusion in xz-utils (which I know is not up to you, but I'm hopeful).
    - vasi 14y ago
      Glad to hear it's been of use :) The author of xz is working on a parallel compression implementation of his own, which will hopefully be in future versions of xz.
  - SnowLprd 14y ago
    That looks very promising. As others have pointed out here, pixz would be much more accessible if one could simply install it via "brew install pixz" or "aptitude install pixz".
    - vasi 14y ago
      I welcome anybody who'd like to package it! I think it's already available in Arch Linux.
malkia 14y ago
"The results: 18.7 seconds for bzip2, and… wait for it… 3.5 seconds for pbzip2. That’s an increase of over 80%!" File cache effect? He should cold reboot first (not sure how you force the file cache out on OSX/linux, on Windows I do it with SysInternals RamMap) and try in different order. It could still be faster, but he could really be measuring I/O that was done in the first case, and not in the second. It's also strange that .tar files are used, not tar.bz2 or .tbz (if such extension makes sense)
- sciurus 14y ago
  On linux, it's echo 1 > /proc/sys/vm/drop_caches http://linux-mm.org/Drop_Caches http://linux-mm.org/Drop_Caches
  - minimax 14y ago
    Awesome tip! Thanks!
    - malkia 14y ago
      Yup. Thanks scirius! Anyone knows what's the one on OSX? (Or some multi-platform library that knows more about this stuff (Windows included))?
      - eridius 14y ago
        On OS X it's merely `purge`.
- SnowLprd 14y ago
  I'll do some additional testing to see if the results are affected by caching. Not sure why you're surprised that I used .tar files for the compression testing. As I mentioned in the article, most of the time I'm creating bzipped tarballs from directories of files, so it made sense to use what is, for me, a common real-world use case. Your mention of tar.bz/.tbz makes me think there's some misunderstanding, since clearly I wouldn't want to test compression of already-compressed files. But perhaps it's I who am misunderstanding your suggestion. Please feel free to enlighten me. :)
aphyr 14y ago
18.7 seconds for bzip2, and… wait for it… 3.5 seconds for pbzip2. That’s an increase of over 80%! Er, not really. How about... "pbzip2 reduced running time by 80%." "pbzip2 took only 20% as long as bzip2 did." "pbzip2 is five times faster."
- SnowLprd 14y ago
  Quite right. Clearly not enough coffee. Updated the article with better wording. Thanks!
sciurus 14y ago
For parallel gzip there's pigz (pronounced pig-zee). http://www.zlib.net/pigz/ http://www.zlib.net/pigz/
Inufu 14y ago
Is there a reason this is not the default?
- reidrac 14y ago
  I'm GNU tar user (I believe that's the version in most Linux distributions, but I may be wrong), so I tend to use -z for gzip, -j for bzip2 and -J for xz. That said, I guess using the "alternatives" framework in Linux it would be reasonably easy (and transparent) to support the parallel version of each tool as replacement to the regular one.
juiceandjuice 14y ago
bzip2 has always been parallelizable. At one point a few years ago I was working on a compressed file format with that included compressed block metadata, because bzip2 is most efficient when it gets about ~900kB to compress at a time. In effect, you split the file up into 900kb chunks, compress them in parallel, and recombine them into one file at the end.
BrainInAJar 14y ago
is there a pbzip2 that doesn't eat all your memory ?
mattst88 14y ago
I used to use pbzip2 before I learned about lbzip2 (http://lacos.hu/ http://lacos.hu/) lbzip2 is able to decompress single streams using multiple threads, which apparently pbzip2 cannot do. See the thread beginning with http://lists.debian.org/debian-mentors/2009/02/msg00098.html http://lists.debian.org/debian-mentors/2009/02/msg00098.html
rorrr 14y ago
A GPU implementation would be cool.
dguido 14y ago
Parallel gzip, in case anyone wanted it: http://zlib.net/pigz/ http://zlib.net/pigz/ I've used it to great effect during incident response when I needed to search through hundreds of gigs of logs at a time.

43 points by SnowLprd 14y ago

Since our move to multicore over faster processors, I'm sure we'll see a lot of this sort of thing, that is, people suddenly realizing that their code will be some multiple faster if they can find a way to do operations in parallel. I imagine that the compression itself might be slightly less optimal however since similar blocks that could be compressed are on different threads? I didn't dig into how this might or might not be a concern with this project, however. Long of the short of it, however, parallel is the reality. In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable?

malkia 14y ago
"In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable?" - it could. that's what is done, but for LZ type compressor bigger dictionary (e.g. avoiding splits is for the better) - one more reason why there is .tar -> .tgz (or .tbz), while .zip compresses individually. It would be even better if files are arranged in such way that contentwise they are similar one after each other. I'm not compression expert, just average user since the early days of what we used to call it back in the day "solid" compression.
wtetzner 14y ago
>In theory one could arbitrarily split the file, and then compress each of the splits and get a speed up that is roughly comparable? It doesn't seem unlikely that that's what they're doing, considering you can't pipe data to it on stdin.
CJefferson 14y ago
bz2, out of all current compression methods, is particularly parallisable, as it has already split the files up into 900k (or smaller) blocks, and compressed each individually (well, run BWT on each seperately at least).
stcredzero 14y ago
Since our move to multicore over faster processors, I'm sure we'll see a lot of this sort of thing, that is, people suddenly realizing that their code will be some multiple faster if they can find a way to do operations in parallel. Reimplementation of things like compression algorithms seems very math/algorithm-heavy and thus amenable to functional programming. How about the Haskell/OCaml guys re-implement a bunch of Un^x style utilities for us?
- th0ma5 14y ago
  in theory gnu parallel can be used to automate an idea in place like xargs

wmf 14y ago

BTW, bz2 is kinda over. Check out xz and the parallel version pxz.

vasi 14y ago
I've also got my version of parallel xz: https://github.com/vasi/pixz https://github.com/vasi/pixz It doesn't require use of large temporary files like pxz, and the xz files it produces can also be decompressed in parallel.
- LogicX 14y ago
  Looks worth trying out -- Can I suggest adding installation packages for: brew ubuntu (at least through launchpad)
- ak217 14y ago
  vasi, thanks very much for writing pixz, I've had a great experience working with it and it sped up my code very significantly. The only thing I wish for is more documentation and inclusion in xz-utils (which I know is not up to you, but I'm hopeful).
  - vasi 14y ago
    Glad to hear it's been of use :) The author of xz is working on a parallel compression implementation of his own, which will hopefully be in future versions of xz.
- SnowLprd 14y ago
  That looks very promising. As others have pointed out here, pixz would be much more accessible if one could simply install it via "brew install pixz" or "aptitude install pixz".
  - vasi 14y ago
    I welcome anybody who'd like to package it! I think it's already available in Arch Linux.

malkia 14y ago

"The results: 18.7 seconds for bzip2, and… wait for it… 3.5 seconds for pbzip2. That’s an increase of over 80%!" File cache effect? He should cold reboot first (not sure how you force the file cache out on OSX/linux, on Windows I do it with SysInternals RamMap) and try in different order. It could still be faster, but he could really be measuring I/O that was done in the first case, and not in the second. It's also strange that .tar files are used, not tar.bz2 or .tbz (if such extension makes sense)

sciurus 14y ago
On linux, it's echo 1 > /proc/sys/vm/drop_caches http://linux-mm.org/Drop_Caches http://linux-mm.org/Drop_Caches
- minimax 14y ago
  Awesome tip! Thanks!
  - malkia 14y ago
    Yup. Thanks scirius! Anyone knows what's the one on OSX? (Or some multi-platform library that knows more about this stuff (Windows included))?
    - eridius 14y ago
      On OS X it's merely `purge`.
SnowLprd 14y ago
I'll do some additional testing to see if the results are affected by caching. Not sure why you're surprised that I used .tar files for the compression testing. As I mentioned in the article, most of the time I'm creating bzipped tarballs from directories of files, so it made sense to use what is, for me, a common real-world use case. Your mention of tar.bz/.tbz makes me think there's some misunderstanding, since clearly I wouldn't want to test compression of already-compressed files. But perhaps it's I who am misunderstanding your suggestion. Please feel free to enlighten me. :)

aphyr 14y ago

18.7 seconds for bzip2, and… wait for it… 3.5 seconds for pbzip2. That’s an increase of over 80%! Er, not really. How about... "pbzip2 reduced running time by 80%." "pbzip2 took only 20% as long as bzip2 did." "pbzip2 is five times faster."

SnowLprd 14y ago
Quite right. Clearly not enough coffee. Updated the article with better wording. Thanks!

sciurus 14y ago

For parallel gzip there's pigz (pronounced pig-zee). http://www.zlib.net/pigz/ http://www.zlib.net/pigz/

Inufu 14y ago

Is there a reason this is not the default?

reidrac 14y ago
I'm GNU tar user (I believe that's the version in most Linux distributions, but I may be wrong), so I tend to use -z for gzip, -j for bzip2 and -J for xz. That said, I guess using the "alternatives" framework in Linux it would be reasonably easy (and transparent) to support the parallel version of each tool as replacement to the regular one.

juiceandjuice 14y ago

bzip2 has always been parallelizable. At one point a few years ago I was working on a compressed file format with that included compressed block metadata, because bzip2 is most efficient when it gets about ~900kB to compress at a time. In effect, you split the file up into 900kb chunks, compress them in parallel, and recombine them into one file at the end.

BrainInAJar 14y ago

is there a pbzip2 that doesn't eat all your memory ?

mattst88 14y ago

I used to use pbzip2 before I learned about lbzip2 (http://lacos.hu/ http://lacos.hu/) lbzip2 is able to decompress single streams using multiple threads, which apparently pbzip2 cannot do. See the thread beginning with http://lists.debian.org/debian-mentors/2009/02/msg00098.html http://lists.debian.org/debian-mentors/2009/02/msg00098.html

rorrr 14y ago

A GPU implementation would be cool.

dguido 14y ago

Parallel gzip, in case anyone wanted it: http://zlib.net/pigz/ http://zlib.net/pigz/ I've used it to great effect during incident response when I needed to search through hundreds of gigs of logs at a time.