复制性能：列表与数组

Question

我正在优化一段代码并发现列表复制（浅层）是瓶颈。

现在我很好奇：为什么列表复制比复制array8 字节慢这么多？在我看来，应该没有区别。在这两种情况下，应该只是memcpy(dst, src, sizeof(int64_t)*len(src))因为指针的长度为 8 个字节。但显然 Python 做的工作比我预期的要多。它与GC有某种关系吗？或者列表是否可能实现为链接列表？

import array
import numpy as np
import timeit


n = 100*1000
lst = [i for i in range(n)]
arr = array.array('q', lst)
nmp = np.array(arr, dtype=np.int64)

assert(arr.itemsize == 8)

n_iter = 100000
print('=== copy() ===')
print('List of int:', timeit.timeit(stmt='lst.copy()', setup='from __main__ import lst', number=n_iter))
print('Array of 8-bytes:', timeit.timeit(stmt='arr.__copy__()', setup='from __main__ import arr', number=n_iter))
print('Numpy array of int64:', timeit.timeit(stmt='nmp.copy()', setup='from __main__ import nmp', number=n_iter))

结果：

import array
import numpy as np
import timeit


n = 100*1000
lst = [i for i in range(n)]
arr = array.array('q', lst)
nmp = np.array(arr, dtype=np.int64)

assert(arr.itemsize == 8)

n_iter = 100000
print('=== copy() ===')
print('List of int:', timeit.timeit(stmt='lst.copy()', setup='from __main__ import lst', number=n_iter))
print('Array of 8-bytes:', timeit.timeit(stmt='arr.__copy__()', setup='from __main__ import arr', number=n_iter))
print('Numpy array of int64:', timeit.timeit(stmt='nmp.copy()', setup='from __main__ import nmp', number=n_iter))

Answer 1

对于列表，不仅仅是复制对对象的引用。它还增加了对象内部的引用计数器。另外，这些对象对缓存不友好，因为它们彼此之间不太相邻，因为它们位于对象内部（以及对象的其他数据），并且这些对象位于堆上的某个位置。另请参阅为什么复制打乱的列表要慢得多？（这里有更快的“未洗牌”案例，但那里的解释可能仍然有用）。