[RFC][PATCH] Speed improvement on the Weave.join() function

[John Arbash Meinel]

Goffredo Baroncelli wrote:
> Hi all,
> 
> the patch below contains an optimization for the function
> Wave.join( ), so this function doesn't perform unnecessary content expansion if the
> revision to be merged is already present. For example if you have to merge your
> last 30 revisions of the bzr.dev main branch you don't have to expand the text
> of all the ~2900 revisions present in the inventory weave. The gain is showed in the 
> example below, where we merge an inventory of 2094 revs with one of 2904
> 

Thanks for the optimization. It seems generally worthwile.

I honestly think another optimization is available, which could merge
revisions into a weave file, without unpacking the raw text, and merging
it again (by diffing again).

For a new revision, it's text has to either be new lines, or a subset of
its parents lines. It is not possible to merge lines with other texts
that are not in the ancestry.

Which means that if we already have all of the ancestry for a text, then
we should be able to just pull in its changes. The trick is to get the
lines moved properly relative to the parents.

The current "weave.add()" code extracts the ancestors, so that it can
get the "basis_lineno" which will tell it where to insert.

Now, with the current implementation of weaves, it may not be any
cheaper to figure out which lines map together between two weave files,
though it would mean only doing a 'diff' once, instead of once per revision.

Though, I can't say it will save a lot versus getting append-only
written, so you can do a lot less work.
John
=:->
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 256 bytes
Desc: OpenPGP digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20051210/791beceb/attachment.pgp