为什么 PyPy 中这个筛子的 0/1 比 False/True 快？

Question

类似于为什么在 Python3 中 use True 比 use 1 慢，但我使用 pypy3 而不是使用 sum 函数。

def sieve_num(n):
    nums = [0] * n
    for i in range(2, n):
        if i * i >= n: break
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [i for i in range(2, n) if nums[i] == 0]


def sieve_bool(n):
    nums = [False] * n
    for i in range(2, n):
        if i * i >= n: break
        if nums[i] == False:
            for j in range(i*i, n, i):
                nums[j] = True

    return [i for i in range(2, n) if nums[i] == False]

sieve_num(10**8)需要 2.55 秒，而sieve_bool(10**8)需要 4.45 秒，这是一个明显的差异。

我怀疑它[0]*n在某种程度上比缓存更小[False]*n并且更适合缓存，但是sys.getsizeofPyPy 不支持 vmprof 行分析。我能得到的唯一信息是<listcomp>forsieve_num花费了 116 毫秒（总执行时间的 19%），而工具<listcomp>花费sieve_bool了 450 毫秒（总执行时间的 40%）。

在 Ubuntu 20.04 上使用 PyPy 7.3.1 在具有 24 GB RAM 的 Intel i7-7700HQ 上实现 Python 3.6.9。Python 3.8.10sieve_bool只是稍微慢一点。

Answer 1

原因是 PyPy 对“适合 64 位的整数列表”使用了特殊的实现。它还有一些其他特殊情况，例如“浮点数列表”、“仅包含 ascii 的字符串列表”等。目标主要是为了节省内存：64 位整数列表的存储方式与 an 和array.array('l')not类似。指向实际整数对象的指针列表。您节省的内存不是列表本身的大小（列表本身不会改变），而是事实上您不需要同时存在大量的附加小整数对象。

“布尔列表”没有特殊情况，因为首先只有两个布尔对象。因此，在这种情况下，使用“64 位整数列表”之类的策略不会带来节省内存的好处。当然，我们可以做得更好，每个条目只存储一位，但这在 Python 中并不是一种真正常见的模式；我们只是一直没有时间去实施它。

那么为什么它会变慢呢？原因是，在“一般对象列表”的情况下，JIT 编译器每次从列表中读取项目时都需要生成额外的代码来检查对象的类型，并且每次将项目放入列表中时都需要生成额外的 GC 逻辑。列表。这不是很多代码，但就您而言，我猜它使内部循环生成的（极短）程序集的长度加倍nums[j] = 1。

目前，在 PyPy 和 CPython(*) 中，最快的可能是使用array.array('B')而不是列表，这既避免了 PyPy 特定的问题，又使用了更少的内存（如果您的数据结构包含 10** ，那么总是性能上的胜利） 8 个元素）。

编辑：(*) 不，事实证明 CPython 可能太慢而无法限制内存带宽。在我的机器上，使用字节时 PyPy 的速度可能快 30-35%。另请参阅有关将 CPython 速度从 PyPy 慢 9 倍到 3 倍的 hack 的评论，但它通常会减慢 PyPy 的速度。