为什么这个 LCG 在 Python 2.7 中比在 Python 3.x 中快得多？

Question

这是 Python 中的一个简单的线性同余生成器：

def prng(n):
    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    while True:
        n = n * 48271 % 0x7fffffff
        yield n

g = prng(123)
for i in range(10**8):
    next(g)

assert next(g) == 1062172093

Python 2.7 比任何版本的 Python 3.x 都快。在 Linux 上生成 100M 项：

python2.7 g.py   14.60s user 0.65s system 99% cpu 15.260 total
python3.6 g.py   18.70s user 0.00s system 99% cpu 18.711 total
python3.7 g.py   18.10s user 0.04s system 99% cpu 18.193 total
python3.8 g.py   19.22s user 0.02s system 99% cpu 19.273 total
python3.9 g.py   18.90s user 0.00s system 99% cpu 18.924 total
python3.10 g.py  18.29s user 0.00s system 99% cpu 18.311 total
python3.11 g.py  16.93s user 0.00s system 99% cpu 16.946 total

为什么 CPython 3.x 解释器执行此代码的速度慢得多？

Answer 1

我没有 py2 可以玩，所以下面的基准测试只是比较 py3 中的不同实现细节。所有基准测试均在运行 Python 3.8.8 内核的 IPython 7.22.0 中完成，使用time.process_time. 我每次跑都跑了三趟中间的路。结果在约 1 秒内有意义，即约 3% 的准确度。

原始代码，循环需要 35.36 秒。

您可以将所有数字转换为适当的固定宽度 numpy 类型。这样，您就可以避免将所有 python 2 固定宽度整数隐式转换为 python 3 无限精度整数：

def prng(n):
    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    a = np.uint64(48271)
    b = np.uint64(0x7fffffff)
    n = np.uint64(n)
    while True:
        n = n * a % b
        yield n

g = prng(123)
p = process_time()
for i in range(10**8):
    next(g)
q = process_time()
print(q - p, ':', next(g))

运行时间缩短至 28.05 秒：下降约 21%。顺便说一句，使用全局a，b时间仅下降了约 5% 至 33.55 秒。

正如@Andrej Kesely 所建议的，模拟 py2 的固定宽度整数的更好方法是float在 py3 中使用，而不是每次都调用 numpy 的调度机制：

def prng(n):
    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    while True:
        n = n * 48271.0 % 2147483647.0
        yield n

g = prng(123.0)
p = process_time()
for i in range(10**8):
    next(g)
q = process_time()
print(q - p, ':', next(g))

事实上，我们看到运行时间为 23.63 秒，比原来减少了 33%。

为了绕过生成器 API，让我们在没有生成器的情况下重写循环：

n = 123
p = process_time()
for i in range(10**8):
    n = n * 48271 % 0x7fffffff
q = process_time()
print(q - p, n * 48271 % 0x7fffffff)

该运行时间仅为 26.28 秒，提高了约 26%。

做同样的事情，但使用函数调用只会节省约 3%（运行时间为 34.33 秒）：

def prng(n):
    return n * 48271 % 0x7fffffff

n = 123
p = process_time()
for i in range(10**8):
    n = prng(n)
q = process_time()
print(q - p, prng(n))

使用float可以像使用生成器一样加快函数版本的速度：

def prng(n):
    return n * 48271.0 % 2147483647.0

n = 123.0
p = process_time()
for i in range(10**8):
    n = prng(n)
q = process_time()
print(q - p, prng(n))

22.97 秒的运行时间额外下降了 33%，就像我们在生成器中看到的那样。

使用运行仅循环解决方案float也有很大帮助：

n = 123.0
p = process_time()
for i in range(10**8):
    n = n * 48271.0 % 2147483647.0
q = process_time()
print(q - p, n * 48271.0 % 2147483647.0)

运行时间为12.72s，比原来下降了64%，比int循环版本下降了52%。

显然，数据类型是导致速度缓慢的一个重要原因，但 Python 3 的生成器机制也很可能使运行时间再增加 20% 左右。消除这两个缓慢的来源使我们能够得到比原始代码运行时间一半更好的结果。

目前尚不完全清楚删除无限精度类型后的剩余部分有多少是由生成器与for循环机制引起的。那么让我们摆脱循环for看看会发生什么：

from itertools import islice
from collections import deque

def prng(n):
    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    while True:
        n = n * 48271 % 0x7fffffff
        yield n

g = prng(123)
p = process_time()
deque(islice(g, 10**8), maxlen=0)
q = process_time()
print(q - p, ':', next(g))

运行时间为 21.32s，比原始代码快了 40%，这表明for实现可能变得更加健壮，因此在 py3 中也更加麻烦。

float使用in会变得更好prng（与第一个示例完全相同）。现在，运行时间为 10.09 秒，下降了 71%，或者比原始代码快约 3 倍。

@chepner 建议的另一个可测试的区别是，在 py2 中，range(10**8)相当于 py3 中的list(range(10**8))。这很重要，因为 py3 中的生成器似乎更慢的确切原因。

def prng(n):
    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    while True:
        n = n * 48271.0 % 2147483647.0
        yield n

g = prng(123.0)
r = list(range(10**8))
p = process_time()
for i in r:
    next(g)
q = process_time()
print(q - p, ':', next(g))

这个版本需要 20.62 秒，比使用生成的相同代码快约 13% range，比原始代码快 42%。显然，发电机机械也是一个重要因素。