You don't mention ratios. Better compression becomes asymptotically/exponentially harder when it gets close to the optimal code size.

Thanks for the shout out. BTW Matt's benchmarks are for all major compression engines, not only bzip2.