为什么这个 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
python3.12 g.py  18.18s user 0.00s system 99% cpu 18.201 total

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

Answer 1

我没有 py2 可以玩，所以下面的基准测试只是比较 py3 中的不同实现细节。所有基准测试都是在使用

time.process_time

运行 Python 3.8.8 内核的 IPython 7.22.0 中完成的。我每次跑都跑了三趟中间的路。结果大约 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 的固定宽度整数的更好方法是在 py3 中使用

float

，而不是每次都调用 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.32 秒，比原始代码快了 40%，这表明

for

实现可能变得更加健壮，因此在 py3 中也更加麻烦。

使用

float

中的

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 秒，比具有生成的

range

 的相同代码快约 13%，比原始代码好 42%。显然，发电机机械也是一个重要因素。