map 和 starmap 的性能区别？

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位) 上运行。

- godaygo

---

为什么不直接使用 seq1 == seq2？ - Błotosmętek

@Błotosmętek 谢谢您的纠正！我的第一意图是逐元素比较，而不是使用 all，这从我的问题中并不明显 :) 实际上，如果您将 all 替换为 list，时间顺序将保持不变。 - godaygo

什么Python版本？这是CPython吗？ - MSeifert

@MSeifert 是的，运行在 Windows 10 (64位) 上的 CPython 3.6.2。 - godaygo

Answer 1

多个因素共同导致性能差异：

• zip 在下一次调用 __next__ 时会重复使用返回的 tuple，如果该 tuple 的引用计数为 1。
• map 每次调用 __next__ 时都会创建一个新的 tuple 并将其传递给“映射函数”。实际上，Python 维护了一个未使用的 tuple 存储空间，所以它可能不会完全从头开始创建新的 tuple。但在这种情况下，map 必须查找正确大小的未使用的 tuple。
• starmap 检查可迭代对象中的下一个项是否是类型为 tuple 的元组，如果是，则直接传递该元组。
• 在 C 代码中使用 PyObject_Call 调用 C 函数时，不会创建要传递给被调用方的新 tuple。

因此，starmap 结合使用 zip 只会反复使用传递给 operator.eq 的一个 tuple，从而大大减少函数调用开销。另一方面，map 每次调用 operator.eq 时都会创建一个新的 tuple（或在 CPython 3.6 中填充 C 数组）。因此，实际上的速度差异就是 tuple 创建开销。

我不提供源代码链接，而是提供一些 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认为没有其他人持有返回的元组的引用。

至于“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

因此，在调用函数也是C函数时，使用starmap和zip比调用具有多个参数的map更快，这种情况中存在许多“巧合”...

- MSeifert

Answer 2

我能注意到的一个区别是map和zip从可迭代对象中检索项目的方式不同。两者都会从每个可迭代对象创建一个迭代器元组。现在，zip在内部维护一个结果元组，每次调用next时都会填充它；而另一方面，map会创建一个新的数组^*，每次调用next时都会分配和释放它。

---

*_{正如MSeifert指出的那样，在3.5.4版本之前，map_next每次都会分配一个新的Python元组。这在3.6中发生了改变，对于小于等于5个可迭代对象，使用C堆栈，否则使用堆。相关PR： Issue #27809: map_next() uses fast call 和 Add _PY_FASTCALL_SMALL_STACK constant | Issue: https://bugs.python.org/issue27809}

- Ashwini Chaudhary

---

这将假定这是3.6版本，请注意3.5.4中的代码看起来不同。 :) - MSeifert

@MSeifert 我想知道3.5.4实现相对于3.6.2有多慢/快。 - Ashwini Chaudhary

由于堆和C栈访问的差异，前5个可迭代对象可能会很慢。 - Ashwini Chaudhary

是的，你说得对。我的“研究”也得出了同样的结论。 - MSeifert