时间戳

首页 > 解决方案 > 为什么 a=[0] 的 list(x for x in a) 比 a=[] 快？

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

问题描述

我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

标签： pythonperformancecpythonpython-internals

解决方案

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

在分析器中很容易看到，两个版本之间的主要区别在于list_resize-case_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_Mallocdown to传递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);
}

因此，案例a=[0]将使用pymalloc，而a=[]将使用底层 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 的加速。

对于分析，使用了以下脚本：

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

与 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-runtime 分配之间的差异。

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

推荐阅读