[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Whither delta combiner

From: Greg Hudson <ghudson_at_MIT.EDU>
Date: 2002-02-08 23:50:45 CET

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

This is an archived mail posted to the Subversion Dev mailing list.