75

Using a list's insert function is much slower than achieving the same effect using slice assignment:

> python -m timeit -n 100000 -s "a=[]" "a.insert(0,0)"
100000 loops, best of 5: 19.2 usec per loop

> python -m timeit -n 100000 -s "a=[]" "a[0:0]=[0]"
100000 loops, best of 5: 6.78 usec per loop

(Note that a=[] is only the setup, so a starts empty but then grows to 100,000 elements.)

At first I thought maybe it's the attribute lookup or function call overhead or so, but inserting near the end shows that that's negligible:

> python -m timeit -n 100000 -s "a=[]" "a.insert(-1,0)"
100000 loops, best of 5: 79.1 nsec per loop

Why is the presumably simpler dedicated "insert single element" function so much slower?

I can also reproduce it at repl.it:

from timeit import repeat

for _ in range(3):
  for stmt in 'a.insert(0,0)', 'a[0:0]=[0]', 'a.insert(-1,0)':
    t = min(repeat(stmt, 'a=[]', number=10**5))
    print('%.6f' % t, stmt)
  print()

# Example output:
#
# 4.803514 a.insert(0,0)
# 1.807832 a[0:0]=[0]
# 0.012533 a.insert(-1,0)
#
# 4.967313 a.insert(0,0)
# 1.821665 a[0:0]=[0]
# 0.012738 a.insert(-1,0)
#
# 5.694100 a.insert(0,0)
# 1.899940 a[0:0]=[0]
# 0.012664 a.insert(-1,0)

I use Python 3.8.1 32-bit on Windows 10 64-bit.
repl.it uses Python 3.8.1 64-bit on Linux 64-bit.

8
  • Interesting to note that a=[]; a[0:0]=[0] does the same as a=[]; a[100:200]=[0]
    – smac89
    Feb 29, 2020 at 15:08
  • Is there any reason why you are testing this with just an empty list? Feb 29, 2020 at 15:13
  • @MisterMiyagi Well, I have to start with something. Note that it's empty only before the first insertion and grows to 100,000 elements during the benchmark. Feb 29, 2020 at 15:14
  • @smac89 a=[1,2,3];a[100:200]=[4] is appending 4 to the end of the list a interesting.
    – Ch3steR
    Feb 29, 2020 at 15:15
  • 1
    @smac89 While that's true, it doesn't really have to do with the question and I fear it might mislead someone into thinking that I'm benchmarking a=[]; a[0:0]=[0] or that a[0:0]=[0] does the same as a[100:200]=[0]... Feb 29, 2020 at 15:45

1 Answer 1

71

I think it's probably just that they forgot to use memmove in list.insert. If you take a look at the code list.insert uses to shift elements, you can see it's just a manual loop:

for (i = n; --i >= where; )
    items[i+1] = items[i];

while list.__setitem__ on the slice assignment path uses memmove:

memmove(&item[ihigh+d], &item[ihigh],
    (k - ihigh)*sizeof(PyObject *));

memmove typically has a lot of optimization put into it, such as taking advantage of SSE/AVX instructions.

5
  • 7
    If the interpreter was built with -O3 auto-vectorization enabled, that manual loop might compile efficiently. But unless the compiler recognizes the loop as being a memmove and compiles it into an actual call to memmove, it can only take advantage of instruction-set extensions enabled at compile time. (Fine if you're building your own with -march=native, not so much for distro binaries built with baseline). And GCC won't unroll loops by default unless you use PGO (-fprofile-generate / run / ...-use) Mar 1, 2020 at 1:10
  • @PeterCordes Do I understand you correctly that if the compiler does compile it into an actual memmove call, that can then take advantage of all extensions present at execution time? Mar 1, 2020 at 2:24
  • 1
    @HeapOverflow: Yes. On GNU/Linux for example, glibc overloads dynamic linker symbol resolution with a function that picks the best hand-written asm version of memmove for this machine based on saved CPU-detection results. (e.g. on x86, a glibc init function uses cpuid). Same for several other mem / str functions. So distros can compile with just -O2 to make run-anywhere binaries, but at least have memcpy/memmove use an unrolled AVX loop loading/storing 32 bytes per instruction. (Or even AVX512 on the few CPUs where that's a good idea; I think just Xeon Phi.) Mar 1, 2020 at 2:30
  • @PeterCordes Thanks. So several memmove versions are included in the compiled program? When does the version get picked? At program start, or at every memmove execution, or at some other time? Mar 1, 2020 at 2:38
  • 1
    @HeapOverflow: No, several memmove versions are sitting there in libc.so, the shared library. For each function, dispatch happens once, during symbol resolution (early binding or on the first call with traditional lazy binding). Like I said, it just overloads / hooks how dynamic linking happens, not by wrapping the function itself. (specifically via GCC's ifunc mechanism: code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/…). Related: for memset the usual choice on modern CPUs is __memset_avx2_unaligned_erms see this Q&A Mar 1, 2020 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.