[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Poole
Subject: Re: [Gnu-arch-users] a brief note on "delta compression"
Date: Mon, 03 May 2004 17:17:00 -0400
User-agent: Gnus/5.1006 (Gnus v5.10.6) XEmacs/21.4 (Security Through Obscurity, linux)

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]