为什么 a.insert(0,0) 比 a[0:0]=[0] 慢得多？

Question

使用列表的 insert 函数比使用切片赋值实现相同效果要慢得多:

> 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

（请注意，a=[]只是准备工作，因此a最初为空，但随后增加到100,000个元素。）

起初我以为可能是属性查找或函数调用开销等原因，但在接近结尾处插入元素时发现这是可以忽略不计的：

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

为什么那个看起来更简单的专用“插入单个元素”函数会慢得多？

我也可以在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)

我在Windows 10 64位系统上使用Python 3.8.1 32位版本。
而repl.it则在Linux 64位系统上使用Python 3.8.1 64位版本。

- Kelly Bundy

---

你为什么要用一个空列表来测试这个？ - MisterMiyagi

@MisterMiyagi 好的，我必须从某个地方开始。请注意，在第一次插入之前它是空的，并且在基准测试期间会增长到100,000个元素。 - Kelly Bundy

@smac89 a=[1,2,3];a[100:200]=[4] 将 4 添加到列表 a 的末尾，这很有趣。 - Ch3steR

有趣的一点：Python 3.8 在 python3.8 -m timeit -n 100000 -s "a=[]" "a.insert(-1,0)" 方面速度更快。也许 What’s New In Python 3.8 可以帮助您深入了解这个问题。 - fabianegli

@smac89 虽然这是正确的，但它与问题并没有真正关系，我担心这可能会误导某些人认为我正在对 a=[]; a[0:0]=[0] 进行基准测试，或者 a[0:0]=[0] 与 a[100:200]=[0] 相同... - Kelly Bundy

Answer 1

我认为他们可能只是在list.insert中忘记使用memmove了。如果您查看移动元素所使用的list.insert代码的链接，您会发现它只是一个手动循环。

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

在切片赋值路径上，list.__setitem__使用了memmove：

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

memmove 通常会进行很多优化，例如利用SSE/AVX指令。

- user2357112

---

谢谢。我创建了一个问题，涉及到这个事情。 - Kelly Bundy

如果解释器是使用-O3自动向量化编译的，那么手动循环可能会编译得更有效率。但是，除非编译器将该循环识别为memmove并将其编译成实际调用memmove的代码，否则它只能利用在编译时启用的指令集扩展。如果你是用-march=native建立自己的程序，那就没问题，但对于基线构建的发行版二进制文件就不太适用了。GCC默认不会展开循环，除非你使用PGO（-fprofile-generate/运行/...-use）。 - Peter Cordes

@PeterCordes 我理解你的意思是，如果编译器确实将其编译成实际的 memmove 调用，那么可以利用在执行时存在的所有扩展功能，对吗？ - Kelly Bundy

@HeapOverflow：是的。例如在GNU/Linux中，glibc超载了动态链接符号解析功能，使用一个函数根据保存的CPU检测结果选择最好的手写汇编版本的memmove函数（例如，在x86上，glibc init函数使用“cpuid”指令）。同样适用于其他几个mem/str函数。因此，发行版可以仅使用“-O2”编译以制作可在任何地方运行的二进制文件，但至少要让memcpy / memmove使用未卷绕的AVX循环每个指令加载/存储32字节。（甚至在少数CPU上使用AVX512也是个不错的主意；我认为只有Xeon Phi可以这么做。） - Peter Cordes

@PeterCordes 谢谢。所以编译后的程序中包含了几个 memmove 版本？版本是在程序启动时、每次执行 memmove 时还是其他时间选择的？ - Kelly Bundy

@HeapOverflow：不，几个memmove版本都在共享库libc.so中。对于每个函数，调度只会发生一次，在符号解析期间（早期绑定或传统的惰性绑定中的第一次调用）。就像我说的那样，它只是重载/挂钩动态链接发生的方式，而不是通过包装函数本身来实现。（具体来说，是通过GCC的ifunc机制：https://code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/memmove.c.html）。相关：对于memset，在现代CPU上通常选择`__memset_avx2_unaligned_erms` 请参见此问答。 - Peter Cordes