Что случилось с pypy3 во время цикла 10 ** 10 - PullRequest
Новая
       13

Что случилось с pypy3 во время цикла 10 ** 10

5 голосов
/ 10 мая 2019

Простой код пока 

@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, 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, 14 апреля 2019, 10:22:55), [PyPy 7.1.1-бета0 с 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?

1 Ответ

3 голосов
/ 10 мая 2019

Pypy достигает значительного ускорения благодаря использованию хорошо известных методов компиляции и оптимизации. Одним из них является использование родной 64-битной целочисленной арифметики везде, где это возможно, и возврат к реализациям biginteger, когда регулярные вычисления вызовут переполнение в оптимизированном пути. Ваш последний тестовый пример - тот, где результат сначала превышает 64-битный диапазон, и у меня есть сильное чувство, что этот откат к более медленному методу вызывает десятикратное замедление по сравнению с ожидаемым. Кстати, операции сложения больших целых не являются постоянным временем, они представляют собой линейное время по количеству добавленных цифр, поэтому я ожидаю суперлинейные измерения с большими входными данными в обоих случаях. (хотя из-за этого не произошло внезапного увеличения в 10 раз)

...