Pythonのfor文のバイトコードを軽く追ってみた

# はじめに

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

# バイトコードとは？

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

# 今回使用したプログラム

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

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

if __name__ == "__main__":
    main()
```

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

main関数のバイトコード

```bytecode
  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__`属性から確認できる。

```python
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の実装も見ていきたい。


# 参考にした記事

https://docs.python.org/ja/3/library/dis.html