[RFC] Multi-parent diffs

[Robert Collins]

On Tue, 2007-04-10 at 13:10 +1000, Martin Pool wrote:
> > I've drafted a spec for a new diff representation that I think we should
> > consider adopting:
> >
> > http://bazaar-vcs.org/DraftSpecs/MultiparentDiffs
> 
> I can see how diffing against all parents would produce a smaller diff
> in some cases, particularly when we're diffing the annotations too.
> 
> However, to extract a text stored this way would require first
> building all of the parents, and that might be substantially more
> work.  So maybe it would be interesting to prototype enough of this to
> assess what effect it has on size and speed.

Well a naive implementation sure, but its only strictly necessary to
access any delta in the files history once; the size of each delta will
be commensurately smaller so the total data to be considered to
reconstruct any single text should be roughly the same; to reconstruct a
sequence (such as iter_inventories does), the total data access should
be lower (by the amount of space saved).

We've recently discussed smart text building routines that would allow
multi-parent diffs in a straight forward manner; a recursive routine
would want to stop at graph dominators, or cache results or some such.
An iterative routine could be sure to always pop off the next revision
to get lines from in a topologically sorted manner, which the knit index
already is - so this doesn't need to perform an additional topo sort.

I agree that it would be interesting to have a benchtest of this, to be
able to compare it with our current performance in both space and time.

-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/20070410/fe35d5d2/attachment.pgp