Использование памяти Pypy увеличивается, когда ничего нового не выделяется

Я не уверен, что это дубликат других вопросов памяти PyPy, но здесь я приведу конкретный пример.

from __future__ import division

def mul_inv(a, m):
    """Modular multiplicative inverse, a^-1 mod m. Credit: rosettacode.org"""
    m0 = m
    x0, x1 = 0, 1
    if m == 1: return 1
    while a > 1:
        assert m != 0, "a and m must be coprime"
        q = a // m
        a, m = m, a%m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += m0
    return x1


M = 1000000009
L = 10**8

bin2 = [0] * L
bin2[0] = 1
for n in range(L-1):
    bin2[n+1] = (bin2[n] * (4*n + 2) * mul_inv(n+1, M)) % M
    if n % 10**5 == 0: print(n, bin2[n])

print(bin2[:20])

С python 3.6 программа использует не более 3-4 ГБ и работает до завершения (изменение списка Армина Риго не меняет этого существенно). С python 2.7.13 с PyPy 5.10.0 программа быстро достигает 8 ГБ (сколько у меня оперативной памяти) и зависает. Даже при вызовах gc.collect() программе не хватает памяти, когда n составляет около 3,5 * 10 ^ 7.

Откуда это использование памяти? Единственным большим использованием памяти должно быть инициализация bin2 как списка 10 ^ 8 int. Ничто другое не должно увеличивать использование памяти при условии, что все локальные переменные в mul_inv собираются сборщиком мусора.


python pypy out-of-memory memory
person qwr    schedule 04.09.2018    source источник
comment
range(L-1) создаст список размером не менее 10**8*24 байтов, поскольку каждый int объект требует около 24 байтов в CPython, не уверен в PyPy. Так что попробуйте с xrange.   -  person juanpa.arrivillaga    schedule 04.09.2018
comment
Хотя, немного читая, PyPy может оптимизировать цикл for i in range(x), чтобы фактически не материализовать весь список.   -  person juanpa.arrivillaga    schedule 04.09.2018
comment
@ juanpa.arrivillaga range никогда раньше не был для меня проблемой. Например, у меня есть функция Sieve of Eratosthenes, которая без проблем делает что-то вроде range(10**8).   -  person qwr    schedule 04.09.2018
comment
Nothing else should be increasing the memory usage - ну нет, каждый новый объект long, хранящийся в списке, требует дополнительной памяти.   -  person Armin Rigo    schedule 05.09.2018

Ответы (2)


arrow_upward
1
arrow_downward

Ой, это плохой случай оптимизации списков целых чисел. Проблема в том, что это начинается со списка целых чисел:

bin2 = [0] * L

Это внутренне хранится в виде массива целых чисел. Обычно он намного компактнее, хотя в данном случае ничего не меняет --- потому что на CPython это список, содержащий L копии одного и того же объекта 0.

Но проблема в том, что довольно скоро мы сохраняем long в списке. На этом этапе нам нужно превратить весь список в общий вид, который может хранить что угодно. Но! Проблема в том, что мы видим 100 миллионов нулей и поэтому создаем 100 миллионов 0 объектов. Это мгновенно создает нехватку памяти 3 ГБ впустую в дополнение к 800 МБ для самого списка.

Мы можем проверить, что проблема не возникает, если мы инициализируем список таким образом, чтобы он действительно содержал в 100 миллионов раз один и тот же объект:

bin2 = [0L] * L     # Python 2.x
bin2[0] = 1

Тем не менее, в вашем примере вам не нужно, чтобы список содержал 100 миллионов элементов. Вы можете инициализировать его как:

bin2 = [1]

и используйте bin2.append(). Это позволяет программе запускаться намного быстрее и без большого использования памяти в самом начале.

Обратите внимание, что PyPy3 по-прежнему использует больше памяти, чем CPython3.

person Armin Rigo    schedule 04.09.2018
comment
Спасибо за полезный анализ. Однако использование памяти все равно растет даже с gc.collect(). Вы знаете, как я могу это смягчить? Я озадачен, откуда вообще взялось это дополнительное использование памяти. - person qwr; 04.09.2018
comment
Использование памяти продолжает расти, потому что цикл заменяет копии 0 (маленькое целое число) объектами long, которые занимают больше места. На PyPy2 понять проблему проще. В Python3 все целые числа одинаковы, но PyPy3 оптимизирует маленькие целые числа больше, чем целые числа, которые были бы long на Python2 (даже если они были получены, например, из (very_large-very_large), что дает большой 0 вместо маленького 0; это тоже можно оптимизировать) - person Armin Rigo; 13.09.2018
comment
Мы только что провели оптимизацию, которая решила здесь проблему: теперь any_long_number % small_int возвращает небольшое целое число в PyPy3, потому что может (в отличие от PyPy2, где это определено языком для возврата объекта long). Поскольку мы храним в списке bin2 значения, которые все равны % M, это сохраняет bin2 списком небольших целых чисел, и это должно потреблять немного меньше памяти, чем сейчас CPython. - person Armin Rigo; 30.05.2021

arrow_upward
1
arrow_downward

AFAICT проблема заключается в том, что вы назначаете longs массиву, и, несмотря на ваш модуль, PyPy, похоже, не замечает, что число все еще вписывается в машинное слово.

Я могу придумать два способа исправить это:

  1. Передайте значение, присвоенное bin2[n+1] - int().
  2. Используйте array.array().

Первый влияет только на PyPy2 и приводит к тому, что, по-видимому, стабильный объем памяти составляет ~ 800 МБ на моем Mac, тогда как последний, похоже, стабилизируется на уровне ~ 1,4 ГБ независимо от того, запускаю ли я его в PyPy2 или PyPy3.

Однако я не выполнил программу полностью, поэтому YMMV…

person Dan Villiom P. Christiansen    schedule 04.09.2018