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 with 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)

从结果来看，从105-106，时间的增长是线性的（10x）。但是到了10**10，时间增长了100倍。

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

Answer 1

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

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

What happened to pypy3 under the 10**10 loop time

pypy

python-3.x