Mercurial > public > mercurial-scm > hg-stable
diff mercurial/hbisect.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 | 14913fcb30c6 |
| children | cafd8a8fb713 |
line wrap: on
line diff
--- a/mercurial/hbisect.py Tue May 15 10:44:17 2012 -0700 +++ b/mercurial/hbisect.py Tue May 15 10:46:23 2012 -0700 @@ -11,7 +11,7 @@ import os, error from i18n import _ from node import short, hex -import util +import collections, util def bisect(changelog, state): """find the next node (if any) for testing during a bisect search. @@ -69,10 +69,10 @@ # build children dict children = {} - visit = [badrev] + visit = collections.deque([badrev]) candidates = [] while visit: - rev = visit.pop(0) + rev = visit.popleft() if ancestors[rev] == []: candidates.append(rev) for prev in clparents(rev):