[Monotone-devel] Re: moving forward on delta storage

[Lapo Luchini]

Nathaniel Smith <njs <at> pobox.com> writes:

> Maybe.  We can always do that later too, though -- holding up a fix
> for initial pull speed in order to get minor improvements in database
> size is probably not a good idea.

That's a very good point.

> I guess it's important to test these things on real data.  Matt
> Mackall (the main mercurial guy) says that in the benchmarks he ran
> when starting out, recursive longest-common-substring matching gave
> better results than xdelta on source files.
> 
> Is there any documentation on the actual algorithm used available?
> One very important question in particular is whether it outputs
> copy/insert deltas like xdelta does, or something else.

The website only states to use "suffix sorting (specifically, Larsson and
Sadakane's qsufsort)"... reading the paper should enlighten, I guess.
I plan to do that sometime soon.
http://www.cs.lth.se/Research/Algorithms/Papers/jesper5.ps

    Lapo