为什么 list(x for x in a) 对于 a=[0] 比对于 a=[] 更快？
Why is list(x for x in a) faster for a=[0] than for a=[]?
我用三种不同的 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
您观察到 pymalloc (Python memory manager) 比 C-runtime.
提供的内存管理器更快
在分析器中很容易看出，两个版本之间的主要区别在于 list_resize 和 _PyObjectRealloc 需要更多时间来处理 a=[]-case。但是为什么？
当从可迭代对象创建新列表时，列表会尝试 to get a hint 迭代器中有多少元素：
n = PyObject_LengthHint(iterable, 8);
但是，此 doesn't work for generators 和提示是默认值 8。
迭代器耗尽后，列表尝试to shrink, because there are only 0 or 1 element (and not the original capacity allocated due to a too large size-hint). For 1 element this would lead to (due to over-allocation) capacity of 4 elements. However, there is a special handling for the case of 0 elements: it will not be over-allocated:
// ...
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 down to pymalloc_alloc 传递，在 0 字节的情况下 returns NULL:
if (UNLIKELY(nbytes == 0)) {
return NULL;
}
但是，_PyObject_Malloc falls back 到“原始”malloc，如果 pymalloc returns NULL:
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;
}
在definition of _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，调整其他成员和 return .
让我们试试看：
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;
}
// ...
}
通过此修复，empty-case 变得比 a=[0] 情况稍快（大约 10%），正如预期的那样。
我的主张，pymalloc 比 C-runtime 内存管理器更快，可以用 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)) out, but MSVC doesn't.
再举一个例子：前段时间我通过 pymalloc 为 c++ 的 std::map 替换了默认分配器，这导致了 a speed up of factor 4.
为了分析，使用了以下脚本：
a=[0] # or a=[]
for _ in range(10000000):
list(x for x in a)
连同 VisualStudio 的 built-in 性能分析器 Release-mode。
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%
显然，与 运行 运行 存在差异，但 运行ning 时间的差异很显着，可以解释大部分观察到的时间差异。
注意：10^7 分配的 0.3 秒的差异是每个分配大约 30ns - 这个数字类似于我们得到的 pymalloc 和 c-runtime 之间的差异分配。
当用调试器验证上面的内容时，必须知道，在debug-mode Python中使用了调试版本的pymalloc，它会向所需内存追加额外的数据，因此pymalloc永远不会被要求在 debug-version 中分配 0 个字节，但是 0 bytes + debug-overhead 并且不会回退到 malloc。因此，应该在 debug-build 中切换到 realease-pymalloc 的发布模式进行调试（可能有一个选项 - 我只是不知道，代码中的相关部分是 here and here).
我用三种不同的 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
您观察到 pymalloc (Python memory manager) 比 C-runtime.
在分析器中很容易看出，两个版本之间的主要区别在于 list_resize 和 _PyObjectRealloc 需要更多时间来处理 a=[]-case。但是为什么？
当从可迭代对象创建新列表时，列表会尝试 to get a hint 迭代器中有多少元素：
n = PyObject_LengthHint(iterable, 8);
但是，此 doesn't work for generators 和提示是默认值 8。
迭代器耗尽后，列表尝试to shrink, because there are only 0 or 1 element (and not the original capacity allocated due to a too large size-hint). For 1 element this would lead to (due to over-allocation) capacity of 4 elements. However, there is a special handling for the case of 0 elements: it will not be over-allocated:
// ...
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 down to pymalloc_alloc 传递，在 0 字节的情况下 returns NULL:
if (UNLIKELY(nbytes == 0)) {
return NULL;
}
但是，_PyObject_Malloc falls back 到“原始”malloc，如果 pymalloc returns NULL:
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;
}
在definition of _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，调整其他成员和 return .
让我们试试看：
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;
}
// ...
}
通过此修复，empty-case 变得比 a=[0] 情况稍快（大约 10%），正如预期的那样。
我的主张，pymalloc 比 C-runtime 内存管理器更快，可以用 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)) out, but MSVC doesn't.
再举一个例子：前段时间我通过 pymalloc 为 c++ 的 std::map 替换了默认分配器，这导致了 a speed up of factor 4.
为了分析，使用了以下脚本：
a=[0] # or a=[]
for _ in range(10000000):
list(x for x in a)
连同 VisualStudio 的 built-in 性能分析器 Release-mode。
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%
显然，与 运行 运行 存在差异，但 运行ning 时间的差异很显着，可以解释大部分观察到的时间差异。
注意：10^7 分配的 0.3 秒的差异是每个分配大约 30ns - 这个数字类似于我们得到的 pymalloc 和 c-runtime 之间的差异分配。
当用调试器验证上面的内容时，必须知道，在debug-mode Python中使用了调试版本的pymalloc，它会向所需内存追加额外的数据，因此pymalloc永远不会被要求在 debug-version 中分配 0 个字节，但是 0 bytes + debug-overhead 并且不会回退到 malloc。因此，应该在 debug-build 中切换到 realease-pymalloc 的发布模式进行调试（可能有一个选项 - 我只是不知道，代码中的相关部分是 here and here).