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

[Stefan Pochmann]

Stefan Pochmann <stefan.pochmann at gmail.com> added the comment:

Benchmarking with two *Python* versions of bisect.insort, the "insert" version takes 1.08 seconds to insort the shuffled range(10**5) while the slice assignment version only takes 0.46 seconds:

from timeit import timeit
import random
from bisect import bisect_right

def insort1(a, x):
    lo = bisect_right(a, x)
    a.insert(lo, x)

def insort2(a, x):
    lo = bisect_right(a, x)
    a[lo:lo] = [x]

for _ in range(3):
    a = list(range(10**5))
    random.shuffle(a)
    for insort in insort1, insort2:
        it = iter(a)
        s = []
        print(timeit(lambda: insort(s, next(it)), number=len(a)))
    print()

----------

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