当没有分配新内容时，Pypy内存使用量会增加

Question

我不确定这是否与其他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 GB并运行完成（Armin Rigo的列表更改不会显着改变）。使用运行PyPy 5.10.0的python 2.7.13，程序快速达到8 GB（我有多少RAM）并冻结。即使使用gc.collect()调用，当n大约3.5 * 10 ^ 7时，程序内存不足。

这个内存使用来自哪里？唯一的大内存使用应该是将bin2初始化为10 ^ 8 int列表。在假设mul_inv中的所有局部变量都是垃圾收集的情况下，没有别的东西应该增加内存使用量。

Answer 1

哎呀，这是整数列表优化的一个坏例子。问题是这是从一个int列表开始的：

bin2 = [0] * L

这在内部存储为一个int数组。它通常更紧凑，即使在这种情况下它不会改变任何东西---因为在CPython上它是一个包含相同对象L的0副本的列表。

但问题是，很快，我们将long存储在列表中。此时，我们需要将整个列表转换为可以存储任何内容的通用类型。但！问题是我们看到1亿个零，因此我们创造了1亿个0对象。这样就可以立即产生3 GB的内存压力，此外还有800 MB的内存压力。

如果我们像这样初始化列表，我们可以检查是否没有出现问题，因此它确实包含了相同对象的1亿倍：

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

也就是说，在您的示例中，您首先不需要列表包含1亿个元素。您可以将其初始化为：

bin2 = [1]

并使用bin2.append()。这使得程序可以更快地启动，并且在开始时不会占用大量内存。

请注意，PyPy3仍然使用比CPython3更多的内存。

Answer 2

AFAICT这里的问题是你要为数组分配long，尽管你的模数，PyPy似乎并没有注意到这个数字仍然适合机器字。

我可以想到两种方法来解决这个问题：

1. 通过bin2[n+1]传递分配给int()的值。
2. 使用array.array()。

前者仅影响PyPy2，并且导致我的Mac上看起来稳定的内存占用大约800MB，而后者似乎稳定在~1.4GB，无论我是在PyPy2还是PyPy3中运行它。

我没有完全完成程序，所以YMMV ......