On Fri, 2002-02-08 at 17:47, Karl Fogel wrote:
> Greg Hudson <ghudson@MIT.EDU> writes:
> > Another option is to apply the deltas streamily and try to keep the
> > number of deltas small, by using some technique like skiplist deltas.
> > If we did that, then even if there are 1024 revs of a file, there should
> > be no more than about 20 deltas between any two revs, for at most 7.5MB
> > of space required. (Which is still kind of big... we could cut it down
> > to 2*windowsize by using a specialized chain-delta applicator which
> > shares the destination view buffer of one delta and the source view
> > buffer of the next. That might be over-optimizing, though.)
>
> Hmmm... Could you describe this in more detail?
Skiplist deltas, you mean? I'll give a simple description. Let's say
we have a node with eight node-revisions (and no branching), and we only
want to have one plaintext of that file--the most recent. Right now, I
assume the node looks something like this (where "1" should really be
"N.1" where N is the node number, but I'll abbreviate):
1 <-- 2 <-- 3 <-- 4 <-- 5 <-- 6 <-- 7 <-- 8
To get the plaintext of rev 1, we need to apply seven deltas. With
skiplist deltas, the node would look like:
4 <-------------------- 8
2 <-------- 4 <-------- 6 <-------- 8
1 <-- 2 <-- 3 <-- 4 <-- 5 <-- 6 <-- 7 <-- 8
Now to get the plaintext of rev 1, we need to apply only three deltas (8
-> 4 -> 2 -> 1), and there shouldn't be more than five deltas between
any two revs (no more than four, looks like).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Oct 21 14:37:05 2006