Just keep a note about the performance comparison of bzip2 v.s. pbzip2. (Not professional and accurate...)

Quotation
bzip2 is a freely available, patent free (see below), high-quality data compressor.
pbzip2 is a parallel implementation of the bzip2 block-sorting file compressor that uses pthreads and achieves near-linear speedup on SMP machines.

Here are the experiment results:

Time Command
bzip2 256.0s bzip2 -k svndump.txt
pbzip2 with 2 processors 126.4s pbzip2 -k -p2 -9 svndump.txt
pbzip2 with 4 processors 66.5s pbzip2 -k -p4 -9 svndump.txt
pbzip2 with 8 processors 53.9s pbzip2 -k -p8 -9 svndump.txt

It's interesting that using 8 processors cannot double the compression speed of using 4 processors.

Experiment Details

Test Environment
The test machine is 8cores Intel(R) Xeon(R) CPU E5620 @ 2.40GHz with CentOS 5.5.

The file to be compressed is a svn repository dump text file with size ~1.15GB:

1234087701 Oct  1 10:11 svndump.txt

bzip2

time bzip2 -k svndump.txt

real    4m16.064s
user    4m14.826s
sys 0m1.181s

pbzip2 with 2 processors

time pbzip2 -k -p2 -9 svndump.txt

real    2m6.352s
user    4m11.332s
sys 0m2.256s

pbzip2 with 4 processors

time pbzip2 -k -p4 -9 svndump.txt

real    1m6.548s
user    4m25.353s
sys 0m1.810s

pbzip2 with 8 processors

time pbzip2 -k -p8 -9 it-repos.dump.txt

real    0m53.934s
user    7m5.333s
sys 0m2.034s