早期返却はなぜ他のものより遅いのですか？

Question

これはan answer I gave a few days backへのフォローアップの質問です。 編集：その質問のOPには、私が彼に投稿したコードを使用してthe same questionと尋ねたようだが、私はそれを知らなかった。謝罪。ただし、提供される回答は異なります！

>>> def without_else(param=False): 
...  if param: 
...   return 1 
...  return 0 
>>> def with_else(param=False): 
...  if param: 
...   return 1 
...  else: 
...   return 0 
>>> from timeit import Timer as T 
>>> T(lambda : without_else()).repeat() 
[0.3011460304260254, 0.2866089344024658, 0.2871549129486084] 
>>> T(lambda : with_else()).repeat() 
[0.27536892890930176, 0.2693932056427002, 0.27011704444885254] 
>>> T(lambda : without_else(True)).repeat() 
[0.3383951187133789, 0.32756996154785156, 0.3279120922088623] 
>>> T(lambda : with_else(True)).repeat() 
[0.3305950164794922, 0.32186388969421387, 0.3209099769592285] 

...または他の言葉で：

は、実質的に私はその観察else句は関係なく、トリガーされるif条件のかをより高速です。

私はそれが2つの異なるバイトコードと関係していると仮定しますが、詳細に確認/説明できる人はいますか？

編集：誰も私のタイミングを再現することはできないようですので、私のシステムにいくつかの情報を与えることが有用かもしれないと思った。私はデフォルトのPythonがインストールされたUbuntu 11.10 64ビットを実行しています。

>>> dis.dis(without_else) 
    2   0 LOAD_FAST    0 (param) 
       3 POP_JUMP_IF_FALSE  10 

    3   6 LOAD_CONST    1 (1) 
       9 RETURN_VALUE   

    4  >> 10 LOAD_CONST    2 (0) 
      13 RETURN_VALUE   
>>> dis.dis(with_else) 
    2   0 LOAD_FAST    0 (param) 
       3 POP_JUMP_IF_FALSE  10 

    3   6 LOAD_CONST    1 (1) 
       9 RETURN_VALUE   

    5  >> 10 LOAD_CONST    2 (0) 
      13 RETURN_VALUE   
      14 LOAD_CONST    0 (None) 
      17 RETURN_VALUE   

Answer 1

これは純粋な推測である、と私はチェックする簡単な方法を考え出したていない。ここで

Python 2.7.2+ (default, Oct 4 2011, 20:06:09) 
[GCC 4.6.1] on linux2 

は、Python 2.7での分解の結果である： pythonは、次のバージョン情報を生成し、それが正しいかどうか、私はあなたのための理論を持っています。

は、私はあなたのコードを試してみましたが、結果の同じを取得し、without_else()が繰り返しwith_else()よりわずかに遅いです：

>>> T(lambda : without_else()).repeat() 
[0.42015745017874906, 0.3188967452567226, 0.31984281521812363] 
>>> T(lambda : with_else()).repeat() 
[0.36009842032996175, 0.28962249392031936, 0.2927151355828528] 
>>> T(lambda : without_else(True)).repeat() 
[0.31709728471076915, 0.3172671387005721, 0.3285821242644147] 
>>> T(lambda : with_else(True)).repeat() 
[0.30939889008243426, 0.3035132258429485, 0.3046679117038593] 

は、バイトコードが同じであることを考慮すると、唯一の違いは、関数の名前です。特に、タイミングテストではグローバル名のルックアップが行われます。 without_else()の名前を変更してみて、違いが消える：

>>> def no_else(param=False): 
    if param: 
     return 1 
    return 0 

>>> T(lambda : no_else()).repeat() 
[0.3359846013948413, 0.29025818923918223, 0.2921801513879245] 
>>> T(lambda : no_else(True)).repeat() 
[0.3810395594970828, 0.2969634408842694, 0.2960104566362247] 

私の推測では、without_elseは、グローバル名前検索が少し遅くなりそうglobals()で何か他のものとのハッシュ衝突を持っていることです。

編集：

>>> [(k, hash(k) % 32) for k in globals().keys() ] 
[('__builtins__', 8), ('with_else', 9), ('__package__', 15), ('without_else', 8), ('T', 21), ('__name__', 25), ('no_else', 28), ('__doc__', 29)] 

ハッシュがどのように機能するかを明確にする：：without_elseは__builtins__とハッシュ衝突を持っていることに基づきので7つのまたは8キーを持つ辞書はおそらく、32個のスロットがあり

__builtins__ハッシュ値は-1196389688になり、テーブルサイズ（32）のモジュロを減らすと、テーブルの＃8スロットに格納されます。

without_elseハッシュ値を505688136に減らすと、モジュロ32が8になり、衝突が発生します。このPythonの計算を解決するには：我々は空きスロットを見つけ、このまで

j = hash % 32 
perturb = hash 

リピート：

j = (5*j) + 1 + perturb; 
perturb >>= 5; 
use j % 2**i as the next table index; 

それ17は次のインデックスとして使用することができます

で始まります。幸いにも、それは無料なので、ループは1回だけ繰り返されます。ハッシュテーブルサイズは2の累乗であるため、2**iはハッシュテーブルのサイズ、iはハッシュ値jから使用されるビット数です。

• スロットプロービング停止した場合には、空であり、我々は 値はテーブルではありません知っている：

  テーブルへの各プローブは、これらのものを見つけることができます。

• スロットは使用されていませんが、過去に使用されたスロットの場合は、上記のように計算された次の値 を試してみます。 （つまり、 がwithout_else対__builtins__の場合に何が起こるかだ）

• スロットがいっぱいですが、テーブルに格納されている完全なハッシュ値が 我々が探しているキーのハッシュと同じではありません。

• スロットがいっぱいで、キーと我々が見上げているオブジェクトは（このケースでは、彼らは短い文字列のでされる 同じオブジェクトであるかどうかを確認するために私たちが望む正確にハッシュ値、そしてPythonの チェックを持っています は識別子でも構いませんので、同一の識別子は全く同じ文字列の を使用します）。スロットがいっぱいになったとき

• は最後に、ハッシュは正確に一致したが、その後だけにして、同じオブジェクトではありません キーはPythonは平等のためにそれらを比較する をしようとします。これは比較的遅いですが、 という名前のルックアップは実際には起こらないはずです。