Re: RFC: New diff-delta.c implementation

From: Davide Libenzi <davidel@xmailserver.org>
Date: Apr 22, 2006, 20:36 UTC
Message-ID: <Pine.LNX.4.64.0604221333470.23166@alien.or.mcafeemobile.com>
In-Reply-To: <602974A9-09A3-46E9-92D6-D30728923C11@adacore.com>

On Fri, 21 Apr 2006, Geert Bosch wrote:

Show 25 quoted lines

> 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
>
> Please feel free to play around with this code, and give feedback.
> Keep in mind this wasn't originally written for GIT, and C is not
> my native language, so don't mind my formatting etc.

Geert, I saw you're using a shift of 55 bits, that gives an degree of the root polynomial of 63, that is not prime. Where did you get the root polynomial, and why you did not chose 61 as degree of the root? Just curious ...

- Davide