为什么这种改良的筛子会因为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)需要2.28秒,而sieve_var(10**8)需要2.67秒.我不认为pypy的预热时间是这里的罪魁祸首,那么为什么不是sieve_var,哪个迭代越来越少,越快？在标准的python 3.3 sieve_var中如预期的那样更快.在Windows 8.1上使用pypy 4.0.1 32bit.

编辑:作为测试,我count = 0在函数的开头添加count += 1了内部循环(在哪里nums[j] = 1).sieve(10**8)计数为242570202,而sieve_var(10**8)计数为192570204.因此,虽然计数不会减半sieve_var,但它的工作量却减少了.

Answer 1

我不确定为什么它在Windows上会稍微慢一些.在Linux上速度是一样的.但是,我可以回答为什么我们得到的速度大致相同.如果程序是用C语言编写的,答案是相同的,答案纯粹是在处理器级别.该程序绑定在访问列表的内存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位整数数组)来赢得更多,而是一个位数组(但由于没有标准的内置代码,所以代码更多)比特数组).