[MERGE] Shortcut 'common_ancestor' when a branch tip is in the ancestry

[Aaron Bentley]

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

John Arbash Meinel wrote:
> Aaron has a good point about caching the distance from null for each
> revision, since it doesn't change often. But I'm also wondering if that
> is the algorithm we want to be using.
> 
> Unless we can find a way to handle partial graphs, I don't see any
> algorithm scaling well when we have 160k revisions. (Like the Mozilla
> tree, or a kernel tree).

I don't think handling partial graphs is out of the question.

In fact, a good start would be implementing an uncommon_ancestors
method.  Right now, we always traverse the whole graph to get that info,
which seems unnecessarily expensive.

> I think accepting a slightly less optimal base in exchange for much
> faster performance could be reasonable.

The unfortunate truth is that this algorithm, itself, is not optimal.

The vast majority of the time, the Least Common Ancestor is selected,
and this can cheaply be calculated from the tips.

When there is no Least Common Ancestor, you're almost always dealing
with a criss-cross merge, and in those cases, it seems least harmful to
select an older common ancestor (e.g. the LCA of the Minimal Common
Ancestors), which this algorithm does not do.

It's also possible that the implementation could be optimized.  I
haven't touched it in some time, and I'm amazed that it's held up this well.

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

iD8DBQFGG/M+0F+nu1YWqI0RApLQAJ916LBb5Lan1WTzZgNwRSBTeym4gQCeJyOb
fY2rb9LpKM41lUeXURubLlk=
=eM+m
-----END PGP SIGNATURE-----