Numpy/Python 中初等数学运算的速度：为什么整数除法最慢？

Question

EDIT2：正如@ShadowRanger 所指出的，这是一个 Numpy 现象，而不是 Python。但是当使用列表理解在 Python 中进行计算时（因此 x+y 变为 [a+b for a,b in zip(x,y)]），那么所有算术运算仍然需要同样长的时间（尽管是 Numpy 的 100 倍多）。但是，当我在真实模拟中使用整数除法时，它们运行更快。所以主要问题仍然存在：即使在 Python 中，为什么这些测试表明整数除法并不比常规除法快？

EDIT1：版本：Python 3.5.5，Numpy 1.15.0.

似乎在 ~~Python~~Numpy 中，整数除法比常规除法（整数）更多昂贵，这是违反直觉的。测试时，我得到这个：

setup_string = 'import numpy as np;\
                N=int(1e5);\
                x=np.arange(1,N+1, dtype=int);\
                y=np.arange(N, dtype=int);'

加法(+)~0.1s

timeit("x+y", setup=setup_string, number=int(1e3))
0.09872294100932777

减法(-)~0.1s

timeit("x-y", setup=setup_string, number=int(1e3))
0.09425603999989107

乘法(*)~0.1s

timeit("x*y", setup=setup_string, number=int(1e3))
0.09888673899695277

除法(/)~0.35s

timeit("x/y", setup=setup_string, number=int(1e3))
0.3574664070038125

整数除法(//)~1s(!)

timeit("x//y", setup=setup_string, number=int(1e3))
1.006298642983893

知道为什么会这样吗？为什么整数除法不快？

Answer 1

简短回答：浮点除法在硬件级别比整数除法便宜。在至少一种常见的架构上，浮点除法可以向量化，而整数除法不能，因此代码中最昂贵的操作必须执行更多次，整数数学的每次操作成本更高，而浮点数学则更少次，每次操作的成本更低。

长答案：numpy 在可用时使用向量化数学，the x86-64 architecture (which I'm guessing you're using) doesn't provide a SIMD instruction for integer division. It only provides vectorized multiplication for integers (via the PMULUDQ family of instructions), but provides both multiplication (MULPD family) and division (DIVPD family) 用于浮点数。

当你使用/作为真正的除法时，结果类型是float64，而不是int64，并且numpy可以通过单个打包加载来执行操作并且转换（the VCVTQQ2PD family of operations, followed by a packed divide, followed by a packed move back to memory (MOVAPD family）。

在配备 AVX512 的最现代 x86-64 芯片上（Xeon Phi x200+ 和 Skylake-X 及更高版本，后者自 2017 年底开始投放桌面市场），每个此类矢量化指令可以同时执行八个操作（ post-2011 的旧架构可以用 AVX 做四个，而在那之前你可以用 SSE2 做两个）。对于 /，这意味着您只需要发出两个 VCVTQQ2PD（每个源数组一个），一个 VDIVPD 和一个 VMOVAPD（所有 EVEX 作为前缀对于 512 位操作）每八个要执行的分区。相比之下，对于 // 执行相同的八个除法，它需要从内存中发出八个 MOVs（以加载左数组操作数），八个 CQOs（以符号扩展左IDIV 需要的 128 位值的数组操作数），八个 IDIV（至少为您从右侧数组加载），以及八个 MOV 返回内存。

我不知道 numpy 是否充分利用了这一点（我自己的副本显然是针对所有 x86-64 机器提供的 SSE2 基线编译的，所以它一次只能进行两次除法，而不是八次除法)，但有可能根本无法向量化等效的整数运算。

虽然针对整数情况的单独指令通常会便宜一些，但它们基本上总是比组合的等效指令更昂贵。而对于整数除法，它实际上对于单个操作比对于打包操作的浮点除法更糟糕；每 Agner Fog's Skylake-X table，每 IDIV 的成本为 24-90 个周期，延迟为 42-95；所有 512 位寄存器的 VDIVPD 成本为 16 个周期，延迟为 24 个周期。 VDIVPD 不仅完成了八倍的工作，而且（最多）完成了 IDIV 所需周期的三分之二（我不知道为什么 IDIV 有这么大的循环计数的范围，但 VDIVPD 甚至超过 IDIV 的最佳数字）。对于普通的 AVX 操作（每个 VDIVPD 只有四个除法），每个操作的周期被减半（到八个），而每个指令两个除法的普通 DIVPD 只有四个周期，所以除法本身无论您使用 SSE2、AVX 还是 AVX512 指令，速度基本相同（AVX512 只是为您节省了一点延迟和 load/store 开销）。即使从未使用过矢量化指令，普通的 FDIV 也只是一个 4-5 周期指令（二进制浮点除法通常比整数除法更容易，请看图），所以您会期望看到浮点数学做得很好。

要点是，在硬件级别，除以大量 64 位浮点值比除以大量 64 位整数值更便宜，因此使用 / 的真正除法本质上比使用底除法更快//.

在我自己的机器上（我已经验证它只使用基线 SSE2 DIVPD，所以它每条指令只做两次除法），我试图复制你的结果，我的时间差异较小.真正的除法每次操作花费 485 微秒，而底除法每次操作花费 1.05 毫秒； floor division 只长了 2 倍多一点，对你来说几乎长了 3 倍。据推测，您的 numpy 副本是在支持 AVX 或 AVX512 的情况下编译的，因此您从真正的除法中获得了更多的性能。

至于为什么非numpy Python int floor division 比真正的division 需要更长的时间，这是类似的原因，但有一些复杂的因素：

（帮助 int / int，伤害 int // int）来自 numpy 的相同硬件指令开销问题适用； IDIV 比 FDIV.
（隐藏性能差异）执行单个除法的解释器开销占总时间的百分比更大（减少相对性能差异，因为更多时间花在开销上）
（通常会增加整数运算的成本）整数除法在 Python int 上甚至更多昂贵；在 CPython 上，int 被实现为 15 位或 30 位分支的数组，其中 ssize_t 定义了分支的符号性和数量。 CPython 的 float 只是普通 C double 的普通对象包装器，没有特殊功能。
（增加了int // int的成本）Python保证了floor除法，但是C只提供截断整数除法，所以即使在小ints的快速路径中，Python 必须检查不匹配的符号并调整操作以确保结果是 floor，而不是简单的截断。
（增加 int / int 操作的成本，特别是对于大输入）CPython 的 int / int 操作不只是将两个操作数转换为 float（C double) 并进行浮点除法。当操作数足够小时，它会尝试这样做，但如果它们太大，它会使用复杂的回退算法来实现最佳可能的正确性。
（如果结果在短期内被丢弃，则减少重复 int / int 的成本）由于 Python float 是固定大小，他们实施了一个小的性能优化以使用空闲列表为他们；当你重复创建和删除float时，新创建的不需要去内存分配器，它们只是从空闲列表中拉取，并在引用计数降为零时释放到空闲列表。 CPython的int是可变长度的，没有使用空闲列表。

总的来说，这都稍微有利于 int / int（至少对于小的 int 是这样；大的 int 情况变得更复杂，但是，它可能更糟对于 int // int 也是如此，因为基于数组的除法算法非常疯狂 complicated/expensive)，所以看到 Python 内置类型的类似行为并不意外。

Numpy/Python 中初等数学运算的速度：为什么整数除法最慢？

speed of elementary mathematical operations in Numpy/Python: why is integer division slowest?

python

performance

numpy

integer-division

integer-arithmetic