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

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

0 голосов
/ 04 сентября 2018

Я не уверен, является ли это дубликатом других вопросов о памяти 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 ГБ и работает до конца (изменение списка Armin Rigo не меняет это существенно). В Python 2.7.13 с PyPy 5.10.0 программа быстро достигает 8 ГБ (сколько у меня оперативной памяти) и зависает. Даже при вызовах gc.collect() программе не хватает памяти, когда n составляет около 3,5 * 10 ^ 7.

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

Ответы [ 2 ]

0 голосов
/ 04 сентября 2018

УДОВОЛЬСТВУЕТ проблема в том, что вы назначаете long массиву, и, несмотря на ваше значение по модулю, PyPy, похоже, не замечает, что число все еще вписывается в машинное слово.

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

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

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

Я не запустил программу до конца, так что YMMV…

0 голосов
/ 04 сентября 2018

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

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.

...