Re: diff'ing files ...

From: Nicolas Pitre <nico@fluxnic.net>
Date: Jun 10, 2011, 20:37 UTC
Message-ID: <alpine.LFD.2.00.1106101612060.2142@xanadu.home>
In-Reply-To: <m34o3xesqn.fsf@localhost.localdomain>

On Fri, 10 Jun 2011, Jakub Narebski wrote:

Show 19 quoted lines

> Nicolas Pitre <nico@fluxnic.net> writes:
> > 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

No idea. But you can test that pretty easily if you wish. I would be interested in the results of course. Just do:

	make test-delta

and then, to compress something:

	./test-delta -d <input_file> <reference_file> <output_file>

Of course this will produce <output_file> which is only the bare binary diff annotation data against the reference file. In Git that output is also deflated with zlib, before it is stored in a pack. The other binary diff tools are usually doing a similar post-deflation pass as well.

It should be noted that the algorithm that Git uses won't produce the absolute smallest output. When I tried that, computation time went up of course, but surprizingly the final deflated result was slightly _larger_ as well, probably due to the fact that zlib was less efficient with the increased randomness in the tighter delta output to deflate.

Nicolas