はじめに

Pythonのfor文は遅いからどんな処理をしているのか気になったのでバイトコードを調べてみた。
間違っている所があれば指摘して頂けると嬉しいです。

バイトコードとは？

Pythonはソースコードを一気に機械語にコンパイルするのではなく、一度バイトコードと呼ばれる中間言語にしている。
これはスタックベースのPythonの仮想マシンに対する命令群で一行ずつ実行される。
JavaもPythonと同じ形式で設計されている。

今回使用したプログラム

変数sに$1$を足す処理を$10^8$回する。

def main():
    s = 0
    for _ in range(100000000):
        s += 1

if __name__ == "__main__":
    main()

バイトコードの処理を追う

main関数のバイトコード

  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               0 (s)

  3           4 LOAD_GLOBAL              0 (range)
              6 LOAD_CONST               2 (100000000)
              8 CALL_FUNCTION            1
             10 GET_ITER
        >>   12 FOR_ITER                12 (to 26)
             14 STORE_FAST               1 (_)

  4          16 LOAD_FAST                0 (s)
             18 LOAD_CONST               3 (1)
             20 INPLACE_ADD
             22 STORE_FAST               0 (s)
             24 JUMP_ABSOLUTE           12
        >>   26 LOAD_CONST               0 (None)
             28 RETURN_VALUE

変数や定数はスタックとは別の場所に保存される。
関数の__code__属性から確認できる。

main.__code__.co_consts  # (None, 0, 100000000, 1)
main.__code__.co_varnames  # ('s', '_')
main.__code__.co_names  # ('range',)

ブロックに分けて調べていく。
命令の詳細は公式ドキュメントを引用する。

変数sに0を代入する

  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               0 (s)

LOAD_CONST

co_consts[consti] をスタックにプッシュします。

STORE_FAST

TOS をローカルな co_varnames[var_num] の中に保存します。

s=0の行のバイトコード。LOAD_CONSTと書かれた行の 1 (0)は、1が引数で(0)がco_consts[1]の値を表している。
またTOSとは Top Of Stack のことでスタックの先頭のこと。
つまり、LOAD_CONSTで0をスタックにプッシュしてSTORE_FASTで1をPOPして変数sに代入している。

rangeの呼び出し

  3           4 LOAD_GLOBAL              0 (range)
              6 LOAD_CONST               2 (100000000)
              8 CALL_FUNCTION            1

LOAD_GLOBAL

co_names[namei] という名前のグローバルをスタック上にロードします。

CALL_FUNCTION

Calls a callable object with positional arguments. argc indicates the number of positional arguments. The top of the stack contains positional arguments, with the right-most argument on top. Below the arguments is a callable object to call. CALL_FUNCTION pops all arguments and the callable object off the stack, calls the callable object with those arguments, and pushes the return value returned by the callable object.

rangeと100000000をスタックにプッシュして実行している。
rangeオブジェクトのインスタンスが返ってくる？

for文の実行

             10 GET_ITER
        >>   12 FOR_ITER                12 (to 26)
             14 STORE_FAST               1 (_)

GET_ITER

TOS = iter(TOS) を実行します。

FOR_ITER

TOS is an iterator. Call its __next__() method. If this yields a new value, push it on the stack (leaving the iterator below it). If the iterator indicates it is exhausted, TOS is popped, and the byte code counter is incremented by delta.

GET_ITERでイテレータの取得後、FOR_ITERでfor文の開始する。
__next__()を実行して値が取得できたら、スタックにプッシュする。
もし次の値がなくて正常に終了したら、その段階でTOSはイテレータなのでそれをポップしてカウンターを進める。
STORE_FASTはTOSをポップして変数_に代入している。

s+=1

  4          16 LOAD_FAST                0 (s)
             18 LOAD_CONST               3 (1)
             20 INPLACE_ADD
             22 STORE_FAST               0 (s)

INPLACE_ADD

インプレースの TOS = TOS1 + TOS を実行します。

ここはsと1をプッシュしてIPLACE_ADDで足し算をしている。
STORE_FASTで変数sに結果を格納する。

jump命令

24 JUMP_ABSOLUTE           12

JUMP_ABSOLUTE

バイトコードカウンタを target に設定します。

FOR_ITERにジャンプする。

return処理

        >>   26 LOAD_CONST               0 (None)
             28 RETURN_VALUE

RETURN_VALUE

関数の呼び出し元へ TOS を返します。

今回は特に戻り値を指定していないのでNoneを返す。

おわりに

これでスタックベースの大まかな処理とその流れがわかった。
for文が関係しているのは4～24でループ部分は12～24。
ただの足し算なのに命令の数が増えたな～と感じる。
バイトコードを確認するだけではfor文の速度が遅い原因を調べるのに無理があるので、CPythonの実装も見ていきたい。

参考にした記事