Tim Peters <[email protected]> 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 <[email protected]>
<https://bugs.python.org/issue39801>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
