pypy3在10 ** 10循环时间内发生了什么

Question

代码简单

@count_run_time
def test_while(l: int=0) -> (int, int):
    y = 0
    x = 0
    while x < l:
        y += x
        x += 1
    return x, y

当我使用cpython（Python 3.6.8（v3.6.8：3c6b436a57，Dec 24 2018，02:04:31））运行时

test_while(10**5)
[func: test_while] cost @0.008665s
(100000, 4999950000)

test_while(10**6)
[func: test_while] cost @0.080222s
(1000000, 499999500000)

test_while(10**7)
[func: test_while] cost @0.814199s
(10000000, 49999995000000)

test_while(10**8)
[func: test_while] cost @7.944017s
(100000000, 4999999950000000)

test_while(10**9)
[func: test_while] cost @80.063558s
(1000000000, 499999999500000000)

test_while(10**10)
[func: test_while] cost @851.572578s
(10000000000, 49999999995000000000)

从结果可以看出，随着循环次数的增加，消耗的时间也呈线性增加。

接下来，我尝试在pypy3（Python 3.6.1（784b254d6699，Apr 14 2019，10:22:55），[PyPy 7.1.1-beta0与GCC 4.2.1兼容Apple LLVM 10.0.0（clang- 1000.11.45.5）]），发生了奇怪的事情

test_while(10**5)
[func: test_while] cost @0.000117s
(100000, 4999950000)

test_while(10**6)
[func: test_while] cost @0.001446s
(1000000, 499999500000)

test_while(10**7)
[func: test_while] cost @0.010868s
(10000000, 49999995000000)

test_while(10**8)
[func: test_while] cost @0.105472s
(100000000, 4999999950000000)

test_while(10**9)
[func: test_while] cost @1.055387s
(1000000000, 499999999500000000)

test_while(10**10)
[func: test_while] cost @99.784553s
(10000000000, 49999999995000000000)

从结果来看，从10 5-10 6开始，时间的增长是线性的（10x）。但是在10 ** 10，时间增长增加了100倍。

pypy3在10 ** 10发生了什么？

Answer 1

pypy 通过利用众所周知的编译和优化技术实现了显着的加速。其中之一是尽可能使用本机 64 位整数算术，并在常规计算会导致优化路径溢出时回退到大整数实现。您的最后一个测试用例是结果首先超过 64 位范围的测试用例，我有一种非常强烈的感觉，这种回退到较慢的方法会导致与预期相比减慢十倍。顺便说一句，大整数加法运算不是恒定时间的，它们是按添加的位数计算的线性时间，因此我希望在这两种情况下都可以使用更大的输入进行超线性测量。（虽然不是因此而突然增加十倍）