Nearly a decade ago, I spent some time learning about delta-compression tools and writing a test-harness to compare them. Recently, some of those tools were updated so I decided to update my tests and run them again.
Delta compression is a form of file compression that describes the differences (traditionally abbreviated as “d”, or the Greek equivalent, “delta”) between two files. If a person already has a copy of version 1 of a file, and you want to give them a copy of version 2, it can be much more efficient to just send them the differences from version 1 to version 2, rather than the whole thing.
In my tests, I used the following delta-compression tools:
|beat||BPS||Suffix arrays||The latest tool from byuu, the author of bsnes.|
|bsdiff||Custom||Suffix arrays||Used by Firefox to distribute updates.|
|bps||BPS||brute force||The previous tool from byuu, no longer supported.|
|Flips||BPS||Suffix arrays||Also supports the more primitive IPS format.|
|python-bps||BPS||hashing||My own attempt at writing a BPS comparison tool.|
|xdelta3||VCDIFF||Rolling hashes||The most popular tool for delta-compression.|
I started writing python-bps to experiment with different delta-compression algorithms, and wrote the test-harness so I could easily compare my own code to others’. The new entries in the 2019 edition are beat and Flips; the others are the same as before.
I collected various pairs of slightly modified files, used each tool to compare the source and target, and recorded the size of the resulting patch file.
/dev/urandomas the source, and generates the target by randomly copy/pasting chunks of it.
In addition, many tests have a “rev” variant, which reverses the source and target files.
In case you want to run tests for yourself, or even submit your own, I’ve published my test harness as a git repo. Note that for legal reasons, the repo does not contain every testcase listed above, just the ones that can be legally distributed.
The test harness runs every tool for every test, and produces a tab-separated values file listing the size of every patch, and the tool and test involved. This file can be loaded into your favourite spreadsheet or database tool so you can analyse it as you like.
Let’s start with the total size of all the patches generated by each tool:
Note that xdelta appears twice in the table. Unlike other formats, the VCDIFF format supports optional internal compression, and xdelta allows the amount of compression to be tweaked. “xdelta3 -0” disables the internal compression, while “xdelta3 -9” compresses as much as possible. Clearly this helps xdelta3 quite a bit, so let’s run the patches through gzip to see if that changes anything.
“xdelta3 -9” doesn’t change much at all, as expected since it’s already compressed.
“bsdiff” also doesn’t change much, since it is also already compressed. Unlike xdelta3, compression isn’t optional for bsdiff, so there’s no compression-disabled variant.
It looks like all the BPS-based tools (flips, beat, byuu-bps and python-bps) aren’t as efficient as they could be, since gzip shaves about a megabyte off the total for each one.
Weirdly, the uncompressed “xdelta3 -0” gets bigger. I guess the delta-compression information is stored in a way that naive gzip can’t compress, which is why the format supports internal compression.
Some tests have “forwards” and “reverse” variants, where the “reverse” patch just undoes the effect of the “forwards” patch. Are some tools better at one than the other?
The total size of reverse-patches is much smaller than forward patches, because there’s not as many reverse patches in the corpus. The relative performance of each tool is quite consistent, except that xdelta3 -0 is much better in reverse than forwards, while xdelta3 -9 remains the same. Perhaps that’s because forward patchse add data that needs to be inserted into the file, which can benefit from compression, while reverse patches tend to remove data, and therefore do not benefit as much from compression.
Now that we’ve establish trends across our entire corpus, let’s look at the different use-cases for for delta compression. Do different tools behave differently for the “recompiled binary” use-case?
bsdiff is the undisputed champion of this category, which is unsurprising since it was specifically designed for such things.
How about hand-modified binaries?
bsdiff falls back into the middle of the pack for hand-modified binaries. Somewhat bizarrely, the uncompressed xdelta3 -0 is smaller than every other tool, including the compressed xdelta3 -9. However, all the tools are pretty closely-matched in this category, so it might not be a significant difference.
The last major category is “hand modified sources”:
For mostly-text data like source-code, bsdiff is again mediocre, and Flips and beat make a good showing. xdelta3 -9 makes the best showing, possibly because the new data added into the target file is text, and therefore compresses well.
If you think about it, traditional file-compression is just a special case of delta-compression where the source file is always empty, so any delta-compression tool should be usable as a regular file-compression tool. Just for kicks, let’s try using our delta-compression tools to compresst the bsnes v072 binary from the “bsnes” test:
For comparison, the uncompressed file is 1.1MiB, and gzip -9 compresses it to ~400KiB. Surprisingly, xdelta3 beats everything else, including gzip. Even more surprisingly, xdelta3 -0 beats xdelta3 -9. I could not begin to imagine how.
Total patch size is an important measurement for any kind of file compression, but not the only one. If a particular tool can generate super-tightly compressed files, but requires a gigabyte of RAM for each kilobyte of the source file, or takes days to run, it may not be worth the effort.
Unfortunately, my test harness does not record elapsed time or memory usage, so I can’t provide those numbers here. However, while running the tests I observed the following:
From the numbers we’ve seen, we can draw a few conclusions:
If you’re developing software and want to distribute updates to your users, bsdiff is the only game in town.
If you’re hand-modifying binaries or source less than a few hundred megabytes in size, Flips produces great patches, and the BPS file-format is the simplest to support in your patcher.
If you’re hand-modifying binaries like CD or DVD images, you’ll probably want xdelta3.