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@xxxxxxx). 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
-
: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html