Re: [Gnu-arch-users] a brief note on "delta compression"

[Michael Poole]

James Blackwell writes:

> The lower we set X, the less point there is in bothering to do CD in the
> first place. The higher we set X, the more useful the extra stored CD,
> but the less likely that we'll actually be able to use it.

I believe this is what skip lists are designed to work around.
Someone (probably several someones, but I do not remember names) has
already suggested using skip lists of deltas.

In addition to human hinting about what deltas are interesting to
cache, I think doing something like that would be a good tradeoff
between what is useful and what is quick.

For example, for patch-N, if N is a power of two, keep a 1-CD and a
(N/2)-CD; otherwise, keep a 1-CD and a (least-set-bit-of-N)-CD.  This
allows for binary search to find any revision.  You could also base
the calculations relative to the most recent cachedrev or the most
recent hinted CD participant.

Michael Poole