为什么Python 2.7中的LCG比Python3.9中的LCG要快得多呢？

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)

print(next(g))

Python 2.7在这里要快得多。Python3.9中的运行时间相比降低了110-115% ( macbook上的自制CPythons )。产生1亿个术语：

$ python2 -V
Python 2.7.16
$ python3 -V
Python 3.9.1
$ time python2 g.py
1062172093
python2 g.py  11.31s user 0.43s system 99% cpu 11.759 total
$ time python3 g.py
1062172093
python3 g.py  24.48s user 0.04s system 99% cpu 24.549 total

为什么CPython 3.x解释器在执行这段代码时要慢得多？有什么办法能让它与2.7的运行时间持平吗？

我并不是在寻找使用编译的答案- JIT、PyPy、cython、numba等等。使用numpy很好，也可以通过任何方式说服CPython使用固定大小的uint(如果stdlib大int是效率低下的根源)。

Answer 1

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

原始代码，循环时间为35.36秒。

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

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.05s:下降了21%。顺便说一句，使用全局a和b只减少了大约5%的时间，达到33.55s。

作为@Andrej Kesely建议，模拟py2的固定宽度ints的更好方法是在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 s，比原来的运行时减少了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.28s，提高了26%。

执行相同的操作，但使用函数调用只会节省3%(运行时为34.33 s)：

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.72 s，比原始版本下降了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在prng中会变得更好(与第一个示例完全一样)。现在运行时是10.09 s，下降了71%，比原来的代码快了3倍。

另一个可测试的区别是，由@chepner推荐在py2's中，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%。很明显，发电机机械也是一个重要的因素。