Probably this software existed for a quite long time but I didn’t know its existence ’til now: pbzip2
it’s basically a bzip2 algorithm implementation with pthreads support. This mean, in a always more SMP world, that you can greatly improve your bzipping perfomances (divide the zipping time by the number of cores you have et voilà!)
Compression syntax is totally compatible:
$ pbzip2 big.file
while to unzip you have to do
$ pbzip2 -d big.file.bz2
Use with caution (or with -l and -p switches) cause you can easily saturate your 4xSix-cores monster.