John Goerzen: How To Think About Compression
and the case against bzip2
Compression is with us all the time. I want to talk about general-purpose lossless compression here.
There is a lot of agonizing over compression ratios: the size of output for various sizes of input. For some situations, this is of course the single most important factor. For instance, if you re Linus Torvalds putting your code out there for millions of people to download, the benefit of saving even a few percent of file size is well worth the cost of perhaps 50% worse compression performance. He compresses a source tarball once a month maybe, and we are all downloading it thousands of times a day.
On the other hand, when you re doing backups, the calculation is different. Your storage media costs money, but so does your CPU. If you have a large photo collection or edit digital video, you may create 50GB of new data in a day. If you use a compression algorithm that s too slow, your backup for one day may not complete before your backup for the next day starts. This is even more significant a problem when you consider enterprises backing up terabytes of data each day.
So I want to think of compression both in terms of resulting size and performance. Onward
Starting Point
I started by looking at the practical compression test, which has some very useful charts. He has charted savings vs. runtime for a number of different compressors, and with the range of different settings for each.
If you look at his first chart, you ll notice several interesting things:
I wanted to try something a bit more interesting. I made an uncompressed tar file of /usr on my workstation, which comes to 6GB of data. My /usr contains highly compressible data such as header files and source code, ELF binaries and libraries, already-compressed documentation files, small icons, and the like. It is a large, real-world mix of data. In fact, every compression comparison I saw was using data sets less than 1GB in size hardly representative of backup workloads. Let s start with the numbers:
In the MB saved column, higher numbers are better; in all other columns, lower numbers are better. I m using clock seconds here on a dual-core machine. The cost column is clock seconds per MB saved.
What does this tell us?
Like the other charts, the best area is the lower left, and worst is upper right. It s clear we have two outliers: gzip and bzip2. And a cluster of pretty similar performers.
This view somewhat magnifies the differences, though. Let s add cat to the mix:
And finally, look at the cost:
Conclusions
First off, the difference in time is far larger than the difference in space. We re talking a difference of 15% at the most in terms of space, but orders of magnitude for time.
I think this pretty definitively is a death knell for bzip2. lzma -1 can achieve better compression in significantly less time, and lzma -2 can achieve significantly better compression in a little less time.
pbzip2 can help even that out in terms of clock time on multicore machines, but 7za already has a parallel LZMA implementation, and it seems only a matter of time before /usr/bin/lzma gets it too. Also, if I were to chart CPU time, the numbers would be even less kind to pbzip2 than to bzip2.
bzip2 does have some interesting properties, such as resetting everything every 900K, which could provide marginally better safety than any other compressor here though I don t know if lzma provides similar properties, or could.
I think a strong argument remains that gzip is most suitable for backups in the general case. lzma -1 makes a good contender when space is at more of a premium. bzip2 doesn t seem to make a good contender at all now that we have lzma.
I have also made my spreadsheet (OpenOffice format) containing the raw numbers and charts available for those interested.
Update
Part 2 of this story is now available, which considers more compression tools, and looks at performance compressing files individually rather than the large tar file.
- gzip performance flattens at about -5 or -6, right where the manpage tells us it will, and in line with its defaults.
- 7za -2 (the LZMA algorithm used in 7-Zip and p7zip) is both faster and smaller than any possible bzip2 combination. 7za -3 gets much slower.
- bzip2 s performance is more tightly clustered than the others, both in terms of speed and space. bzip2 -3 is about the same speed as -1, but gains some space.
I wanted to try something a bit more interesting. I made an uncompressed tar file of /usr on my workstation, which comes to 6GB of data. My /usr contains highly compressible data such as header files and source code, ELF binaries and libraries, already-compressed documentation files, small icons, and the like. It is a large, real-world mix of data. In fact, every compression comparison I saw was using data sets less than 1GB in size hardly representative of backup workloads. Let s start with the numbers:
| Tool | MB saved | Space vs. gzip | Time vs. gzip | Cost |
|---|---|---|---|---|
| gzip | 3398 | 100.00% | 100.00% | 0.15 |
| bzip2 | 3590 | 92.91% | 333.05% | 0.48 |
| pbzip2 | 3587 | 92.99% | 183.77% | 0.26 |
| lzma -1 | 3641 | 91.01% | 195.58% | 0.28 |
| lzma -2 | 3783 | 85.76% | 273.83% | 0.37 |
- bzip2 can do roughly 7% better than gzip, at a cost of a compression time more than 3 times as long.
- lzma -1 compresses better than bzip2 -9 in less than twice the time of gzip. That is, it is significantly faster and marginally smaller than bzip2.
- lzma -2 is significantly smaller and still somewhat faster than bzip2.
- pbzip2 achieves better wall clock performance, though not better CPU time performance, than bzip2 though even then, it is only marginally better than lzma -1 on a dual-core machine.
Like the other charts, the best area is the lower left, and worst is upper right. It s clear we have two outliers: gzip and bzip2. And a cluster of pretty similar performers.
This view somewhat magnifies the differences, though. Let s add cat to the mix:
And finally, look at the cost:
Conclusions
First off, the difference in time is far larger than the difference in space. We re talking a difference of 15% at the most in terms of space, but orders of magnitude for time.
I think this pretty definitively is a death knell for bzip2. lzma -1 can achieve better compression in significantly less time, and lzma -2 can achieve significantly better compression in a little less time.
pbzip2 can help even that out in terms of clock time on multicore machines, but 7za already has a parallel LZMA implementation, and it seems only a matter of time before /usr/bin/lzma gets it too. Also, if I were to chart CPU time, the numbers would be even less kind to pbzip2 than to bzip2.
bzip2 does have some interesting properties, such as resetting everything every 900K, which could provide marginally better safety than any other compressor here though I don t know if lzma provides similar properties, or could.
I think a strong argument remains that gzip is most suitable for backups in the general case. lzma -1 makes a good contender when space is at more of a premium. bzip2 doesn t seem to make a good contender at all now that we have lzma.
I have also made my spreadsheet (OpenOffice format) containing the raw numbers and charts available for those interested.
Update
Part 2 of this story is now available, which considers more compression tools, and looks at performance compressing files individually rather than the large tar file.
I took the package of blackberries from the freezer, where it had sat,
neglected since I picked them from my fecund vines in August. They had
some frost on top; it didn't seem that the wait could have improved them.
But, I figured, let's do this right. No store-bought pie crust, made my
own with lots of love, and no little trepidation, since pie crust is not
my strong suite. Put it back in the fridge to rest as I melted the
frozen berries. Added some honey, then worried I'd sweetened it too much.
Seemed too runny, so added some flour. Spent what seemed a long
time criss-crossing strips of the pastry on top. Which, now that I
look at it, doesn't seem to be quite the way it's typically done, but
whatever.
45 minutes later, it came out, and bliss, it's the most perfect pie I've
ever made. Crust acceptably flaky, berries just the right mix of tart and
sweet. But mostly, it tastes of summer and care, and the wait seems to have
been worth it.
So that's my 
Alright, Debian GNU/Linux 5.0 AKA as Lenny 
What does the new stable release bring for system administrators? I ll give an overview what news you might expect when upgrading from Debian GNU/Linux 4.0, codename Etch (released on 8th April 2007) to the current version Debian GNU/Linux 5.0, codename 
This weekend I have mostly been investigating Common Lisp.
If you're new to the environment then you may get started via a simple:
So in 2009 I've started using Social Media Accounts alot more like Facebook, Twitter,Wordpress ( self hosted ), and plan to use more as time goes on and I discover new services and new services are introduced.
<rant>
One of the issues I've noticed is most "tweet flows" want you to update your status across multiple services, like your IM status would be the same as your Twitter status and again the same as your Facebook status and so on. See the problem with this is not all "status" messages on Social Media sites are used for the same purpose , e.g. the Facebook status allows comments and the Tweet allows replies and RT's ( Re-Tweets ) and IM status doesn't allow any feedback at all, at least not publicly. An posting to both identi.ca and twitter causes replies and such to be checked on both.
Where is our "Digital Convergence" / Digital Universe for Social Media ?
How do any of you keep all the different forms of social media updated ( an relevant ) to the media its self, e.g. not posting the wrong status to the wrong service and not using 100000(.5) web interfaces constantly.
</rant>
Well, no, neither FOSDEM nor Debian are dead. But FOSDEM '09
is gone, over, and dealt with.
It was a breeze, for the most part. I'm still not very happy
with the booth; that needs to be done better next year. Help and
suggestions in that area are more than welcome.
One thing that more than deserves a follow-up is 
No, Debian folks, not our former DPL...:-)
My, by far, favourite skipper in the greatest race around the world (alone on a 60-feet boat without assistance), 
After the Google employee went back to New Jersey with Jarjar, I
somehow ended up paying $9 for a good slice of pizza and what
is potentially the second-most-disgusting piece of vegan pizza
I have ever encountered.
Life sometimes has extreme ways of waking people up and making them realize what matters for them. I'm going through such a phase right now in my romantic life. I won't discuss what happened here, but suffice it to say that I haven't felt so depressed in a long, long, long, long time.
The good news is that life has proven to me once again how having good friends who truly care for me makes a whole world of difference. The big slap in the face that life gave me over these last few days was a harsh lesson, but I think that it was worth it. Of course, it helps that people like Gilles, Jaana, Henni, Pia, Linda, Arno and Sailesh beleived in me enough to support me through this rough spot in my life. Although their advices were vastly different, they all pointed in a very positive direction and gave me the strenght to carry on.
I also must thank my beloved Anastassija; what she did was cruel beyond beleif and yet, if her few SMS from the last 24 hours are any indication, there's still hope after the storm. I'll be seeing her tonight again, after a few days of separation and I prepared her a truly romantic evening. It ain't much, but I hope that it truly succeeds in bringing the point accross that Love is stronger than everything and that even the unforgivable can be forgiven, over time, if everyone involved has enough faith in each other's future as a couple.
Tonight, I truly could use the prayers of a million voices to support me and Anastassija in this difficult time. Life slapped me hard and I got the message... I think... and whatever happens after tonight, I need to know that I gave it my best shot and that, whatever her and I decide, Life can only take a turn for the better from now on.
In the Openmoko community, a lot of programs are written in python and use services provided over D-Bus. But I m under the impression that not enough programmers consider that D-Bus is a remote protocol, and the other side might fail to respond any time. The code then works find if nothing goes wrong, but does not handle problems well. Understandably, it is hard to get this error checking right if you can t really test it, as usually the D-Bus services do not fail. This is particularly annoying on a phone, because it might just be the program responsible for popping up the on screen keyboard that just failed.Therefore I started to write a little