トップレベルのループと関数内のループの違い

動機

「競技プログラミングで Python を使う時は関数にしよう」という記事を見て、トップレベルに処理を記載した場合：

loop_toplevel.py

for i in range(10**7):
    pass

と、関数内に処理を記載した場合：

loop_function.py

def main():
    for i in range(10**7):
        pass
main()

で大きな性能差があることを知りました。実際に時間を測ってみると

$ python3 --version
Python 3.7.2
$ time python3 loop_toplevel.py
python3 loop_toplevel.py  0.66s user 0.02s system 95% cpu 0.712 total
$ time python3 loop_function.py
python3 loop_function.py  0.39s user 0.01s system 97% cpu 0.418 total

と確かに有意な差が出ることが確認できます。

この差異はどこから来ているのでしょうか？違いを理解するために、まずはコードを逆アセンブルして、Python VM上で実行されるバイトコードの差異を確認しましょう。

関数の逆アセンブル

「dis --- Python バイトコードの逆アセンブラ」を使うと、関数の逆アセンブルができます。関数の中に処理を書いたほうだと

>>> from loop_function import main
>>> type(main)
<class 'function'>
>>> import dis
>>> dis.dis(main)
  2           0 SETUP_LOOP              16 (to 18)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_CONST               1 (10000000)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 4 (to 16)
             12 STORE_FAST               0 (i)

  3          14 JUMP_ABSOLUTE           10
        >>   16 POP_BLOCK
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE
>>>

と逆アセンブルすることができます。

モジュールの逆アセンブル

モジュールを対象にして dis.dis を呼ぶと

>>> import loop_toplevel
>>> type(loop_toplevel)
<class 'module'>
>>> import dis
>>> dis.dis(loop_toplevel)
>>>

あれれ？何も表示されません。

dis.dis のヘルプを見ると、

Disassemble classes, methods, functions, and other compiled objects.

と説明されていて、モジュールが対象として書いてない代わりに、コンパイルしたオブジェクトが対象に入っています。

というわけで、ソースを読み込んでコンパイルしてみます。

>>> f = open('loop_toplevel.py')
>>> s = f.read()
>>> c = compile(s, 'loop_toplevel', 'exec')
>>> c
<code object <module> at 0x10af69930, file "loop_toplevel", line 1>

これでコンパイルしたものが得られたので逆アセンブルすると

>>> import dis
>>> dis.dis(c)
  1           0 SETUP_LOOP              16 (to 18)
              2 LOAD_NAME                0 (range)
              4 LOAD_CONST               0 (10000000)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 4 (to 16)
             12 STORE_NAME               1 (i)

  2          14 JUMP_ABSOLUTE           10
        >>   16 POP_BLOCK
        >>   18 LOAD_CONST               1 (None)
             20 RETURN_VALUE

と結果が得られました！

結果の比較

逆アセンブルした結果を見比べると

| loop_function.py | loop_toplevel.py |
|---|---|---|
| LOAD_GLOBAL | LOAD_NAME |
| STORE_FAST | STORE_NAME |

という違いがあります。

rangeに与える整数、すなわちループの回数を大きくすると、実行時間の差も大きくなることが見れるので、実行時間の差に効いているのはループ内、つまりFOR_ITERとJUMP_ABSOLUTEの間にあるSTORE_FASTとSTORE_NAMEの違いであることがわかります。

それぞれに対するVMの処理を比較すればもう少し詳細を理解できるはずですが、今回はバイトコードの差異まで見れたのでここまでにしておきます。

→ 「Python VMのプロファイル」でVMの処理のプロファイルをしてみました。