changeset 2081:416d8b2a75b8

Speedup revlog.ancestors for the linear case

revlog.ancestors can be expensive on big repos.  This cuts down the overall
time for hg update by ~19% by short cutting revlog.ancestors when one of the
revisions is reachable from another.

--- a/mercurial/revlog.py	Tue Apr 04 19:00:40 2006 -0400
+++ b/mercurial/revlog.py	Thu Apr 06 20:13:09 2006 -0400
@@ -940,6 +940,24 @@
 
     def ancestor(self, a, b):
         """calculate the least common ancestor of nodes a and b"""
+
+        # start with some short cuts for the linear cases
+        if a == b:
+            return a
+        ra = self.rev(a)
+        rb = self.rev(b)
+        if ra < rb:
+            last = b
+            first = a
+        else:
+            last = a
+            first = b
+
+        # reachable won't include stop in the list, so we have to use a parent
+        reachable = self.reachable(last, stop=self.parents(first)[0])
+        if first in reachable:
+            return first
+
         # calculate the distance of every node from root
         dist = {nullid: 0}
         for i in xrange(self.count()):