この改良されたふるいは、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でpypy 4.0.1 32bitを使用する8.1。

編集：試験として、Iは（nums[j] = 1である）内側ループ内の関数の開始時count = 0とcount += 1を加えました。 sieve(10**8)は242570202をカウントし、sieve_var(10**8)は192570204をカウントします。したがって、カウントはsieve_varで半分にはなりませんが、「作業」は少なくなります。

Answer 1

なぜWindows上で少し遅いのかわかりません。 Linuxでは速度は同じです。しかし、私はなぜがほとんど同じ速度を得るのか答えることができます。プログラムがC言語で書かれていて、その答えが純粋にプロセッサのレベルであれば、答えは同じになります。このプログラムは、400または800MBのサイズのリストにアクセスするメモリI/Oにバインドされています。 2番目のバージョンでは、基本的に1つの余分なif nums[i] == 0チェックを避けています。ただし、この余分なチェックには何も必要ありません。CPUが以前の反復でキャッシュ内にnums[i - 1]をフェッチしただけで、次の反復ではnums[i + 1]が必要になるためです。 CPUはとにかくメモリを待っています。

私が言っていることを確認するには、numsアレイをよりコンパクトにしてみてください。私はnums[i // 2]でそれにアクセスしようとしました.iが常に奇数であると仮定し、結果は2倍速くなりました。おそらくPythonリスト（32ビットPyPy上に32ビット整数の配列として格納されている）を使わずに、ビットの配列（ただし、標準の組み込み関数がないためコードがもっとたくさんあります）ビットの配列）。

Answer 2

TL、DR;

Cプログラムとして、これはメモリに縛られたアルゴリズムです。しかし、ジットコンパイルされたpypyコードでさえ、かなりのオーバーヘッドを持ち、操作はもはや「無料」ではありません。驚いたことに（またはそうでないかもしれませんが）、2つのsieveバージョンのジットコードが違っています.2番目のバージョンの方がコードが遅くなるのはおそらく不運です。

---

もしそれがCであれば、@ Arminの回答は正しいでしょう。最新のコンピュータ/キャッシュとメモリバウンドコードでは、整数にジャンプするかどうかは関係ありませんが、すべての値をメモリからフェッチする必要があり、これはボトルネックであることはよく知られています。詳しい説明はthis articleを参照してください。

私の実験では、最適化されていないバージョン（sieve）は最適化されたバージョン（sieve_var）よりわずかに高速です。 sieveの最後の行がsieve_var - return [2] + [i for i in range(3, n, 2) if nums[i] == 0]よりも速く実行されるというタイミングも示されています。

私のマシンでは秒対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秒。対0.45秒（時間差が偶然ではなく、いくつかのjit-warmupのせいではないことを確かめるために、私はコードの最後の部分をfor-loopに置き、常に同じタイミングを得ました）。さらに進む前に

、のはgcc and -Os we getでコンパイルされた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秒かかります機械。私の記憶は10GB/sの速さで、8*10^8バイトがあるので、データを得るためには基本的に全時間が必要でした。

しかしこれからも、ピーピーバージョンはCコードと比較して約0.25秒のオーバーヘッドを持つことがわかります。それはどこから来たのですか？ vmprof-moduleを利用することにより、我々はJITコードと見ることができます：ループの1回の繰り返しのために

1. を、C-バージョン
2. でより多くの操作があるsieveとsieve_par用のバージョンは非常に異なっています。反復のuse debugger to count the number of instructionはsieveのためのと76の2番目の要素だけを扱うsieve_varの操作です。実際には、関係は24:38です。

pypyをデバッグしないと、両方のバージョンでjitコードが大きく異なる理由は分かりません。おそらく、それはちょうど不運である、sieve_parが遅いです。