为什么 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 位。

Answer 1

我认为这可能只是他们忘记使用memmovein list.insert。如果您查看用于移动元素的代码 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 指令。