地图与星图的性能？

Question

我试图对两个序列进行纯python（没有外部依赖）元素比较。我的第一个解决方案是：

list(map(operator.eq, seq1, seq2))

然后我从itertools中找到了starmap函数，这看起来和我很相似。但事实证明，在最坏的情况下，它在我的电脑上要快 37%。因为这对我来说并不明显，所以我测量了从生成器中检索 1 个元素所需的时间（不知道这种方式是否正确）：

from operator import eq
from itertools import starmap

seq1 = [1,2,3]*10000
seq2 = [1,2,3]*10000
seq2[-1] = 5

gen1 = map(eq, seq1, seq2))
gen2 = starmap(eq, zip(seq1, seq2))

%timeit -n1000 -r10 next(gen1)
%timeit -n1000 -r10 next(gen2)

271 ns ± 1.26 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each)
208 ns ± 1.72 ns per loop (mean ± std. dev. of 10 runs, 1000 loops each)

在检索元素时，第二种解决方案的性能提高了 24%。之后，它们都为 list 产生相同的结果。但是从某个地方我们及时获得了额外的 13%：

%timeit list(map(eq, seq1, seq2))
%timeit list(starmap(eq, zip(seq1, seq2)))

5.24 ms ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
3.34 ms ± 84.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

我不知道如何更深入地分析这种嵌套代码？所以我的问题是，为什么第一个生成器的检索速度如此之快，并且我们从哪里获得额外的 list 函数 13%？

编辑：我的第一个意图是执行逐元素比较而不是 all，因此 all 函数被替换为 list。本次替换不影响时序比

CPython 3.6.2 在 Windows 10（64 位）

Answer 1

我注意到的一个区别是 map 如何从可迭代对象中检索项目。 map and zip create a tuple of iterators from each iterable passed. Now zip maintains a result tuple internally that is populated every time next is called and on the other hand, map creates a new array^* 每次调用都会释放它。

*_{正如 MSeifert 指出的那样，直到 3.5.4 map_next 每次都用于分配一个新的 Python 元组。这在 3.6 中发生了变化，直到使用了 5 个可迭代的 C 堆栈，并且对于任何大于该堆的东西都被使用。相关 PR：Issue #27809: map_next() uses fast call and Add _PY_FASTCALL_SMALL_STACK constant | Issue: https://bugs.python.org/issue27809}

Answer 2

有几个因素（共同）导致观察到的性能差异：

zip 重新使用返回的 tuple，如果它在下一个 __next__ 调用时的引用计数为 1。
map 构建一个 new tuple，每次调用 __next__ 时都会传递给 "mapped function"。实际上它可能不会从头开始创建新的元组，因为 Python 维护未使用的元组的存储。但是在那种情况下 map 必须找到一个大小合适的未使用的元组。
starmap 检查 iterable 中的下一项是否为 tuple 类型，如果是，则继续传递。
使用 PyObject_Call 从 C 代码中调用 C 函数不会创建传递给被调用方的新元组。

所以 starmap 和 zip 只会一遍又一遍地使用传递给 operator.eq 的一个元组，从而极大地减少了函数调用开销。另一方面，每次调用 operator.eq 时，map 都会创建一个新元组（或从 CPython 3.6 开始填充一个 C 数组）。所以实际上速度差异只是元组创建开销。

我将提供一些可用于验证这一点的 Cython 代码，而不是链接到源代码：

In [1]: %load_ext cython

In [2]: %%cython
   ...:
   ...: from cpython.ref cimport Py_DECREF
   ...:
   ...: cpdef func(zipper):
   ...:     a = next(zipper)
   ...:     print('a', a)
   ...:     Py_DECREF(a)
   ...:     b = next(zipper)
   ...:     print('a', a)

In [3]: func(zip([1, 2], [1, 2]))
a (1, 1)
a (2, 2)

是的，tuples 并不是真正不可变的，一个简单的 Py_DECREF 就足以让 "trick" zip 相信没有其他人持有对返回元组的引用!

至于"tuple-pass-thru"：

In [4]: %%cython
   ...:
   ...: def func_inner(*args):
   ...:     print(id(args))
   ...:
   ...: def func(*args):
   ...:     print(id(args))
   ...:     func_inner(*args)

In [5]: func(1, 2)
1404350461320
1404350461320

所以元组被直接传递（只是因为它们被定义为 C 函数！）纯 Python 函数不会发生这种情况：

In [6]: def func_inner(*args):
   ...:     print(id(args))
   ...:
   ...: def func(*args):
   ...:     print(id(args))
   ...:     func_inner(*args)
   ...:

In [7]: func(1, 2)
1404350436488
1404352833800

请注意，如果被调用的函数不是 C 函数，即使从 C 函数调用也不会发生这种情况：

In [8]: %%cython
   ...: 
   ...: def func_inner_c(*args):
   ...:     print(id(args))
   ...: 
   ...: def func(inner, *args):
   ...:     print(id(args))
   ...:     inner(*args)
   ...:

In [9]: def func_inner_py(*args):
    ...:     print(id(args))
    ...:
    ...:

In [10]: func(func_inner_py, 1, 2)
1404350471944
1404353010184

In [11]: func(func_inner_c, 1, 2)
1404344354824
1404344354824

所以有很多 "coincidences" 导致 starmap 使用 zip 比使用多个参数调用 map 更快，当被调用函数是还有一个 C 函数...

地图与星图的性能？

Performance of map vs starmap?

python

performance

cpython

itertools

python-3.x