[issue39801] list.insert is slow, likely due to manual memmove

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

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.

----------
nosy: +tim.peters

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue39801>
_______________________________________