[RFC] ancestry cache

[Aaron Bentley]

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

Hi all,

I've been fiddling with progress bars for merge application, and it
turns out we spend a lot of our time selecting a merge base.  What
surprised me is that the largest part of this is the time generating a
graph of common ancestors.

So I've implemented a prototype ancestry cache.  Patch attached.  Does
this seem worth pursuing?

I benchmarked the results.  They weren't as good as I hoped, but they do
improve things some.  I'm counting real time, because this is an
IO-limited operation.

Without the patch, the average of 4 runs was 7.45 seconds
With patch, the average of 4 runs was 6.45.  So the patch improves
overall merge performance by ~ 15%.  Perhaps more, if you assume cold cache.

We can probably speed the common ancestor detection by up to 50% by
using a somewhat more complicated algorithm.

This data is optional cache data, so it's compatible with existing
branch formats, and doesn't need to be locked.  It can only differ from
the repository if revisions are removed from the repository.

It is a better source of ancestry data than the inventory weave, because
it is accurate even in the presence of ghosts

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

iD8DBQFD9P+60F+nu1YWqI0RAlPdAJ4xSBnCTPbdM7FE7DOIf492lWAQYACeKbOc
6DphPD6vZzwF0aOeWfoaE1Y=
=98PE
-----END PGP SIGNATURE-----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ancestry-cache.patch
Type: text/x-patch
Size: 6905 bytes
Desc: not available
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060216/9e63f0ac/attachment.bin