Re: diff'ing files ...

From: Jakub Narebski <jnareb@gmail.com>
Date: Jun 10, 2011, 13:12 UTC
Message-ID: <m34o3xesqn.fsf@localhost.localdomain>
In-Reply-To: <alpine.LFD.2.00.1106092145390.2142@xanadu.home>

Nicolas Pitre <nico@fluxnic.net> writes:

Show 6 quoted lines

> On Tue, 7 Jun 2011, Jeff King wrote:
> > On Tue, Jun 07, 2011 at 10:12:35PM +0000, Albretch Mueller wrote:
> > 
> > > > ... binary diffs, though I don't know offhand the details of the algorithm.
> > > ~
> > >  this is the part that I need ;-)

[...]

Show 20 quoted lines

> > According to the xdiff page linked:
> > 
> >   For binary files, LibXDiff implements both (with some modification)
> >   the algorithm described in File System Support for Delta Compression
> >   by Joshua P.  MacDonald, and the algorithm described in Fingerprinting
> >   By Random Polynomials by Michael O. Rabin.
> > 
> > Nicolas (cc'd) might be able to say what, if any, substantive changes
> > were made from those works.
> 
> The libxdiff code was pretty generic so to be highly portable and usable 
> for many application types.  What I did is to get rid of everything that 
> git strictly didn't need in order to make the code as simple as 
> possible, and most importantly as fast as possible. [...]
> 
> And then further modifications were made to avoid pathological corner 
> cases which were taking too much time for little gain in the Git 
> context.
> 
> I also changed the output encoding to make it tighter.

Nicolas, do you know how binary diff used by git compares with respect to performance and compression with other binary diff algorithms:

  * original LibXDiff
  * bsdiff
  * xdelta (vcdif algorithm)
  * vbindiff

-- 
Jakub Narebski
Poland
ShadeHawk on #git