为什么这个改进的筛子和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.28s，而sieve_var(10**8)需要2.67s。我不认为pypy的热身时间是罪魁祸首，那么为什么sieve_var没有更少、更快的迭代呢？在标准python3.3中，sieve_var比预期的更快。在Windows8.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]]

使用python3.6，sieve_slice的运行速度比sieve快4倍，而使用pypy3 7.3.0，sieve的运行速度比sieve_slice快2倍。

Answer 1

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

要验证我的意思，请尝试使nums数组更加紧凑。我试着用nums[i // 2]访问它，假设i总是很奇怪，而且结果要快两倍。如果不使用Python列表(存储在32位PyPy上的32位整数数组)，而是使用一个位数组(但这是更多的代码，因为没有标准的内置位数组)，您可能会赢得更多。

Answer 2

TL，DR；

作为一个C程序，这将是一个内存绑定算法.然而，即使是jit编译的pypy代码也有相当大的开销，而且操作不再是“免费”的。令人惊讶的是(也许不是)，rhese的两个sieve版本有不同的jit-代码，可能只是运气不好，因为第二个版本导致代码变慢了。

“如果是C的话，”阿明的回答将是正确的。众所周知，对于现代计算机/缓存和内存绑定代码来说，跳过整数并不重要--尽管如此，所有的值都必须从内存中获取，这是一个瓶颈。有关一个很好的解释，请参见这篇文章。

然而，我的实验表明，非优化版本(sieve)略快于优化版本(sieve_var)。Timings还显示，sieve的最后一行[i for i in range(2, n) if nums[i] == 0]比sieve_var - return [2] + [i for i in range(3, n, 2) if nums[i] == 0]行执行得更快。

在我的机器上，0.45秒与0.65秒对应于10^8元素。这些数字可能因机器而异，因此，CPU速度较快、内存较慢的人很可能根本看不到任何差别。如果可以用“内存支配一切”来解释，那么我们应该能够看到，速度较慢的版本有更多的缓存丢失，而速度越快的版本就越少。

但是，通过运行valgrind --tool=cachegrind pypy sieveXXX.py，我们可以看到，缓存丢失的数量几乎没有任何差别，至少没有任何东西可以解释这种可观察到的差异。

让我们考虑一个稍微简单一些的版本，它显示出完全相同的行为--我们不保存素数，但只计算它们：

def sieve(n):
    ...
    res=0
    for i in range(2, n): 
          if nums[i] == 0:
              res+=1
    return res

def sieve_var(n):
    ...
    res=1
    for i in range(3, n,2): 
          if nums[i] == 0:
              res+=1
    return res

第一个版本更快：0.35秒。Vs.0.45 sec (为了确保时间差不是偶然的，也不是由于一些jit-预热，我将代码的最后一部分放入了for-循环中，得到的总是相同的时间)。

在进一步研究之前，让我们先看一下C-实现及其程序集

long long int sum(long long int *a, int n){
    long long int res=0;
    for(int i=2;i<n;i++)
       if(a[i]==0)
          res++;
    return res;
} 

用我们会得到编译

        movl    $2, %edx
        xorl    %eax, %eax
.L4:
        cmpl    %edx, %esi
        jle     .L1
        cmpq    $0, (%rdi,%rdx,8)
        jne     .L3
        incq    %rax
.L3:
        incq    %rdx
        jmp     .L4
.L1:
        ret

非常小，直接前进，只需要0.08秒在我的机器上。我的内存可以达到10 GB/s的速度，并且有8*10^8字节-所以基本上需要所有的时间来获取数据。

但是从这一点我们也可以看到，与C代码相比，pypy版本大约有0.25秒的开销。它是从哪里来的？通过使用vmprof-模块，我们可以看到jit-代码和：

1. 对于循环的一次迭代，比在C版本中有更多的操作。
2. sieve和sieve_par的版本非常不同。我们可以对迭代进行使用调试器计算指令数：24表示sieve，76-operations表示sieve_var，它只处理每一个元素，因此关系实际上是24:38。

很难说，为什么在没有调试pypy的情况下，jit-代码对于这两个版本如此不同。可能只是运气不好，sieve_par慢了一点。