Re: Delta directions (was Re: delta combiner sloooooooowwwwww)

On Sat, 2005-02-12 at 14:18, Branko Èibej wrote:
> Like I said on IRC, it's because I was wrong... the vdelta would be the
> first in the combination chain, and it's full of target copies, so it
> triggers the O(n^2) in the combiner from the start.

Well, we can get around this. With Daniel's patch, an FSFS file history
looks like:

  xdelta --> xdelta --> xdelta --> vdelta --> empty

If we apply all the xdeltas to the vdeltas, we lose. But if we instead
apply the vdelta to the empty stream and combine the rest of the deltas,
now the history looks like:

  xdelta --> xdelta --> xdelta --> <constructed text>

and we win.

FSFS already has code to deal with the "delta --> delta --> delta -->
plain" case, although it (a) doesn't get used in practice, and (b) isn't
quite generic enough for this purpose. But it should be pretty simple
to fix it up. Then we can get the full speed benefit of the xdelta
changeover without sacrificing plaintext compression, and without a
schema change.

(I already presented this idea on IRC, but since I'm not going to
implement it myself in the near future, I thought I should note it on
the list.)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Feb 12 23:36:10 2005