Mercurial > public > mercurial-scm > hg-stable
diff mercurial/revset.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 | 2ac08d8b21aa |
| children | 5260a9e93113 |
line wrap: on
line diff
--- a/mercurial/revset.py Tue May 15 10:44:17 2012 -0700 +++ b/mercurial/revset.py Tue May 15 10:46:23 2012 -0700 @@ -5,7 +5,7 @@ # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. -import re +import re, collections import parser, util, error, discovery, hbisect, phases import node import bookmarks as bookmarksmod @@ -17,10 +17,10 @@ """Like revlog.ancestors(), but supports followfirst.""" cut = followfirst and 1 or None cl = repo.changelog - visit = list(revs) + visit = collections.deque(revs) seen = set([node.nullrev]) while visit: - for parent in cl.parentrevs(visit.pop(0))[:cut]: + for parent in cl.parentrevs(visit.popleft())[:cut]: if parent not in seen: visit.append(parent) seen.add(parent)