使い方 Pythonコードが関数内で高速に動作するのはなぜですか?




xrange 使い方 (3)

def main():
    for i in xrange(10**8):
        pass
main()

Pythonでこのコードが実行されます(注:タイミングはLinuxのBASHのtime関数で行われます)。

real    0m1.841s
user    0m1.828s
sys     0m0.012s

ただし、forループが関数内に配置されていない場合は、

for i in xrange(10**8):
    pass

それははるかに長い時間実行されます:

real    0m4.543s
user    0m4.524s
sys     0m0.012s

どうしてこれなの?


ローカル/グローバル変数のストア時間とは別に、 オペコード予測によって関数がより高速になります。

他の答えが説明するように、関数はループ内のSTORE_FASTオペコードを使用します。 関数のループのバイトコードは次のとおりです。

    >>   13 FOR_ITER                 6 (to 22)   # get next value from iterator
         16 STORE_FAST               0 (x)       # set local variable
         19 JUMP_ABSOLUTE           13           # back to FOR_ITER

通常、プログラムが実行されるとき、Pythonは各opcodeを順番に実行し、スタックを追跡し、各opcodeが実行された後にスタックフレームの他のチェックを実行します。 オペコード予測は、あるケースでは、Pythonが次のオペコードに直接ジャンプできるため、このオーバーヘッドの一部を回避することを意味します。

この場合、PythonはFOR_ITER (ループの先頭)を見るFOR_ITERSTORE_FASTが実行する次のオペコードであることを「予測」します。 その後、Pythonは次のオペコードを覗き見し、予測が正しければそのままSTORE_FASTにジャンプしSTORE_FAST 。 これにより、2つのオペコードを1つのオペコードに絞り込む効果があります。

一方、 STORE_NAMEオペコードは、グローバルレベルのループで使用されます。 このオペコードを見ると、Pythonは同様の予測をしません 。 その代わりに、ループが実行される速度に明白な意味を持つ評価ループの先頭に戻る必要があります。

この最適化に関する技術的な詳細については、 ceval.cファイル(Pythonの仮想マシンの「エンジン」)の引用文を以下にceval.cます。

いくつかのオペコードはペアになる傾向があり、したがって、第1のコードが実行されたときに第2のコードを予測することが可能になる。 たとえば、 GET_ITER後にFOR_ITERが続くことがよくあります。 FOR_ITER後には、 STORE_FASTまたはUNPACK_SEQUENCE が続きます。

予測の検証では、定数に対するレジスタ変数の高速テストが1回だけ実行されます。 ペアリングが良好だった場合、プロセッサ自身の内部分岐予測は成功確率が高く、その結果、次のオペコードへのオーバヘッドはほぼゼロになります。 成功した予測は、2つの予期しない分岐、 HAS_ARGテストおよびスイッチケースを含む評価ループを通る旅行を節約する。 プロセッサの内部分岐予測と組み合わせると、成功したPREDICTは、2つのオペコードを、それらが結合された1つの新しいオペコードであるかのように動作させる効果があります。

FOR_ITERオペコードのソースコードでは、 FOR_ITERの予測が行われる場所を正確にSTORE_FASTができます。

case FOR_ITER:                         // the FOR_ITER opcode case
    v = TOP();
    x = (*v->ob_type->tp_iternext)(v); // x is the next value from iterator
    if (x != NULL) {                     
        PUSH(x);                       // put x on top of the stack
        PREDICT(STORE_FAST);           // predict STORE_FAST will follow - success!
        PREDICT(UNPACK_SEQUENCE);      // this and everything below is skipped
        continue;
    }
    // error-checking and more code for when the iterator ends normally                                     

PREDICT関数はif (*next_instr == op) goto PRED_##opすなわち予測されたオペコードの先頭にジャンプします。 この場合、ここでジャンプします:

PREDICTED_WITH_ARG(STORE_FAST);
case STORE_FAST:
    v = POP();                     // pop x back off the stack
    SETLOCAL(oparg, v);            // set it as the new local variable
    goto fast_next_opcode;

ローカル変数が設定され、次のオペコードが実行されます。 Pythonは、終わりに達するまでイテレートを継続し、毎回成功した予測を行います。

Python wikiページには、CPythonの仮想マシンがどのように機能するかについての詳細があります。


グローバル変数よりもローカル変数を格納するほうが速い理由を尋ねるかもしれません。 これはCPython実装の詳細です。

CPythonは、インタプリタが実行するバイトコードにコンパイルされていることに注意してください。 関数がコンパイルされると、ローカル変数は固定長配列( dictではなく )に格納され、変数名はインデックスに割り当てられます。 これは、関数にローカル変数を動的に追加できないために可能です。 次に、ローカル変数を検索することは、文字通りリストへのポインタ検索であり、 PyObject refcountの増加は簡単です。

これをグローバルルックアップ( LOAD_GLOBAL )とLOAD_GLOBAL 。これは、ハッシュなどを含む真のLOAD_GLOBAL検索です。 ちなみに、これをglobal iものにしたいのであれば、 global iを指定する必要があります。スコープ内の変数に割り当てることができない場合は、コンパイラはSTORE_FASTを発行します。

ところで、グローバルルックアップはまだかなり最適化されています。 属性ルックアップfoo.bar本当に遅いものです!

ここでは、ローカル変数の効率に関する小さなillustrationがあります。


関数の内部では、バイトコードは次のようになります。

  2           0 SETUP_LOOP              20 (to 23)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_FAST               0 (i)

  3          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               0 (None)
             26 RETURN_VALUE        

トップレベルでは、バイトコードは

  1           0 SETUP_LOOP              20 (to 23)
              3 LOAD_NAME                0 (xrange)
              6 LOAD_CONST               3 (100000000)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                 6 (to 22)
             16 STORE_NAME               1 (i)

  2          19 JUMP_ABSOLUTE           13
        >>   22 POP_BLOCK           
        >>   23 LOAD_CONST               2 (None)
             26 RETURN_VALUE        

違いは、 STORE_FASTSTORE_FASTよりも高速です(!)ことSTORE_NAME 。 これは、ある関数では、 iはローカルですが、トップレベルではグローバルです。

バイトコードを調べるには、 disモジュールを使います 。 私は関数を直接解体することができましたが、 compile組み込み関数を使用しなければならなかった最上位コードを逆アセンブルしました。





cpython