On 9 Feb 2002, Greg Hudson wrote:
> 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))
>
Skiplist deltas are, in fact, the logical extension of what i just
described to Branko.
In addition, the skiplist deltas are only twice as big as you
increase in level, in the absolute worst case.
The deltas could quite possibly intersect (IE you rewrote the same routine
later or something), and in that case, they wouldn't be twice as big.
The deltas on the next level up are, in reality, the size
|(a - b) U (b - a)|
--Dan
---------------------------------------------------------------------
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