This is an archive of the discontinued Mercurial Phabricator instance.

pycompat: wrap xrange for py2 to provide efficient __contains__
ClosedPublic

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

Details

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

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
This revision was automatically updated to reflect the committed changes.

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?