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.
Details
Details
- Reviewers
indygreg durin42 - Group Reviewers
hg-reviewers - Commits
- rHG45e05d39d9ce: pycompat: wrap xrange for py2 to provide efficient __contains__
Diff Detail
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
Comment Actions
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?
Comment Actions
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.
Comment Actions
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?