python - Numpy/Python : why is integer division slowest? 中基本数学运算的速度

Question

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

编辑1 :版本:Python 3.5.5，Numpy 1.15.0。

似乎在 PythonNumpy 中，整数除法比常规除法(整数)更昂贵，这是违反直觉的。测试时，我得到这个:

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 .它只提供整数的向量化乘法(通过 PMULUDQ 系列指令)，但同时提供乘法( MULPD family )和除法( DIVPD family )的浮点数。

当您使用 /对于真正的除法，结果类型是 float64 ，不是 int64 , 和 numpy可以通过单个打包加载和转换来执行操作(使用 the VCVTQQ2PD family of operations ，然后是打包除法，然后是打包移回内存( MOVAPD family )。

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

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

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

Point 是，在硬件级别，划分大量 64 位浮点值比划分大量 64 位整数值便宜，因此使用 / 进行真正除法本质上比使用 // 的楼层划分更快.

在我自己的机器上(我已经验证它只使用基线 SSE2 DIVPD ，所以它每条指令只进行两次除法)，我试图复制你的结果，我的时间差异有点小。真除法每次运算需要 485 μs，而地板除法每次运算需要 1.05 ms；楼层划分只长了 2 倍多一点，而对你来说几乎是 3 倍。猜测一下，您的副本 numpy编译时支持 AVX 或 AVX512，因此您从真正的除法中挤出了更多的性能。

至于为什么非numpy python int楼层划分比真正的划分需要更长的时间，这是一个类似的原因，但有一些复杂的因素:

(帮助 int / int，伤害 int // int)来自 numpy 的相同硬件指令开销问题申请; IDIV比 FDIV 慢.

(隐藏性能差异)执行单个分割的解释器开销占总时间的百分比更大(减少相对性能差异，因为更多的时间花在开销上)

(通常会增加整数运算的成本)Python 上的整数除法成本更高 int s;在 CPython 上，int实现为 15 位或 30 位肢体的数组，带有 ssize_t这定义了符号和肢体数量。 CPython 的 float只是一个普通 C 语言的普通对象包装器 double没有特殊功能。

(增加了 int // int 的成本)Python 保证了楼层除法，但 C 只提供了截断整数除法，所以即使在小 int 的快速路径中s、Python 必须检查不匹配的符号并调整操作以确保结果是地板，而不是简单的截断。

(增加 int / int 操作的成本，专门针对大输入)CPython 的 int / int操作不只是将两个操作数都转换为 float (C double) 并执行浮点除法。当操作数足够小时，它会尝试这样做，但如果它们太大，它有一个复杂的回退算法来实现最佳可能的正确性。

(如果结果在短时间内被丢弃，则减少重复 int / int 的成本)由于 Python float s 是固定大小，他们实现了一个小的性能优化来为他们使用一个空闲列表；创建和删除时 float s 重复，新创建的不需要去内存分配器，它们只是从空闲列表中拉取，并在引用计数下降到零时释放到空闲列表。 CPython 的 int s 是可变长度的，并且不使用空闲列表。

总的来说，这对 int / int 都略有帮助。 (至少对于小的 int s；大的 int 情况变得更加复杂，但是，对于 int // int 来说可能更糟，因为基于数组的除法算法非常复杂/昂贵)，所以看到类似的行为Python 内置类型并不意外。