Re: RFC: New diff-delta.c implementation

[Davide Libenzi <davidel@xmailserver.org>]

On Fri, 21 Apr 2006, Geert Bosch wrote:

> I wrote a new binary differencing algorithm that is both faster
> and generates smaller deltas than the current implementation.
> The format is compatible with that used by patch-delta, so
> it should be easy to integrate.
>
> Originally, I wrote this for the GDIFF format, see 
> http://www.w3.org/TR/NOTE-gdiff-19970901.
> The adaptation for GIT format was relatively simple, but is not thoroughly 
> tested.
> The code is not derived from libxdiff, but uses the rabin_slide function 
> written
> by David Mazieres (dm@uun.org). Also the tables are generated using his code.
> Finally, this was developed on Darwin, and not a Linux system, so some 
> changes may be needed.
>
> Initial testing seems quite positive, take for example git-1.2.5.tar vs 
> git-1.2.6.tar
> on my PowerBook (both with -O2 -DNDEBUG):
>
> current: 2.281s, patch size 36563
> new    : 0.109s, patch size 16199

Geert, the code needs some works IMO ;), but otherwise very lever idea to 
use Rabin's polynomials and impressive results!



- Davide