Python3.11の新機能 Python 3.11の新機能(その3）関数呼び出しのインライン化

Python 3.11では、パフォーマンスチューニングの一環として、Python関数呼び出しのインライン化 が行われました。既存のPythonインタープリタのしくみを大きく変更する変更ですので、簡単に解説しておきます。

先に書いておきますが、今回行われた「関数呼び出しのインライン化」は、C/C++などの inline のように、ユーザ定義関数を呼び出し元で展開してオーバヘッドを削減するものではありません。また、Schemeなどにある末尾再帰の最適化でもありません。

cevalループ¶

Pythonインタープリタは、Python 3.11の新機能(その2） 特殊化適応的インタープリタ で解説したように、Pythonのソースコードをバイトコードへ変換し、順次実行します。このバイトコードを実行する関数はPythonインタープリタの心臓部であり、CPythonソースツリーのファイル Python/ceval.c で実装されていることから、通称 cevalループ と呼ばれています。

cevalループはC言語で書かれた大きな関数ですが、基本的にはバイトコードに従って処理を実行するための switch 〜 case 文からなる関数で、構造は比較的単純です。

Python3.10までのcevalループの擬似コードは、次のように書けます。

ceval_loop(byte_codes) {
    // 処理が終了するまで繰り返す
    while (not finished)  {
        byte_code = get_next_byte_code(byte_codes) // 次のバイトコードを取得
        switch (byte_code) {
            case 足し算: do_add(); break;
            case 引き算: do_sub(); break;
            case ...
        }
    }
}

関数呼び出し¶

さて、次の関数 foo()は、関数 bar() を呼び出すだけのPython関数です。

def foo():
    bar()
    return

def bar():
    return

Pythonインタープリタが関数 foo() を実行するとき、まずこの関数をバイトコードに変換し、cevalループで実行します。この時のcevalループの処理は、次のようになっています。

ceval_loop(byte_codes) {
    // 処理が終了するまで繰り返す
    while not finished {
        byte_code = get_next_byte_code(byte_codes) // 次のバイトコードを取得
        switch byte_code {
            case 関数呼び出し:
                ceval_loop(bar)  // ceval_loop()で関数barを実行する
                break;

            case return文:  // return文で呼び出し元に復帰する
                return

            case ...
        }
    }
}

cevalループがPythonの関数を呼び出すとき、cevalループは再帰的にcevalループを呼び出して、対象のPython関数を実行します。呼び出した関数(ここでは関数 bar())がさらに関数を呼び出す場合は、ふたたびcevalループを再帰的に呼び出します。

次の関数 foo() は bar() を呼び出し、bar() は更に baz() を呼び出します。

def foo():
    bar()   # 再帰的にceval_loop(bar)を呼び出す
    return

def bar():
    baz()   # 再帰的にceval_loop(baz)を呼び出す
    return

def baz():
    1 + 1
    return

f()  # ceval_loop(foo)を呼び出す

このとき、cevalループ関数の呼び出し関係は次のようになります。

-> ceval_loop(foo)
    -> ceval_loop(bar)
        -> ceval_loop(baz)
             1 + 1 を実行
        <-   return
    <-  return
<-  return

関数呼び出しのインライン化¶

このように、Python3.10までは、Pythonの関数を呼び出すときには再帰的にcevalループ関数を呼び出していました。

3.11からは大きくcevalループが大きく修正され、関数を呼び出すときにはcevalループを呼び出すのではなく、関数の実行情報のみを更新する方法に変更されました。

前置きが長くなりましたが、これが 関数呼び出しのインライン化 と言われている改善の正体です。

あたらしいcevalループは次のようになります。

ceval_loop(byte_codes) {
    top:

    // 処理が終了するまで繰り返す
    if (finished) {
      return
    }
    byte_code = get_next_byte_code(byte_codes) // 次のバイトコードを取得
    switch (byte_code) {
        case 足し算:
            do_add();
            goto top;

        case 関数呼び出し:
            実行中のバイトコードを次に実行する関数に設定;
            goto top;

        case return文:
            実行中のバイトコードを呼び出し元の関数に設定;
            goto top;

        case ...
    }
}

「cevalループ」と言いながら、ループブロックがなくなって goto 文だけになってしまいましたが、これにより、関数の呼び出しや初期設定のコストを軽減し、パフォーマンスが大きく向上しました。

ベンチマークとして、関数の呼び出し性能を計測する際に利用される 竹内関数 を実行してみましょう。

def tak(x, y, z):
    if x <= y:
        return z
    return tak(
        tak(x-1, y, z),
        tak(y-1, z, x),
        tak(z-1, x, y))

次の環境で実行します。

• MacBook Pro(16 inch, 2019)
• 2.4 GHz 8コアIntel Core i9
• 64 GB 2667 MHz DDR4
• macOS Monterey 12.3
• Python 3.10.6 (v3.10.6:9c7b4bd164, Aug 1 2022, 17:13:48) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin
• Python 3.11.0rc1 (v3.11.0rc1:41cb07120b, Aug 5 2022, 11:44:46) [Clang 13.0.0 (clang-1300.0.29.30)] on darwin

~ python3.10 -m timeit -s "import tak" "tak.tak(18, 9, 0)"
1 loop, best of 5: 1.24 sec per loop
~ python3.11 -m timeit -s "import tak" "tak.tak(18, 9, 0)"
1 loop, best of 5: 609 msec per loop

Python3.10と比較すると、1.24秒 -> 0.61秒と倍以上のパフォーマンス向上が確認できます。このパフォーマンス向上は関数呼び出しのインライン化だけではなく、Python3.11では関数呼び出し時のフレームオブジェクト生成の最適化など、他の多くの修正も貢献しています。

関数呼び出しインライン化の有効範囲¶

このパフォーマンス向上は、主にPythonのバイトコードインタープリタの改善によるものです。言葉を変えて言えば、Python言語のプログラムがcevalループを使って関数を呼び出した場合に有効なパフォーマンスチューニングです。

しかし、Pythonの関数やメソッドはPython言語だけで書かれているわけではありません。多くの関数やメソッドはC言語で書かれた組み込み関数で、Python言語から利用できるようになっています。こういった組み込み関数がPythonの関数を呼び出す場合はかならずcevalループの呼び出しが行われ、今回のパフォーマンス向上の恩恵は受けられません。

例えば、次のようにリストの要素を、それぞれの値が奇数なら1、偶数なら0に変換する、Python言語の関数を実行してみましょう。

def is_odd(d):
    return d % 2

def to_flags(L):
    ret = []
    for e in L:
        ret.append(is_odd(e))
    return ret

この処理は、Python3.11では大きく高速化します。

$ python3.10 -m timeit -s "import to_flags" "to_flags.to_flags(range(100000))"
20 loops, best of 5: 11 msec per loop
$ python3.11 -m timeit -s "import to_flags" "to_flags.to_flags(range(100000))"
50 loops, best of 5: 6.68 msec per loop

同じ処理を、Pythonの組み込み関数 map で実装してみましょう。

def is_odd(d):
    return d % 2

def to_flags_map(L):
    return list(map(is_odd, L))

この処理では、Python3.11でほとんど高速化されていません。

$ python3.10 -m timeit -s "import to_flags2" "to_flags2.to_flags_map(range(100000))"
50 loops, best of 5: 6.12 msec per loop
$ python3.11 -m timeit -s "import to_flags2" "to_flags2.to_flags_map(range(100000))"
50 loops, best of 5: 6.03 msec per loop

また、Python3.10では、ループによる to_flags() と map() を使った to_flags_map() では to_flags_map() のほうがかなり高速ですが、Python3.11ではあまり差がありません。

これは、Python3.11では関数呼び出しのインライン化や バイトコードの特殊化 など、Python言語で記述された処理の最適化が大きく進んでいますが、map() はC言語で実装された組み込み関数であるため、その影響をほとんど受けていないためです。

Pythonのループと map() のパフォーマンス差がこの程度であれば、パフォーマンス向上を目的とした map() の利用はあまり必要なくなるかもしれません。

これまで高速化のためにいろいろな処理がC言語で書かれていましたが、近い将来、Pythonの高速化が進むと、最適化しやすいPythonで書いたほうが読みやすくより高速になる、という時代が来るのかもしれません。

もう一つ、Python3.11の最適化が効果を発揮しない例を紹介しましょう。

class C:
    @property
    def x(self):
        return 1

この例では、クラス C にプロパティ x を定義しています。x を参照する速度を測ってみましょう。

$ python3.10 -m timeit -s "from prop import C; c = C()" "c.x"
5000000 loops, best of 5: 46.1 nsec per loop
$ python3.11 -m timeit -s "from prop import C; c = C()" "c.x"
5000000 loops, best of 5: 42.5 nsec per loop

Python 3.10でも3.11でもパフォーマンスに大きな違いはありません。プロパティを使ったメソッド x() の呼び出しはC言語で書かれた property オブジェクトから呼び出されるため、あまり3.11でのチューニングの効果がないためです。

プロパティを使わず、通常のメソッドを呼び出した場合はどうでしょうか？

class C:
    def x(self):
        return 1

クラス C のメソッド x() の呼び出し速度を測定してみましょう。

$ python3.10 -m timeit -s "from meth import C; c = C()" "c.x()"
5000000 loops, best of 5: 51.4 nsec per loop
$ python3.11 -m timeit -s "from meth import C; c = C()" "c.x()"
10000000 loops, best of 5: 30.3 nsec per loop

Python3.11では、Python3.10よりも70%高速化しています。また、この場合は最適化が効果を発揮するため、プロパティの参照に比べて40%高速に参照できます。

再帰呼び出しとスタックオーバーフロー¶

前述のとおり、Python3.10までは、Pythonの関数がPython関数を呼び出したとき、C言語で書かれた関数であるcevalループが再帰的に呼び出されます。

C言語の関数は、呼び出すとコールスタックと呼ばれる領域のメモリを消費します。このコールスタックは有限で、比較的少ないサイズしか確保していません。このため、関数呼び出しのネストが深くなりすぎてコールスタックを使い果たすと、有名な スタックオーバーフロー によるエラーが発生してしまいます。

Pythonでは、スタックオーバーフローを避けるために、関数呼び出しのネストの深さを制限しています。この制限を超えて関数呼び出しを行うと、RecursionError 例外が発生します。

>>> def foo():
...     global n
...     n += 1
...     foo()
...
>>> n = 0
>>> foo()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in foo
  File "<stdin>", line 4, in foo
  File "<stdin>", line 4, in foo
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
>>> print(n)
999

デフォルトでは、関数呼び出しのネストが1000に達すると RecursionError が発生します。最大ネスト回数は、sys.setrecursionlimit で指定できます。

最大ネスト回数を 5000 として実行してみましょう。

>>> import sys
>>> sys.setrecursionlimit(5000)
>>> n = 0
>>> foo()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in foo
  File "<stdin>", line 4, in foo
  File "<stdin>", line 4, in foo
  [Previous line repeated 46 more times]
RecursionError: maximum recursion depth exceeded
>>> print(n)
4999

最大の呼び出しネストの深さが変更されているのがわかると思います。

指定可能な最大再帰回数は実行環境や処理によって大きく変化するため、通常はsys.setrecursionlimit() の値は変更するべきではありません。しかし、再帰を利用すれば単純なアルゴリズムで行える処理などもあり、そういった場合には注意しながら最大再帰回数を変更する場合があります。

しかし、このネストの深さは無制限に大きくできるわけではありません。大きくしすぎると、前述のスタック領域を使い果たし、スタックオーバーフローによるエラーが発生します。

macOS上のPython 3.10.6 では、次のスクリプトで21392回のネストならスタックオーバーフローとはならず、RecursionErrorが発生します。

>>> import sys
>>> def foo(n):
...     if n:
...         foo(n-1)
...
>>> def test(limit):
...     sys.setrecursionlimit(limit)
...     foo(limit)
...
>>> test(21392)
Traceback (most recent call last):
  File "<stdin>", line 3, in foo
  File "<stdin>", line 3, in foo
  File "<stdin>", line 3, in foo
  [Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded

しかし、21393回繰り返すとセグメンテーションエラーが発生し、Pythonが終了してしまいます。

>>> test(21393)
[1]    93611 segmentation fault  python3.10

Python3.11の最大再帰回数¶

上の例で最大再帰回数を大きくしすぎるとスタックオーバーフローが発生するのは、Python3.10以前ではcevalループ関数が再帰的に呼び出されるためでした。

しかし、Python 3.11ではcevalループ関数は呼び出されず、スタック領域も消費されないため、メモリ容量が許す限り再帰できてしまいます。次の例のように、1億回再帰呼び出しを繰り返しても正常に終了します。

>>> import sys
>>> def foo(n):
...     if n:
...         foo(n-1)
...
>>> def test(limit):
...     sys.setrecursionlimit(limit+10)
...     foo(limit)
...
>>> test(100_000_000)

このようにスタック領域が消費されないのは、Pythonの関数がPythonの関数を呼び出した場合に限られる、という点に注意してください。Pythonでは多くの関数や型がC言語で実装されて組み込まれており、こういった関数や型のメソッドを呼び出すとスタックを消費します。

次の例では、自分自身を直接呼び出すのではなく、map関数 を使って再帰しています。

>>> import sys
>>> def foo(n):
...     if n:
...         next(map(foo, [n-1]))
...
>>> def test(limit):
...     sys.setrecursionlimit(limit+10)
...     foo(limit)
...
>>> test(28332)
>>> test(28333)
[1]    95208 segmentation fault  python3.11

map 関数はC言語で実装されているため、スタック領域を使用します。この例では28332回までの再帰呼び出しは可能でしたが、それ以上になるとセグメンテーションエラーが発生してしまいます。