On Sun, 2003-07-06 at 00:09, Brad Appleton wrote:
> > using the skip-delta technique to ensure that...
> Is this the same thing as the interleaved (or "inline", or sometimes
> called "interlaced") delta approach that is used by ClearCase and SCCS
> (among others?). It works basically like a great big bunch of
> "#ifdefs" for each delta. If not, can you say more about how it
> differs from the inline delta approach?
It's not a weave, no. A weave doesn't scale particularly well when
there are many revisions of a file.
I'll reiterate the new idea. For any n>0, let D(n) be n-(1<<m) where
(1<<m) is the least significant bit set in n. (D(1) is 0, D(8) is 8,
D(13) is 12, D(20) is 16.) We store rev 0 of a file as plaintext (or
self-compressed), and rev n of a file as a delta against rev D(n). The
first 16 revs of a file would look like:
0 <- 1 2 <- 3 4 <- 5 6 <- 7 8 <- 9 10 <- 11 12 <- 13 14 <- 15
0 <---- 2 4 <---- 6 8 <----- 10 12 <----- 14
0 <------------ 4 8 <--------------- 12
0 <---------------------------- 8
So to fetch the contents of rev 15 of the file, you'd see that rev 15 is
a delta against rev 14, which is a delta against rev 12, which is a
delta against rev 8, which is a delta against rev 0. You combine those
four deltas using the delta combiner, apply them to rev 0, and get your
result.
(What we do right now is similar to the above, but in reverse, so that
older revs are expressed as deltas against newer revs. The last section
of http://web.mit.edu/ghudson/thoughts/file-versioning contains a
description of skip-deltas as we use them today.)
> I think the inline approach makes it easier than the reverse-delta (or
> RCS style with reverse-deltas on the main trunk and forward-delta on
> branches) when it comes down to doing merge-algebra in an intelligent
> fashion.
How?
> Once upon a time, back in the mid-80s I worked on a commercial VC tool
> called SVM (Seidl Version Manager). Where were one of the few VC tools
> for the PC (other main ones being PVCS, TLIB, and a relative newcomer
> named MKS ;-). Ours was the only one of that bunch that used
> forward-deltas. We overcame the performance issue by keeping a cache
> of the most recent N versions in a cache area (where N could be
> configured per system, as could the set of files for which to keep the
> cache - if I recall correctly anyway :)
Caching fails to ensure guaranteed acceptable performance, which I think
is an important property of an FS back end.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sun Jul 6 07:02:11 2003