This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4313

pycompat: wrap xrange for py2 to provide efficient __contains__
ClosedPublic

Authored by joerg.sonnenberger on Aug 16 2018, 7:31 PM.

Details

Reviewers
indygreg
durin42
Group Reviewers
hg-reviewers
Commits
rHG45e05d39d9ce: pycompat: wrap xrange for py2 to provide efficient __contains__
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

indygreg accepted this revision.Aug 17 2018, 12:57 PM
indygreg added a subscriber: indygreg.

This seems reasonable.

Out of curiosity, what code is doing an expensive membership test and do you have timing numbers that could be included in the commit message?

This revision is now accepted and ready to land.Aug 17 2018, 12:57 PM
joerg.sonnenberger added a comment.Aug 17 2018, 5:50 PM

It's used in reportphasechanges and that accidently turned O(n) into O(n^2). I noticed it when trying a clone --narrow of the NetBSD repo, since it hung for quite a while in that loop.

durin42 accepted this revision.Aug 20 2018, 3:05 PM
Closed by commit rHG45e05d39d9ce: pycompat: wrap xrange for py2 to provide efficient __contains__ (authored by joerg.sonnenberger). · Explain WhyAug 20 2018, 3:19 PM
This revision was automatically updated to reflect the committed changes.
lothiraldan added a subscriber: lothiraldan.Aug 22 2018, 5:07 AM

As the initial code was introduced during the 4.6 cycle, is contained in
the 4.7 release and is a performance regression on clone and pull, would
it be possible to graft the fix on the stable range to be included in
the next 4.7 release?

Revision Contents
Changeset List

PathPackages
Mmercurial/changelog.py (4 lines)
Mmercurial/pycompat.py (20 lines)

Diff 10462

mercurial/changelog.py

# revision on the transaction. # revision on the transaction.
rev = len(self) rev = len(self)
node = super(changelog, self)._addrevision(node, rawtext, transaction, node = super(changelog, self)._addrevision(node, rawtext, transaction,
*args, **kwargs) *args, **kwargs)
revs = transaction.changes.get('revs') revs = transaction.changes.get('revs')
if revs is not None: if revs is not None:
if revs: if revs:
assert revs[-1] + 1 == rev assert revs[-1] + 1 == rev
revs = pycompat.xrange(revs[0], rev + 1) revs = pycompat.membershiprange(revs[0], rev + 1)
else: else:
revs = pycompat.xrange(rev, rev + 1) revs = pycompat.membershiprange(rev, rev + 1)
transaction.changes['revs'] = revs transaction.changes['revs'] = revs
return node return node

mercurial/pycompat.py

return w return w
# these wrappers are automagically imported by hgloader # these wrappers are automagically imported by hgloader
delattr = _wrapattrfunc(builtins.delattr) delattr = _wrapattrfunc(builtins.delattr)
getattr = _wrapattrfunc(builtins.getattr) getattr = _wrapattrfunc(builtins.getattr)
hasattr = _wrapattrfunc(builtins.hasattr) hasattr = _wrapattrfunc(builtins.hasattr)
setattr = _wrapattrfunc(builtins.setattr) setattr = _wrapattrfunc(builtins.setattr)
xrange = builtins.range xrange = builtins.range
membershiprange = builtins.range
unicode = str unicode = str
def open(name, mode='r', buffering=-1, encoding=None): def open(name, mode='r', buffering=-1, encoding=None):
return builtins.open(name, sysstr(mode), buffering, encoding) return builtins.open(name, sysstr(mode), buffering, encoding)
safehasattr = _wrapattrfunc(builtins.hasattr) safehasattr = _wrapattrfunc(builtins.hasattr)
def _getoptbwrapper(orig, args, shortlist, namelist): def _getoptbwrapper(orig, args, shortlist, namelist):
bytestr = str bytestr = str
iterbytestr = iter iterbytestr = iter
maybebytestr = identity maybebytestr = identity
sysbytes = identity sysbytes = identity
sysstr = identity sysstr = identity
strurl = identity strurl = identity
bytesurl = 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 # this can't be parsed on Python 3
exec('def raisewithtb(exc, tb):\n' exec('def raisewithtb(exc, tb):\n'
' raise exc, None, tb\n') ' raise exc, None, tb\n')
def fsencode(filename): def fsencode(filename):
""" """
Partial backport from os.py in Python 3, which only accepts bytes. Partial backport from os.py in Python 3, which only accepts bytes.
In Python 2, our paths should only ever be bytes, a unicode path In Python 2, our paths should only ever be bytes, a unicode path