diff mercurial/patch.py @ 16803:107a3270a24a

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.

--- a/mercurial/patch.py	Tue May 15 10:44:17 2012 -0700
+++ b/mercurial/patch.py	Tue May 15 10:46:23 2012 -0700
@@ -12,7 +12,7 @@
 from i18n import _
 from node import hex, nullid, short
 import base85, mdiff, scmutil, util, diffhelpers, copies, encoding, error
-import context
+import collections, context
 
 gitre = re.compile('diff --git a/(.*) b/(.*)')
 
@@ -1588,12 +1588,12 @@
 
     def lrugetfilectx():
         cache = {}
-        order = []
+        order = collections.deque()
         def getfilectx(f, ctx):
             fctx = ctx.filectx(f, filelog=cache.get(f))
             if f not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[f] = fctx.filelog()
             else:
                 order.remove(f)