はじめに
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の実装も見ていきたい。
参考にした記事