为什么 a=[0] 的 list(x for x in a) 比 a=[] 快？

Question

我list(x for x in a)用三个不同的 CPython 版本进行了测试。Ona = [0]比 on 快得多a = []：

 3.9.0 64-bit       3.9.0 32-bit       3.7.8 64-bit
a = []  a = [0]    a = []  a = [0]    a = []  a = [0]

465 ns  412 ns     543 ns  515 ns     513 ns  457 ns   
450 ns  406 ns     544 ns  515 ns     506 ns  491 ns   
456 ns  408 ns     551 ns  513 ns     515 ns  487 ns   
455 ns  413 ns     548 ns  516 ns     513 ns  491 ns   
452 ns  404 ns     549 ns  511 ns     508 ns  486 ns   

使用tuple而不是list，这是预期的另一种方式：

 3.9.0 64-bit       3.9.0 32-bit       3.7.8 64-bit
a = []  a = [0]    a = []  a = [0]    a = []  a = [0]

354 ns  405 ns     467 ns  514 ns     421 ns  465 ns   
364 ns  407 ns     467 ns  527 ns     425 ns  464 ns   
353 ns  399 ns     490 ns  549 ns     419 ns  465 ns   
352 ns  400 ns     500 ns  556 ns     414 ns  474 ns   
354 ns  405 ns     494 ns  560 ns     420 ns  474 ns   

那么为什么list当它（和底层的生成器迭代器）必须做更多的事情时会更快呢？

在 Windows 10 Pro 2004 64 位上测试。

基准代码：

from timeit import repeat

setups = 'a = []', 'a = [0]'
number = 10**6

print(*setups, sep='   ')
for _ in range(5):
    for setup in setups:
        t = min(repeat('list(x for x in a)', setup, number=number)) / number
        print('%d ns' % (t * 1e9), end='   ')
    print()

字节大小，表明它不会为输入过度分配，[]但会为输入过度分配[0]：

>>> [].__sizeof__()
40
>>> list(x for x in []).__sizeof__()
40

>>> [0].__sizeof__()
48
>>> list(x for x in [0]).__sizeof__()
72

Answer 1

您观察到的是pymalloc（Python 内存管理器）比 C 运行时提供的内存管理器更快。

这是很容易在探查看到，这两个版本之间的主要区别是，list_resize和_PyObjectRealloc需要更多的时间a=[]-案例。但为什么？

当从可迭代对象创建新列表时，该列表会尝试获取迭代器中有多少元素的提示：

n = PyObject_LengthHint(iterable, 8);

但是，这不适用于生成器，因此提示是默认值8。

迭代器用完后，列表会尝试收缩，因为只有 0 或 1 个元素（并且由于大小提示太大而不是原始容量分配）。对于 1 个元素，这将导致（由于过度分配）4 个元素的容量。但是，对于 0 个元素的情况有一个特殊处理：它不会被过度分配：

// ...
if (newsize == 0)
        new_allocated = 0;
num_allocated_bytes = new_allocated * sizeof(PyObject *);
items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
// ...

所以在“空”的情况下，PyMem_Realloc会要求0字节。此调用将通过_PyObject_Malloc向下传递到pymalloc_alloc，在 0 字节的情况下返回NULL：

if (UNLIKELY(nbytes == 0)) {
   return NULL;
}

但是，如果返回，则_PyObject_Malloc 回退到“原始”malloc ：pymallocNULL

static void *
_PyObject_Malloc(void *ctx, size_t nbytes)
{
    void* ptr = pymalloc_alloc(ctx, nbytes);
    if (LIKELY(ptr != NULL)) {
        return ptr;
    }

    ptr = PyMem_RawMalloc(nbytes);
    if (ptr != NULL) {
        raw_allocated_blocks++;
    }
    return ptr;
}

从 的定义中_PyMem_RawMalloc可以很容易看出：

static void *
_PyMem_RawMalloc(void *ctx, size_t size)
{
    /* PyMem_RawMalloc(0) means malloc(1). Some systems would return NULL
       for malloc(0), which would be treated as an error. Some platforms would
       return a pointer with no memory behind it, which would break pymalloc.
       To solve these problems, allocate an extra byte. */
    if (size == 0)
        size = 1;
    return malloc(size);
}

因此，casea=[0]将使用pymalloc，whilea=[]将使用底层 c-runtime 的内存管理器，这解释了观察到的差异。

现在，这一切都可以看作是错过了优化，因为对于 newsize=0，我们只需将 设置ob_item为NULL，调整其他成员并返回。

让我们试试看：

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    // ...
    if (newsize == 0) {
        PyMem_Del(self->ob_item);
        self->ob_item = NULL;
        Py_SIZE(self) = 0;
        self->allocated = 0;
        return 0;
    }
    // ...
}

使用此修复程序a=[0]，如预期的那样，空箱变得比箱稍快（约 10%）。

我的说法pymalloc是，对于更小的大小比 C 运行时内存管理器更快，可以很容易地测试bytes：如果需要分配超过 512 个字节，pymalloc将回退到简单malloc：

print(bytes(479).__sizeof__())   #  512
%timeit bytes(479)               # 189 ns ± 20.4 ns
print(bytes(480).__sizeof__())   #  513
%timeit bytes(480)               # 296 ns ± 24.8 ns

实际差异大于所示的 50%（这种跳跃不能仅用大小改变一个字节来解释），因为至少有一部分时间用于字节对象的初始化等。

这是在cython的帮助下更直接的比较：

%%cython
from libc.stdlib cimport malloc, free
from cpython cimport PyMem_Malloc, PyMem_Del

def with_pymalloc(int size):
    cdef int i
    for i in range(1000):
        PyMem_Del(PyMem_Malloc(size))
        
def with_cmalloc(int size):
    cdef int i
    for i in range(1000):
        free(malloc(size))  

现在

%timeit with_pymalloc(1)   #  15.8 µs ± 566 ns
%timeit with_cmalloc(1)    #  51.9 µs ± 2.17 µs

即pymalloc大约快 3 倍（或每次分配大约 35ns）。注意：一些编译器会优化 free(malloc(size))掉，但MSVC 不会。

再举一个例子：前段时间我通过 pymalloc 替换了 c++ 的默认分配器，std::map这导致了因子 4 的加速。

为了分析，使用了以下脚本：

%timeit with_pymalloc(1)   #  15.8 µs ± 566 ns
%timeit with_cmalloc(1)    #  51.9 µs ± 2.17 µs

与 VisualStudio 在发布模式下的内置性能分析器一起使用。

a=[0]-version 需要 6.6 秒（在分析器中），而a=[]version 需要 6.9 秒（即大约慢 5%）。在“修复”之后，a=[]只需要 5.8 秒。

在list_resize和 中花费的时间份额_PyObject_Realloc：

                     a=[0]          a=[]       a=[], fixed        
list_resize           3.5%          10.2%          3%
_PyObject_Realloc     3.2%           9.3%          1%

显然，每次运行都有差异，但运行时间的差异是显着的，可以解释观察到的时间差异的大部分。

注：区别0.3秒10^7拨款大约每30ns的分配-一个数一个类似于我们得到pymalloc的和C运行时的分配之间的差异。

使用调试器验证上述内容时，必须注意，在调试模式下，Python 使用调试版本的 pymalloc，它将附加数据附加到所需的内存中，因此永远不会要求 pymalloc 在调试版本中分配 0 个字节，但是0 bytes + debug-overhead并且不会回退到malloc. 因此，应该在发布模式下进行调试，在调试构建中切换到 realease-pymalloc（可能有一个选项 - 我只是不知道，代码中的相关部分在这里和这里）。