changeset 13259:3b616dfa4b17

revlog: do revlog node->rev mapping by scanning Now that the nodemap is lazily created, we use linear scanning back from tip for typical node to rev mapping. Given that nodemap creation is O(n log n) and revisions searched for are usually very close to tip, this is often a significant performance win for a small number of searches. When we do end up building a nodemap for bulk lookups, the scanning function is replaced with a hash lookup.
author Matt Mackall <mpm@selenic.com>
date Tue, 11 Jan 2011 21:52:03 -0600
parents c2661863f16f
children 911a4499adb0
files mercurial/revlog.py
diffstat 1 files changed, 13 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/mercurial/revlog.py	Tue Jan 11 17:12:32 2011 -0600
+++ b/mercurial/revlog.py	Tue Jan 11 21:52:03 2011 -0600
@@ -283,6 +283,7 @@
         i = self.index
         for r in xrange(len(i) - 1):
             n[i[r][7]] = r
+        self.rev = self._revmap
         return n
 
     def tip(self):
@@ -292,11 +293,20 @@
     def __iter__(self):
         for i in xrange(len(self)):
             yield i
-    def rev(self, node):
+    def _revmap(self, node):
         try:
             return self.nodemap[node]
         except KeyError:
             raise LookupError(node, self.indexfile, _('no node'))
+
+    def rev(self, node):
+        if node == nullid:
+            return nullrev
+        i = self.index
+        for r in xrange(len(i) - 2, -1, -1):
+            if i[r][7] == node:
+                return r
+        raise LookupError(node, self.indexfile, _('no node'))
     def node(self, rev):
         return self.index[rev][7]
     def linkrev(self, rev):
@@ -711,8 +721,8 @@
             try:
                 # hex(node)[:...]
                 l = len(id) // 2  # grab an even number of digits
-                bin_id = bin(id[:l * 2])
-                nl = [n for n in self.nodemap if n[:l] == bin_id]
+                prefix = bin(id[:l * 2])
+                nl = [e[7] for e in self.index if e[7].startswith(prefix)]
                 nl = [n for n in nl if hex(n).startswith(id)]
                 if len(nl) > 0:
                     if len(nl) == 1: