What compression tools are available in Ubuntu that can benefit from a multi-core CPU.
There are two main tools.
Well, the keyword was parallel. After looking for all compression tools that were also parallel I found the following:
PXZ - Parallel XZ is a compression utility that takes advantage of running LZMA compression of different parts of an input file on multiple cores and processors simultaneously. Its primary goal is to utilize all resources to speed up compression time with minimal possible influence on compression ratio.
PLZIP - Lzip is a lossless data compressor based on the LZMA algorithm, with very safe integrity checking and a user interface similar to the one of gzip or bzip2. Lzip decompresses almost as fast as gzip and compresses better than bzip2, which makes it well suited for software distribution and data archiving.
Plzip is a massively parallel (multi-threaded) version of lzip using the lzip file format; the files produced by plzip are fully compatible with lzip.
Plzip is intended for faster compression/decompression of big files on multiprocessor machines, which makes it specially well suited for distribution of big software files and large scale data archiving. On files big enough, plzip can use hundreds of processors.
PIGZ - pigz, which stands for Parallel Implementation of GZip, is a fully functional replacement for gzip that takes advantage of multiple processors and multiple cores when compressing data.
PBZIP2 - pbzip2 is a parallel implementation of the bzip2 block-sorting file compressor that uses pthreads and achieves near-linear speedup on SMP machines. The output of this version is fully compatible with bzip2 v1.0.2 (ie: anything compressed with pbzip2 can be decompressed with bzip2).
LRZIP - A multithreaded compression program that can achieve very high compression ratios and speed when used with large files. It uses the combined compression algorithms of zpaq and lzma for maximum compression, lzo for maximum speed, and the long range redundancy reduction of rzip. It is designed to scale with increases with RAM size, improving compression further. A choice of either size or speed optimizations allows for either better compression than even lzma can provide, or better speed than gzip, but with bzip2 sized compression levels.
A small Compression Benchmark (Using the test Oli created):
ORIGINAL FILE SIZE - 100 MB
A small Compression Benchmark (Using a Text file):
ORIGINAL FILE SIZE - 70 KB Text File
In addition the nice summary above (thanks Luis), these days folks might also want to consider PIXZ, which according to it's README (Source: https://github.com/vasi/pixz -- I haven't verified the claims myself) has some advantages over PXZ.
In other words, PIXZ is supposedly more memory and disk efficient, and has an optional indexing feature that speeds up decompression of individual components of compressed tar files.
lzop may also be a viable option, although it's single-threaded.
It uses the very fast lempel-ziv-oberhumer compression algorithm which is 5-6 times faster than gzip in my observation.
Note: Although it's not multi-threaded yet, it will probably outperform pigz on 1-4 core systems. That's why I decided to post this even if it doesn't directly answer your question. Try it, it may solve your CPU bottleneck problem while using only one CPU and compressing a little worse. I found it often to be a better solution than, e.g pigz.