This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients Stefan Pochmann, rhettinger, tim.peters
Date 2020-02-29.17:28:41
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1582997321.74.0.207133537601.issue39801@roundup.psfhosted.org>
In-reply-to
Content
Be cautious about this.  Many years ago I looked into this, mostly in the context of the list sort's binary insertion sort, and results were all over the map, depending on the compiler in use, the optimization level, and the range at which (if any!) memmove() was actually faster than a simple loop.  A fancy memmove() will (at least) arrange to copy (say) 8 bytes at a time, but the overhead of setting that up (+ the function call) made it a loser when the number of bytes to be moved was "too small".

Don't know whether the comment in listobject.c's binarysort() still applies:

           Caution: using memmove is much slower under MSVC 5;
           we're not usually moving many slots. */

Optimizing to move 100,000 elements isn't really sane - cutting the constant factor on an inherently quadratic-time too-simplistic basic approach isn't really doing you a favor ;-)

Also note that sortedcontainers does not use unbounded-length Python lists under the covers.  It puts an upper bound on the length of the Python lists it uses, precisely to avoid visibly quadratic-time behavior.
History
Date User Action Args
2020-02-29 17:28:41tim.peterssetrecipients: + tim.peters, rhettinger, Stefan Pochmann
2020-02-29 17:28:41tim.peterssetmessageid: <1582997321.74.0.207133537601.issue39801@roundup.psfhosted.org>
2020-02-29 17:28:41tim.peterslinkissue39801 messages
2020-02-29 17:28:41tim.peterscreate