为什么对于a=[0]而言，list(x for x in a)比a=[]更快？

Question

我在三个不同版本的CPython中测试了list(x for x in a)。对于a = [0]，它比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

- Kelly Bundy

---

我想知道这是否与预分配有关。如果我没记错，空列表会生成一个带有为未来元素分配的默认空间的列表对象。对于非空列表，list仅会分配足以容纳迭代器中元素的空间。元组由于无法增长，因此始终只分配足以容纳迭代器中内容的空间。 - chepner

@chepner 另一个测试：list(x for x in []).__sizeof__() 显示为 40 字节，而 list(x for x in [0]).__sizeof__() 则显示为 72 字节。 - Kelly Bundy

我无法重现你的结果（Python 3.7 64位/Win 10 Pro）。有时 [] 更快，有时 [0] 更快。 - Ocaso Protal

@OcasoProtal 奇怪，我在 Python 3.7 64 位 Win10 Pro 上经常看到 [] 的执行时间比 [0] 长大约两倍。 - Pranav Hosangadi

@HeapOverflow，我也无法重现你的结果；供参考，我得到了：[]: 463 ns ± 2.69 ns每次循环（15次运行的平均值±标准差，每次10000000个循环）和[0]: 471 ns ± 3.4 ns每次循环（15次运行的平均值±标准差，每次10000000个循环）。您还应该检查标准差，以确保您的结果不会有太大的变化。此外，请提供有关如何获得这些Python分布的详细信息。 - a_guest

Answer 1

你所观察到的是，Python内存管理器（pymalloc）比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);
// ...

因此，在“空”情况下，将请求0字节的PyMem_Realloc。这个调用将通过_PyObject_Malloc传递到pymalloc_alloc，在0字节的情况下返回NULL：

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

然而，如果pymalloc返回NULL，_PyObject_Malloc会回退到“原始”malloc。

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);
}

因此，情况a=[0]将使用pymalloc，而a=[]将使用底层c运行时的内存管理器，这解释了观察到的差异。

---

现在，这一切都可以被看作是错过的优化，因为对于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倍的加速。

---

以下脚本用于性能分析：

a=[0] # or a=[]
for _ in range(10000000):
    list(x for x in a)

与VisualStudio内置的Release模式性能分析器一起使用。

a=[0]版本需要6.6秒（在分析器中），而a=[]版本需要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%

显然，每次运行之间存在差异，但运行时间的差异很大，并且可以解释观察到的时间差异中的大部分。

注意：对于10 ^ 7个分配来说，0.3秒的差异大约是每个分配30ns的数量级 - 这个数字类似于我们在 pymalloc 和 c-runtime 分配之间得到的差异。

---

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

- ead

---

干得好，你也知道为什么 pymalloc 更快吗？我正在阅读源代码，但我不确定我是否正确理解它。是 pymalloc 仅仅为每个在性能测试循环的每次迭代中创建的新 list 重复使用完全相同的内存吗？那么如果只运行单个迭代（因为那时没有内存可重用），这种性能差异会消失吗？ - a_guest

@a_guest，我不知道为什么pymalloc更快（我真的不知道Windows上堆内存是如何工作的，也不太了解glibc的实现）。可能有一件事情是，pymalloc不适用于多线程（感谢GIL），因此它不必锁定任何内容。但这只是一种猜测。但这并不让我感到惊讶：如果pymalloc不能胜任底层内存管理器，那写pymalloc就很奇怪了。 - ead

我认为 Py_SIZE(self) = 0; 应该改为 Py_SET_SIZE(self, 0);，例如在这里。 - Kelly Bundy

@HeapOverflow Py_SET_SIZE 是相当新的（3.9，https://docs.python.org/3/c-api/structures.html#c.Py_SET_SIZE），并且是以下工作的一部分 https://bugs.python.org/issue39573。因此，对于 Python>=3.9，应优先使用 Py_SET_SIZE，而对于旧版本的 Python，则应使用 Py_SIZE(self)。 - ead