なぜPypyの両端キューが遅いのですか？

Question

ここにProject Euler Problem 49の（やや乱雑な）試みがあります。

私は明らかに、dequeは良い選択ではありませんでした！私の考えは、メンバシップをテストするために素数集合を縮小すると、ループが加速することになります。しかし、setを使用する必要があり、要素の削除について心配してはならないことに気付いたとき、私は60倍のスピードアップを得ました。私はsetを使用することを考えて前に

from collections import deque 
from itertools import permutations 
from .sieve import sieve_of_erastothenes # my own implementation of the Sieve of Erastothenes 

primes = deque(prime for prime in sieve_of_erastothenes(10000) if prime > 1000 and prime != 1487) # all four-digit primes except 1487 
try: 
    while True: 
     prime = primes.popleft() # decrease the length of primes each time to speed up membership test 
     for inc in xrange(1,10000 + 1 - (2 * prime)): # this limit ensures we don't end up with results > 10000 
      inc1 = prime + inc 
      inc2 = prime + 2*inc 

      if inc1 in primes and inc2 in primes: 
       primestr = str(prime) 
       perms = set(''.join(tup) for tup in permutations(primestr)) # because permutations() returns tuples 
       inc1str = str(inc1) 
       inc2str = str(inc2) 
       if inc1str in perms and inc2str in perms: 
        print primestr + inc1str + inc2str 
        raise IOError # I chose IOError because it's unlikely to be raised 
            # by anything else in the block. Exceptions are an easy 
            # way to break out of nested loops. 
except IOError: 
    pass 

とにかく、私はPypyでそれを試してみました。

$ time python "problem49-deque.py" 
296962999629 

real 1m3.429s 
user 0m49.779s 
sys 0m0.335s 

$ time pypy-c "problem49-deque.py" 
296962999629 

real 5m52.736s 
user 5m15.608s 
sys 0m1.509s 

なぜこのコードでPypyが5倍以上遅くなったのですか？私は、dequeのPypyのバージョンが（setバージョンではより速く実行されるため）犯人だと推測しますが、なぜそれがあるのか​​わかりません。

Answer 1

遅い部分はinc1 in primes and inc2 in primesです。 PyPyがなぜ非常に遅いのかを見ていきます（基本的にパフォーマンスバグレポートのおかげで）。あなたが言及したように、コードは信じられないほど速く（PyPyとCPythonの両方で）---この場合、ループの直前のセットにprimesデキューをコピーすることによって行うことができます。

Answer 2

リスト内のメンバシップテストにリニアスキャンが含まれているため、deque（pythonのパフォーマンス特性を持つ）のメンバシップテストが遅くなることが予想されます。対照的に、setはメンバーシップテストに最適化されたデータ構造です。その意味で、バグはありません。