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
Geert, the code needs some works IMO ;), but otherwise very lever idea to
use Rabin's polynomials and impressive results!
- 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