PyPy中埃氏筛用0/1为何比False/True更快？

我实现了两个埃氏筛法函数，一个用整数0/1标记非质数，另一个用布尔值False/True标记，在PyPy3中测试发现性能差异明显：

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秒，其中列表推导部分耗时116毫秒，占总执行时间的19%
• 调用sieve_bool(10**8)耗时4.45秒，其中列表推导部分耗时450毫秒，占总执行时间的40%
• 在CPython 3.8.10中，两个函数的性能差异很小，仅sieve_bool略慢一点

可能的原因分析 #

核心差异大概率来自内存占用与缓存适配：

• [0]*n生成的整数列表，在PyPy的内存管理中可能采用更紧凑的连续存储格式，每个元素占用内存更小，更容易被CPU缓存命中，大幅降低内存访问开销
• 而[False]*n的布尔列表，PyPy未做同等程度的紧凑优化，或者布尔值的比较操作在JIT编译后的执行效率不如整数比较，尤其是在列表推导这种高频循环判断场景下，差异被进一步放大

测试环境：Ubuntu 20.04，Intel i7-7700HQ，24GB内存，PyPy 7.3.1（兼容Python 3.6.9）

内容的提问来源于stack exchange，提问作者qwr