Re: RFC: New diff-delta.c implementation

From: Geert Bosch <bosch@adacore.com>
Date: Apr 24, 2006, 19:23 UTC
Message-ID: <0C184231-78A3-4517-89B2-2AE5C2CC9752@adacore.com>
In-Reply-To: <Pine.LNX.4.64.0604241155000.18685@alien.or.mcafeemobile.com>

On Apr 24, 2006, at 15:10, Davide Libenzi wrote:

Show 11 quoted lines

> Right, but you are looking at highest equal-probability  
> distribution over your hash buckets ;)
> Anyway, thanks for bringing Rabin's polynomial fingerprint up from  
> the forgotten lands. Performance and delta size are quite amazing,  
> and I decided to add Rabin's delta to libxdiff.
> I hacked some code (attached) to generate T/U tables. Since  
> libxdiff must be portable everywhere, even on system w/out 64 bits  
> support, I use xrabin to create both 64 bits tables (poly degree  
> 61) and 32 bits tables (poly degree 31), and store them in a .c  
> file letting the build environment to pick the correct one for the  
> platform.

It might actually make sense to use the 32-bit code for GIT as well, since it turns out that on the typical small source files with few differences, the full 64-bit Rabin is a problem for performance.

When diffing large files (my main interest), this is more than offset by the better hash quality. For tiny files with few changes it appears to be overkill...

   -Geert