lbzip2 0.15-1 (amd64 binary) in ubuntu karmic

 Lbzip2 is a Pthreads-based parallel bzip2/bunzip2 filter, passable to GNU tar
 with the --use-compress-program option. It isn't restricted to regular files
 on input, nor output. Lbzip2 utilizes multiple threads and an input-bound
 splitter even when decompressing bz2 files created by standard bzip2.
 Successful splitting for decompression isn't guaranteed, just very likely
 (failure is detected). Splitting in both modes and compression itself occur
 with an approximate 900k block size.
 .
 On an Athlon-64 X2 6000+, lbzip2 was 92% faster than standard bzip2 when
 compressing, and 45% faster when decompressing (based on wall clock time).
 .
 On a 2x Quad-Core Opteron 2352, lbzip2 was 588% faster than standard bzip2
 when compressing, and 394% faster when decompressing (based on wall clock
 time).