xdelta multi-parent hack ?

[Robert Collins]

On Fri, 2007-06-22 at 12:47 -0500, John Arbash Meinel wrote:
> 
> The above data points also give us some ideas of what trade offs we
> might want to implement. I'm also skipping the "linear" and "by size"
> measurements, but I can generate them on request. And Martin mentioned
> another one which was "All relative to a single fulltext (no chain)".
> 
> There is also the performance impact for creating these deltas. As
> near
> as I can tell, it seems to be about 50%. So if it took 2s before, it
> now
> takes 3s. (Or if it took 3s, it now takes 4.5s)

Very cool - thank you for looking at this.

I have another thought, which is that we could consider generating a
single recipe to reconstruct a revision rather than the recursive
recipes we're looking at today.

E.g. (using a single parent example) rather than:
text1 + delta2 = text2
text2 + delta3 = text3
...            = TextIRequested

If we assume everything is stored as deltas, then we can reconstruct a
text by listing the delta elements that make it up:
rev1 bytes 40-50
rev2 bytes 20-70
rev3 bytes 200-201
...

e.g. a VCDIFF output instruction using all the previous *new text*
introduced by versions that have text in common.

The thought here is about latency - rather than having to recurse and
recreate many interim versions, why not just specify the versions and
content needed straight off the bat giving us a complete list of needed
inputs in one round trip.

There are some obvious variations to this such as using a hash swarm to
manage the reconstruction document so it doesn't blow out in size.

-Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070625/f0c3235e/attachment.pgp