Lbzip2 is an independent, multi-threaded implementation of bzip2. It is commonly the fastest SMP (and uniprocessor) bzip2 compressor and decompressor.

lbzip2 integrates nicely with GNU tar.