On Fri, 2002-02-08 at 23:29, Karl Fogel wrote:
> Both proposals trade delta space for faster retrieval of old
> revisions; haven't done a formal proof, but I'm pretty sure both
> methods end up being exactly the same tradeoff, and I think it's about
> the same as the skiplist tradeoff, too. (I haven't thought as much
> about the skiplists, so this is just an off-the-cuff reaction.)
I don't think so. Let's say we have a node with N node-revisions (no
branching), whose average plaintext size is S (after compression), and
for which the average delta size between two adjacent revisions is D.
For simplicity, we'll assume that a delta between revs X and Y is
D*|X-Y|, which is true for something like a ChangeLog file which mostly
just has data added to it in each rev. For such a file, S should grow
as ND.
Let's assume we want at most lg(N) deltas to get to any revision, since
that's what the simplest case of skiplist deltas gets us. Then, the
space costs are:
Checkpoint plaintexts: O(DN^2/lg(N))
Re-deltifying: O(DN^2/lg(N))
Skiplist deltas: O(DNlg(N))
To plug in some vaguely believable numbers, let's say we have a
ChangeLog file with 8192 revisions, an average delta size of 256 bytes,
and an average plaintext size of one meg (which is 8192*256/2).
Plaintext deltas or re-deltifying would cost on the order of 630MB,
while skiplist deltas would cost on the order of 26MB or so.
For those with both skepticism and patience, here is how I get those
orders of magnitude:
Checkpoint plaintexts: We need N/lg(N) plaintexts, of average size S,
plus N-N/lg(N) adjacent-revision deltas. That's SN/lg(N) +
D(N-N/lg(N)), the second term of which is insignificant. Since S grows
as ND, we get DN^2/lg(N).
Re-deltifying: Re-deltifying is fundamentally the same as plaintext
deltas for a file like this; we just diff every lg(N) revisions against
the head instead of against the empty rev 0, effectively. Same order of
growth.
Skiplist deltas: The bottom row of N adjacent-rev deltas takes D*N
space, of course. The next row up also takes D*N space; there are half
as many deltas but they are each twice as big. And so on; since there
are lg(N) rows, we need DNlg(N) space.
Some might wonder about files which have lots of revs but don't behave
like ChangeLog files, such that a delta across many revs is only about
as big as a delta across one rev. In this case, checkpoint plaintexts
will do terribly (order SN/lg(N)), redeltification against the head will
do very well (order DN), and skiplist deltas will do almost as well
(order DN with a larger constant).
---------------------------------------------------------------------
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:06 2006