D4313: pycompat: wrap xrange for py2 to provide efficient __contains__

joerg.sonnenberger (Joerg Sonnenberger) phabricator at mercurial-scm.org
Thu Aug 16 23:31:17 UTC 2018


joerg.sonnenberger created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION 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.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D4313

AFFECTED FILES
  mercurial/changelog.py
  mercurial/pycompat.py

CHANGE DETAILS

diff --git a/mercurial/pycompat.py b/mercurial/pycompat.py
--- a/mercurial/pycompat.py
+++ b/mercurial/pycompat.py
@@ -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')
diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -563,8 +563,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



To: joerg.sonnenberger, #hg-reviewers
Cc: mercurial-devel


More information about the Mercurial-devel mailing list