为什么位运算比乘法/除法/取模慢？

Question

众所周知，将乘法、整数除法和模运算重写为位运算可以更高效地完成：

>>> x = randint(50000, 100000)
>>> x << 2 == x * 4
True
>>> x >> 2 == x // 4
True
>>> x & 3 == x % 4
True

在编译语言中，例如C/C++和Java，测试表明位运算通常比算术运算更快。 （请参见此处和此处）。然而，当我在Python中进行这些测试时，得到了相反的结果：

In [1]: from random import randint
   ...: nums = [randint(0, 1000000) for _ in range(100000)]

In [2]: %timeit [i * 8 for i in nums]
7.73 ms ± 397 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [3]: %timeit [i << 3 for i in nums]
8.22 ms ± 368 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [4]: %timeit [i // 8 for i in nums]
7.05 ms ± 393 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [5]: %timeit [i >> 3 for i in nums]
7.55 ms ± 367 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [6]: %timeit [i % 8 for i in nums]
5.96 ms ± 503 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [7]: %timeit [i & 7 for i in nums]
8.29 ms ± 816 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

正如您所看到的，位运算比其算术运算相对较慢，特别是模数运算。我针对另一组数字重复进行了此项测试，并得到了相同的结果。这是有原因的吗？这些测试是在CPython 3.6.7中进行的，如果这很重要。

- iz_

---

首先，Python的int对象与C语言中的int完全不同，它们是对象。底层表示甚至不是一个C int类型，而是由数字数组组成的，如果你懂C语言，可以自己看一下：https://github.com/python/cpython/blob/master/Include/longintrepr.h 这是因为Python的int对象是任意大小的，而不是固定大小的。 - juanpa.arrivillaga

按照您的要求，翻译如下：将某数除以2的幂次方再取模并不是一个很好的测试方式；任何优秀的 C 编译器都会将其编译为位移操作（对于有符号的i，还需要进行一些处理以保证可能为负的 i 的舍入语义正确）。我不指望 CPython 会这样做，但如果您想将其与 C 进行比较，请使用运行时可变的除数。（否则，i / 12345仍然可以编译为快速乘法/移位。现代x86 CPU具有非常高的性能乘法，大约与3个移位操作同样快。） - Peter Cordes

@PeterCordes 我知道编译器会做这种优化，所以我使用了“dis”模块来检查i % < 2的幂>是否在进行位移操作。据我所知，它并没有在进行位移操作，但是也许优化更深入，所以“dis”模块无法揭示它......我不确定。 - iz_

我对Python内部不是很了解，但这样的优化只有在可以针对常量进行一次优化而不是每次循环时才可能真正有效。检查 x & (x-1) == 0 是否为2的幂，然后使用类似于POSIX ffs() 或 x86 bsf / tzcnt 的位扫描来获取移位计数可能并不值得，除非实现预计2的幂非常普遍。(仅在除法时使用，如果输入具有多个limb，则不要使用乘法) - Peter Cordes

Answer 1

*、%和/都有单“limb”整数的快速运算路径。<<、>>和&则没有，它们走的是通用的任意精度计算路径。

- user2357112

---

这在运算符的实现中。 - user2357112

谢谢，实现的源代码很有帮助。还有一个问题，你能详细解释一下什么是“单肢”整数吗？ - iz_

所以，为了澄清，对于非常大的数字，位运算符会更快吗？ - iz_

“肢”是以2的30次方为基数的“数字”，以二进制整数形式存储在uint32_t或等效类型中。CPython将大整数存储在这种大小的块中。就像您可以一位一位地在纸上添加十进制数字一样，使用2的30次方的数字使得CPython能够通过每个原始加法操作完成大量的工作。(在汇编语言中使用基于2的32次方的块可以利用大多数架构对大整数的硬件支持来使用加法/加法-带进位，但这不是CPython所做的。2的30次方具有某些优势，尤其是对于没有汇编语言的纯C代码。) - Peter Cordes

更新：C++中的BigInt类 包含了一些更多的细节和链接到CPython的bigint代码。https://hg.python.org/cpython/file/db842f730432/Include/longintrepr.h#l10 / https://rushter.com/blog/python-integer-implementation/ - undefined

Answer 2

我测试了大量数字，发现位运算符速度更快。

python -m timeit '[i for i in range(10**64, 10**64+1000) if i & 0b10==0]'
1000 loops, best of 3: 238 usec per loop

python -m timeit '[i for i in range(10**64, 10**64+1000) if i % 2==0]'
1000 loops, best of 3: 303 usec per loop

- JackyChou

---

它们不是等价的：第一个应该是 i & 1。 - Davis Herring