pycompat: wrap xrange for py2 to provide efficient __contains__
The C implementation of xrange in Python 2 provides a O(n) membership
test, which is noticable on pull-based clones of large repositories.
Avoid this by providing a wrapper class with O(1) membership test based
on the edges of the range.
Differential Revision: https://phab.mercurial-scm.org/D4313
--- a/mercurial/changelog.py Mon Aug 20 09:48:08 2018 -0700
+++ b/mercurial/changelog.py Fri Aug 17 00:51:46 2018 +0200
@@ -556,8 +556,8 @@
if revs is not None:
if revs:
assert revs[-1] + 1 == rev
- revs = pycompat.xrange(revs[0], rev + 1)
+ revs = pycompat.membershiprange(revs[0], rev + 1)
else:
- revs = pycompat.xrange(rev, rev + 1)
+ revs = pycompat.membershiprange(rev, rev + 1)
transaction.changes['revs'] = revs
return node
--- a/mercurial/pycompat.py Mon Aug 20 09:48:08 2018 -0700
+++ b/mercurial/pycompat.py Fri Aug 17 00:51:46 2018 +0200
@@ -278,6 +278,7 @@
hasattr = _wrapattrfunc(builtins.hasattr)
setattr = _wrapattrfunc(builtins.setattr)
xrange = builtins.range
+ membershiprange = builtins.range
unicode = str
def open(name, mode='r', buffering=-1, encoding=None):
@@ -343,6 +344,25 @@
strurl = identity
bytesurl = identity
+ class membershiprange(object):
+ "Like xrange(a,b) but with constant-time membership test"
+ def __init__(self, a, b):
+ self._range = xrange(a, b)
+ def __getitem__(self, n):
+ return self._range[n]
+ def __hash__(self):
+ return hash(self._range)
+ def __iter__(self):
+ return iter(self._range)
+ def __len__(self):
+ return len(self._range)
+ def __reversed__(self):
+ return reversed(self._range)
+ def __contains__(self, n):
+ if not self._range:
+ return False
+ return n >= self._range[0] and n <= self._range[-1]
+
# this can't be parsed on Python 3
exec('def raisewithtb(exc, tb):\n'
' raise exc, None, tb\n')