[MERGE] more common-ancestor performance improvements.

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:
> This patch both improves the speed of merge-base selection, and improves
> its behavior with criss-cross merges.

This patch builds on my previous patch.  It changes the
Graph.minimal_common method to avoid traversing the whole graph.

Instead, it scales with:

1. the number of uncommon ancestors
2. the lengths of the shortest paths between border common ancestors

This improves performance somewhat on a local machine, and should have
more dramatic benefits for remote operations, when retrieving a complete
graph can be slow, or when the ancestry is very large.

Benchmarks:
Here are the times for "bzr merge" merging bzr.dev into bzr.ab:

Original:
real    0m12.685s
user    0m12.050s
sys     0m0.315s)

Patch #1
real    0m4.692s
user    0m4.210s
sys     0m0.213s

Current patch
real    0m4.248s
user    0m3.907s
sys     0m0.179s

(The original time was:
real    0m12.685s
user    0m12.050s
sys     0m0.315s)

The find-merge-base command provides a more targeted benchmark:
Original:
real    0m10.505s
user    0m10.060s
sys     0m0.253s

First patch:
real    0m2.204s
user    0m2.044s
sys     0m0.097s

Current patch:
real    0m1.819s
user    0m1.654s
sys     0m0.097s

I've attached both a merge directive, and a patch showing what's changed
since the last patch.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGWbie0F+nu1YWqI0RAjPOAJ9yTBkou4O5YUErlYHDSQhvpe1eqwCeJvvY
oqpTANNk0nXy3z0h9bSgeTc=
=XgGl
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-walker2.patch
Type: text/x-patch
Size: 90742 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070527/afa73c07/attachment-0002.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-walker2b.patch
Type: text/x-patch
Size: 7072 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070527/afa73c07/attachment-0003.bin