Mercurial > public > mercurial-scm > hg
diff mercurial/treediscovery.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 | df902fe3d79e |
| children | cafd8a8fb713 |
line wrap: on
line diff
--- a/mercurial/treediscovery.py Tue May 15 10:44:17 2012 -0700 +++ b/mercurial/treediscovery.py Tue May 15 10:46:23 2012 -0700 @@ -7,7 +7,7 @@ from node import nullid, short from i18n import _ -import util, error +import util, error, collections def findcommonincoming(repo, remote, heads=None, force=False): """Return a tuple (common, fetch, heads) used to identify the common @@ -56,11 +56,11 @@ # a 'branch' here is a linear segment of history, with four parts: # head, root, first parent, second parent # (a branch always has two parents (or none) by definition) - unknown = remote.branches(unknown) + unknown = collections.deque(remote.branches(unknown)) while unknown: r = [] while unknown: - n = unknown.pop(0) + n = unknown.popleft() if n[0] in seen: continue