[Monotone-devel] Re: moving forward on delta storage

[Bruce Stephens]

Nathaniel Smith <address@hidden> writes:

> On Mon, Feb 20, 2006 at 09:15:22AM +0000, Lapo Luchini wrote:

[...]

>> http://www.daemonology.net/bsdiff/
>> regarding size: "bsdiff routinely produces binary patches 50-80% smaller than
>> those produced by Xdelta"
>
> However, it also attributes this partly to "taking advantage of how
> executable files change".
>
> I guess it's important to test these things on real data.  Matt
> Mackall (the main mercurial guy) says that in the benchmarks he ran
> when starting out, recursive longest-common-substring matching gave
> better results than xdelta on source files.

Yeah, and presumably mercurial, git, etc., are likely to have tested
on the kinds of data that monotone's likely to be used on.  IIRC,
performance of this kind of thing varies wildly depending on the
nature of the data.  

git uses libxdiff <http://www.xmailserver.org/xdiff-lib.html>, or at
least code taken from it.  (The idea of using two algorithms (one for
text, one for binary) seems interesting, presuming that a text
algorithm performs much better than the binary one; I guess it's also
interesting if you can use the text diffs in some way (for diff,
annotate, etc.), but that would probably add much too much complexity
to be worthwhile.  I haven't looked to see what code git uses for
delta storage---quite possibly just the xdelta part.)

[...]