Mercurial > public > mercurial-scm > hg

comparison mercurial/revset.py @ 16803:107a3270a24a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
16802:7e5d94381cd1 16803:107a3270a24a
3 # Copyright 2010 Matt Mackall <mpm@selenic.com> 3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
4 # 4 #
5 # This software may be used and distributed according to the terms of the 5 # This software may be used and distributed according to the terms of the
6 # GNU General Public License version 2 or any later version. 6 # GNU General Public License version 2 or any later version.
7 7
8 import re 8 import re, collections
9 import parser, util, error, discovery, hbisect, phases 9 import parser, util, error, discovery, hbisect, phases
10 import node 10 import node
11 import bookmarks as bookmarksmod 11 import bookmarks as bookmarksmod
12 import match as matchmod 12 import match as matchmod
13 from i18n import _ 13 from i18n import _
15 15
16 def _revancestors(repo, revs, followfirst): 16 def _revancestors(repo, revs, followfirst):
17 """Like revlog.ancestors(), but supports followfirst.""" 17 """Like revlog.ancestors(), but supports followfirst."""
18 cut = followfirst and 1 or None 18 cut = followfirst and 1 or None
19 cl = repo.changelog 19 cl = repo.changelog
20 visit = list(revs) 20 visit = collections.deque(revs)
21 seen = set([node.nullrev]) 21 seen = set([node.nullrev])
22 while visit: 22 while visit:
23 for parent in cl.parentrevs(visit.pop(0))[:cut]: 23 for parent in cl.parentrevs(visit.popleft())[:cut]:
24 if parent not in seen: 24 if parent not in seen:
25 visit.append(parent) 25 visit.append(parent)
26 seen.add(parent) 26 seen.add(parent)
27 yield parent 27 yield parent
28 28