Mercurial > public > mercurial-scm > hg
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.
| author | Bryan O'Sullivan <bryano@fb.com> |
|---|---|
| date | Tue, 15 May 2012 10:46:23 -0700 |
| parents | e406b9656da3 |
| children | cafd8a8fb713 |
line wrap: on
line diff
--- 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