为什么在PyPy中，对于这个筛子问题，0/1比False/True更快？

Question

为什么在PyPy中，对于这个筛子问题，0/1比False/True更快？

6

类似于为什么在Python3中使用True比使用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 更小，并且更适合放入缓存中，但是在 PyPy 中不支持使用 sys.getsizeof 和 vmprof 行剖析。我能获得的唯一信息是，sieve_num 的 <listcomp> 花费了 116 毫秒（总执行时间的 19%）而 sieve_bool 的 <listcomp> 花费了 450 毫秒（总执行时间的 40%）。

使用 Python 3.6.9 实现的 PyPy 7.3.1 在搭载有 Intel i7-7700HQ 和 24 GB RAM 的 Ubuntu 20.04 上运行。在 Python 3.8.10 下，sieve_bool 只比较慢一点。

- qwr

在Python 3.7.13（PyPy 7.3.9）上，布尔类型的相等比较似乎比整数更耗费时间，我猜可能是因为MRO中有一个以上的类型。具体表现为2.86秒和3.55秒。 - wim

@wim 我不知道Python如何做等式比较，但是即使像if not num[i]这样的写法仍然会影响性能。 - qwr

如果您真正寻求性能，可以在此处找到一些经过巧妙优化的筛子。但也许您只是对PyPy相对缓慢处理布尔值的技术原因感到好奇。 - wim

我的代码对于我的需求来说足够快（没有需要分段筛子）。我只是对 pypy 优化的黑魔法感兴趣。 - qwr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Armin Rigo · Accepted Answer

原因是PyPy使用了针对“64位整数列表”的特殊实现。它还有一些其他特殊情况，例如“浮点数列表”，“仅包含ASCII字符的字符串列表”等。目标主要是为了节省内存：64位整数列表的存储方式就像array.array（'l'）一样，而不是指向实际整数对象的指针列表。尽管列表本身的大小没有改变，但是您可以在不需要非常多的小附加整数对象同时存在的情况下节省内存。

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

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

现在，无论是在PyPy还是CPython（*），最快的方法可能是使用 array.array（'B'）而不是列表，这既避免了PyPy特定的问题，还使用更少的内存（如果您的数据结构包含10 ** 8个元素，则始终是性能优胜点）。

编辑：（*）不，事实证明CPython可能太慢了，以至于内存带宽成为限制因素。在我的机器上，使用字节时，PyPy可能快30-35％。另请参阅评论，了解一种将CPython从9倍减速到比PyPy慢3倍的hack，但通常会减慢PyPy。