时间戳

首页 > 解决方案 > pypy3 在 10**10 循环时间下发生了什么

python-3.x - pypy3 在 10**10 循环时间下发生了什么

问题描述

简单的while代码

@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 Compatible 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到 10 6，时间的增长是线性的（10x）。但是在 10**10 时，时间增长增加了 100 倍。

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

标签： python-3.xpypy

解决方案

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

推荐阅读