Mercurial > public > mercurial-scm > hg

diff mercurial/revlog.py @ 16803:107a3270a24a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
cleanup: use the deque type where appropriate There have been quite a few places where we pop elements off the front of a list. This can turn O(n) algorithms into something more like O(n**2). Python has provided a deque type that can do this efficiently since at least 2.4. As an example of the difference a deque can make, it improves perfancestors performance on a Linux repo from 0.50 seconds to 0.36.
author Bryan O'Sullivan <bryano@fb.com>
date Tue, 15 May 2012 10:46:23 -0700
parents 2631cd5dd244
children cafd8a8fb713
line wrap: on
line diff
--- a/mercurial/revlog.py	Tue May 15 10:44:17 2012 -0700
+++ b/mercurial/revlog.py	Tue May 15 10:46:23 2012 -0700
@@ -15,7 +15,7 @@
 from node import bin, hex, nullid, nullrev
 from i18n import _
 import ancestor, mdiff, parsers, error, util, dagutil
-import struct, zlib, errno
+import struct, zlib, errno, collections
 
 _pack = struct.pack
 _unpack = struct.unpack
@@ -362,13 +362,13 @@
         """return the set of all nodes ancestral to a given node, including
          the node itself, stopping when stop is matched"""
         reachable = set((node,))
-        visit = [node]
+        visit = collections.deque([node])
         if stop:
             stopn = self.rev(stop)
         else:
             stopn = 0
         while visit:
-            n = visit.pop(0)
+            n = visit.popleft()
             if n == stop:
                 continue
             if n == nullid:
@@ -389,10 +389,10 @@
         an ancestor of itself.  Results are in breadth-first order:
         parents of each rev in revs, then parents of those, etc.  Result
         does not include the null revision."""
-        visit = list(revs)
+        visit = collections.deque(revs)
         seen = set([nullrev])
         while visit:
-            for parent in self.parentrevs(visit.pop(0)):
+            for parent in self.parentrevs(visit.popleft()):
                 if parent not in seen:
                     visit.append(parent)
                     seen.add(parent)
@@ -447,9 +447,9 @@
 
         # take all ancestors from heads that aren't in has
         missing = set()
-        visit = [r for r in heads if r not in has]
+        visit = collections.deque(r for r in heads if r not in has)
         while visit:
-            r = visit.pop(0)
+            r = visit.popleft()
             if r in missing:
                 continue
             else: