python - 当没有分配新的内容时，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 的列表更改不会显着改变这一点)。当 python 2.7.13 运行 PyPy 5.10.0 时，程序很快达到 8 GB(我有多少 RAM)并卡住。即使使用 gc.collect() 调用，当 n 约为 3.5 * 10^7 时，程序也会耗尽内存。

这些内存使用量从何而来？唯一较大的内存使用应该是将 bin2 初始化为 10^8 int 列表。假设 mul_inv 中的所有局部变量都被垃圾回收，那么没有其他事情会增加内存使用量。

Answer 1

糟糕，这是整数列表优化的一个糟糕情况。问题是它以整数列表开头:

bin2 = [0] * L

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

但问题是，很快，我们就在列表中存储了一个long。此时，我们需要将整个列表变成可以存储任何内容的通用类型。但!问题是我们看到了 1 亿个零，因此我们创建了 1 亿个 0 对象。除了列表本身的 800MB 之外，这会立即产生 3 GB 的内存压力。

如果我们像这样初始化列表，以便它确实包含 1 亿次相同的对象，我们可以检查问题是否不会发生:

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

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

bin2 = [1]

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

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