python - map 与星图的性能？

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。这种替换不会影响时序比。

Windows 10(64 位)上的 CPython 3.6.2

Answer 1

有几个因素(联合)导致观察到的性能差异:

• zip 在下一次 __next__ 调用时重新使用返回的 tuple 如果它的引用计数为 1。
• map 构建一个新 元组，每次 __next__ 调用时都会将其传递给“映射函数”制成。实际上它可能不会从头开始创建一个新的元组，因为 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)

是的，tuple 并不是真正不可变的，一个简单的 Py_DECREF 就足以“欺骗”zip 相信没有其他人拥有一个引用返回的元组!

至于“元组传递”:

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

所以有很多“巧合”导致 starmap 使用 zip 比使用多个参数调用 map 更快当被调用函数也是 C 函数时...