python - 为什么这种改进的筛子使用 pypy 会变慢？

Question

def sieve(n):
    nums = [0] * n
    for i in range(2, int(n**0.5)+1):
        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_var(n):
    nums = [0] * n
    for i in range(3, int(n**0.5)+1, 2):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

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

在我的机器上，sieve(10**8) sieve_var(10**8) 需要 2.28 秒需要 2.67 秒。我不认为 pypy 的预热时间是这里的罪魁祸首，所以为什么不是 sieve_var ，迭代次数更少，速度更快？在标准 python 3.3 中 sieve_var正如预期的那样更快。在 Windows 8.1 上使用 pypy 4.0.1 32 位。

编辑:作为测试，我添加了 count = 0在函数的开头和 count += 1在内循环中(nums[j] = 1 所在的位置)。 sieve(10**8)计数 242570202 而 sieve_var(10**8)计数为 192570204。因此尽管 sieve_var 的计数没有减半，它正在做更少的“工作”。

为了好玩，这里有一个带有切片索引的版本:

def sieve_slice(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

使用 python 3.6，sieve_slice运行速度比 sieve 快约 4 倍, 但使用 pypy3 7.3.0, sieve运行速度比 sieve_slice 快约 2 倍.

Answer 1

我不确定为什么它在 Windows 上会稍微慢一些。在 Linux 上速度是一样的。但是，我可以回答为什么我们大部分的速度相同。如果程序是用 C 编写的，答案也是一样的，而且答案完全在处理器级别。该程序绑定(bind)在访问列表的内存 I/O 上，大小为 400 或 800MB。在第二个版本中，您基本上避免了一次额外的 if nums[i] == 0 检查。不过，这个额外的检查不需要任何费用，因为 CPU 在上一次迭代期间只是在其缓存中获取了 nums[i - 1]，并且在迭代期间需要 nums[i + 1]下一次迭代。无论如何，CPU 都在等待内存。

为了验证我在说什么，请尝试使 nums 数组更紧凑。我尝试用 nums[i//2] 访问它，假设 i 总是奇数，结果快了两倍。如果不使用 Python 列表(在 32 位 PyPy 上存储为 32 位整数数组)，而是使用位数组(但它的代码要多得多，因为没有标准的内置位数组)。