diff mercurial/util.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/util.py	Tue May 15 10:44:17 2012 -0700
+++ b/mercurial/util.py	Tue May 15 10:46:23 2012 -0700
@@ -14,7 +14,7 @@
 """
 
 from i18n import _
-import error, osutil, encoding
+import error, osutil, encoding, collections
 import errno, re, shutil, sys, tempfile, traceback
 import os, time, datetime, calendar, textwrap, signal
 import imp, socket, urllib
@@ -205,12 +205,12 @@
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}
-    order = []
+    order = collections.deque()
     if func.func_code.co_argcount == 1:
         def f(arg):
             if arg not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[arg] = func(arg)
             else:
                 order.remove(arg)
@@ -220,7 +220,7 @@
         def f(*args):
             if args not in cache:
                 if len(cache) > 20:
-                    del cache[order.pop(0)]
+                    del cache[order.popleft()]
                 cache[args] = func(*args)
             else:
                 order.remove(args)
@@ -865,7 +865,7 @@
         Returns less than L bytes if the iterator runs dry."""
         left = l
         buf = ''
-        queue = self._queue
+        queue = collections.deque(self._queue)
         while left > 0:
             # refill the queue
             if not queue:
@@ -878,13 +878,14 @@
                 if not queue:
                     break
 
-            chunk = queue.pop(0)
+            chunk = queue.popleft()
             left -= len(chunk)
             if left < 0:
-                queue.insert(0, chunk[left:])
+                queue.appendleft(chunk[left:])
                 buf += chunk[:left]
             else:
                 buf += chunk
+        self._queue = list(queue)
 
         return buf