爲什麼使用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 += 1內環內（其中nums[j] = 1是）加入count = 0。 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位整數數組的形式存儲），而是使用一系列位（但它的代碼更多，因爲沒有標準的內置函數位數組）。

Answer 2

TL，DR;

作爲一個C程序，這將是一個內存綁定算法。然而，即使是jit編譯的pypy代碼也有相當多的開銷，並且操作不再是「免費」的。令人驚訝的是（或者不是），兩個sieve版本有不同的jit-code，第二個版本導致代碼變慢可能只是運氣不好。

---

如果是C，@Armin的答案是正確的。衆所周知，對於現代計算機/緩存和內存綁定代碼，如果我們跳過一個整數，並不重要 - 但所有的值都必須從內存中獲取，這是一個瓶頸。請參閱this article以獲得很好的解釋。

然而，我的實驗表明，非優化版本（sieve）比優化版本（sieve_var）稍快。時機還顯示，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秒，而對於10^8元素，則是0.65秒。這些數字可能因機器不同而不同，因此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秒。與0.45秒（爲了確保時間差不是僥倖，而不是由於某些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; 
} 

與gcc and -Os we get編譯：

 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-module我們可以看到JIT碼和：

1. 用於循環的一次迭代中，還有更多的操作比C-版本
2. 的版本sieve和sieve_par有很大的不同。我們可以使用use debugger to count the number of instruction迭代：24sieve和76-sieve_var只能處理每個第二個元素，所以關係實際上是24:38。

很難說，爲什麼在沒有調試pypy的情況下，兩個版本的jit-code差別很大。可能是運氣不好，sieve_par比較慢。