News for hackers. Stuff that matters.
Re:Saving Data: Reducing the Size of App Updates by 65% by hawski on Wednesday December 07, 2016 @07:08AM (#13121974)
Could rsync algorithm be used to prepare binary diffs? How would it compare to bsdiff?

EDIT:

Thanks for the downvote.

There is a tool using rsync algorithm for binary diffs. It's called rdiff [1]. I found Master's thesis Binary Differencing for Media Files by Vladimir Komsiyski [2]. What I take from there is that rdiff is fast, but bsdiff produces smaller patches.

Excerpts:

> bsdiff is marginally better than xdelta as far as compression is concerned. rdiff and especially edelta generate much larger patches. The upload gains from the viewpoints of the server are exactly the same as the compression rates and the saved disk space is proportional to it. For example, an expected number of versions per file of 3.7 (which is the case in Dataset A) and differencing with xdelta result in 70% less required disk space.

> As expected, bsdiff ’s slow differencing time results in 3 times slower upload from the viewpoint of the client when compared to the server’s experienced time. Apart from that, the added time due to the differencing is smaller compared to the transfer of the produced patch and lead to up to 21 times faster transfer than when no differencing is done. Even the worst performing tool edelta reaches a speed-up with a factor of 3. xdelta, showing the best results out of the four tools, achieves a 21x speedup when transferring a file to the server. The second best tool, bsdiff , is only 9 times faster. However, its coefficient may dramatically increase with increasing the file size (Adobe Photoshop files) because of the non-linear runtime of this tool. edelta is severely outperformed by all other tools. The fastest tool rdiff loses its lead due to the bigger patches it produces.

> For Adobe Documents (and most likely other image editing software files) the binary differencing tool xdelta shows the best run-time for the compression it achieves. rdiff is faster, but its patches are bigger. bsdiff shows better compression, but its non-linear runtime makes it unusable for files of this size. The benefits of xdelta are considerable - decrease of the file size with more than 96% for Adobe InDesign files, causing up to 30 times faster file transfer. Adobe Photoshop documents also show substantial gain despite their much larger size.

[1] https://en.wikipedia.org/wiki/Rsync#Variations https://linux.die.net/man/1/rdiff

[2] http://scriptiesonline.uba.uva.nl/document/490827

There are no comments on this comment yet.