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.
author Chris Mason <mason@suse.com>
date Thu, 06 Apr 2006 20:13:09 -0400
parents 1cbb14c048cb
children 856f0ba200bc
files mercurial/revlog.py
diffstat 1 files changed, 18 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- 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()):