RFC: New diff-delta.c implementation
- From
- Geert Bosch <bosch@adacore.com>
- Date
- Apr 21, 2006, 21:16 UTC
- Message-ID
- <602974A9-09A3-46E9-92D6-D30728923C11@adacore.com>
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