Blog Dice

Performance of the Python 3.14 tail-call interpreter

Nelson Elhage

Python 3.14の末尾呼び出しインタプリタの性能

原文は Nelson Elhage により に公開されました。 このブログを購読する

約1か月前、CPythonプロジェクトはバイトコードインタプリタ向けの新たな実装戦略をマージした。当初の注目を集めた結果は非常に印象的で、幅広いベンチマークにおいて多様なプラットフォームにわたり平均で10〜15%の性能向上を示していた。

残念ながら、本記事で詳述するように、これらの印象的な性能向上は主としてLLVM 19のリグレッションを偶然回避したことによるものだったことが判明した。より適切なベースライン（GCCやclang-18、あるいは特定のチューニングフラグを付けたLLVM 19など）と比較すると、正確な環境にもよるが、性能向上は1〜5%程度に縮小する。

tail-callインタプリタが発表されたとき、私は性能向上に驚き感心した一方で、戸惑いも覚えた。専門家というわけではないが、現代のCPUハードウェアやコンパイラ、インタプリタ設計については一通りの知識があり、なぜこの変更がそれほど効果的なのか説明がつかなかったのだ。好奇心が — そして少しばかりの執着心が — 湧き、何が起きているのかを理解しようと、数週間にわたって断続的に数十種類もの異なるPythonバイナリをコンパイルし、ベンチマークを取り、逆アセンブルした。本記事の報告はその成果である。

最後には、この状況をベンチマークや性能エンジニアリング、そしてソフトウェアエンジニアリング全般における課題のケーススタディとして振り返りたい。

また、はっきり述べておきたいが、私は今でもtail-callインタプリタは素晴らしい成果であり、真の高速化（当初期待されたほど劇的ではないにせよ）だと考えている。さらに、後述するように、従来のインタプリタよりも堅牢なアプローチでもあると楽観視している。Pythonチームの誰かを責めるつもりもまったくない。この種の混乱は非常によくあることだ — 私自身、これまで何度もベンチマークを誤解してきた — この点についても最後に考察したい。

加えて、LLVMのリグレッションの影響は本研究以前には知られていなかったようだ（そして本記事の公開時点ではバグはまだ修正されていなかったが、その後修正された）。その意味では、（本研究がなければ）代替案はclang-19以降でビルドされた場合、実際におよそ10〜15%遅かった可能性が高い。たとえば、Simon Willisonは10%の高速化を「実地で」再現しており、python-build-standaloneによるビルドを用いてPython 3.13と比較している。

性能測定の結果

以下が私の主要な測定結果だ。CPythonインタプリタのいくつかのビルドを、複数の異なるコンパイラや設定オプションでベンチマークした。マシンは2台、Hetznerで私が管理しているIntelサーバー（Raptor Lake i5-13500）と、私のApple M1 MacBook Airだ。これらのビルドは私のnix設定を使って再現できるが、これほど多くの要素を同時に管理する上で不可欠だった。

すべてのビルドでLTOとPGOを使用している。設定は次のとおりだ。

  • clang18: Clang 18.1.8でビルド、computed gotoを使用。
  • gcc（Intelのみ）: GCC 14.2.1でビルド、computed gotoを使用。
  • clang19: Clang 19.1.7でビルド、computed gotoを使用。
  • clang19.tc: Clang 19.1.7でビルド、新しいtail-callインタプリタを使用。
  • clang19.taildup: Clang 19.1.7でビルド、computed gotoに加え、リグレッションを回避するいくつかの-mllvmチューニングフラグを使用。

ベースラインとしてclang18を用い、pypeformance/pyperf compare_toが報告する全体的な「平均」を示している。完全な出力ファイルやレポートはGitHub上にある。

プラットフォームclang18clang19clang19.taildupclang19.tcgcc
Raptor Lake i5-13500（基準）1.09倍遅い1.01倍速い1.03倍速い1.02倍速い
Apple M1 MacBook Air（基準）1.12倍遅い1.02倍遅い1.00倍遅いN/A

tail-callインタプリタはclang-18と比較して依然として高速化を示しているが、clang-19への移行による速度低下に比べればはるかに小さいことがわかる。Pythonチームは（バグを考慮した上で）私よりも一部のプラットフォームでより大きな高速化を観測している。

お気づきかもしれないが、旧バージョンのClangでのtail-callインタプリタ（clang18.tcに相当するもの）はベンチマークしていない。tail-callインタプリタはClang 19で新たに追加されたコンパイラ機能に依存しており、以前のバージョンではテストできないのだ。この相互作用こそが、この話を非常にややこしくし、私が状況を確信を持って理解するまでにあれほど多くのベンチマークを要した大きな理由だと考えている。

LLVMのリグレッション

背景

古典的なバイトコードインタプリタは、whileループの中にswitch文を置いた構造になっており、例えば次のような形になる。

while (true) {
  opcode_t this_op = bytecode[pc++];
  switch (this_op) {
    case OP_IMM: {
      // push an immediate onto the stack
      break;
    }
    case OP_ADD: {
      // handle the add
      break;
    }
    // etc
  }
}

ほとんどのコンパイラはswitchをジャンプテーブルにコンパイルする — 各case OP_xxxブロックのアドレスを格納したテーブルを生成し、オペコードでインデックスを引き、間接ジャンプを行うのだ。

この形式のバイトコードインタプリタは、各オペコードの本体にジャンプテーブルのディスパッチを複製することで高速化できることが以前から知られている。すなわち、各オペコードをjmp loop_topで終えるのではなく、各オペコードが「次の命令をデコードしてジャンプテーブルを参照する」ロジックの独立したインスタンスを含むようにするのである。

現代のCコンパイラはラベルのアドレス取得をサポートしており、それらのラベルを「computed goto」で用いることで、このパターンを実装できる。そのため、CPythonを含む多くの現代的なバイトコードインタプリタ（tail-callの取り組み以前）は、次のようなインタプリタループを採用している。

static void *opcode_table[256] = {
    [OP_IMM] = &&TARGET_IMM,
    [OP_ADD] = &&TARGET_ADD,
    // etc
};

#define DISPATCH() goto *opcode_table[bytecode[pc++]]

DISPATCH();

TARGET_IMM: {
    // push an immediate onto the stack
    DISPATCH();
}
TARGET_ADD: {
    // handle the add
    DISPATCH();
}

LLVMにおけるcomputed goto

（生成されるコードではなく）コンパイラ自体の性能上の理由から、ClangとLLVMは内部的には実際には後者のコードにあるすべてのgotoを単一のindirectbr LLVM命令に統合してしまう。各オペコードはそこへジャンプすることになる。つまり、コンパイラは我々の苦労をわざわざ書き換え、switchベースのインタプリタと本質的に同じ制御フローグラフにしてしまうのだ。

そしてコード生成時に、LLVMは「末尾複製（tail duplication）」を行い、分岐を各箇所にコピーし戻して本来の意図を復元する。この一連の動きは、古いLLVMブログ記事で高水準に文書化されており、新しい実装の導入時に説明されている。

LLVM 19のリグレッション

この重複排除してからコピーし直すという一連の動作全体の理由は、技術的な事情により、多数のindirectbr命令を含む制御フローグラフの作成や操作が非常に高コストになり得るためだ。

特定のケースで壊滅的なスローダウン（やメモリ使用量の増大）を避けるため、LLVM 19ではtail duplicationパスにいくつかの制限が実装され、IRのサイズが一定の制限を超えて肥大化する場合には複製を中断するようになった。

残念ながら、CPythonではそれらの制限により、Clangはすべてのディスパッチジャンプを統合したままにしてしまい、computed gotoベースの実装の目的全体を台無しにしてしまった。このバグは別の言語実装によって最初に特定されたが、同様のインタプリタループを持つものの、CPythonに影響を与えていることは（私が調べた限りでは）知られていなかった。

性能への影響に加え、生成されたオブジェクトコードを逆アセンブルして異なる間接ジャンプの数を数えることで、このバグを直接観察できる。

$ objdump -S --disassemble=_PyEval_EvalFrameDefault ${clang18}/bin/python3.14 | \
  egrep -c 'jmp\s+\*'
332

$ objdump -S --disassemble=_PyEval_EvalFrameDefault ${clang19}/bin/python3.14 | \
  egrep -c 'jmp\s+\*'
3

さらなる奇妙な点

tail duplicationロジックの変更がリグレッションを引き起こしたことは確信している。修正すれば性能はclang-18並みに戻るからだ。しかし、リグレッションの大きさについては完全には説明がつかない。

歴史的に、バイトコードディスパッチを各オペコードに複製する最適化は、インタプリタを20%から100%まで高速化するとされてきた。しかし、分岐予測が改善された現代のプロセッサでは、より最近の研究ははるかに小さい2〜4%程度の高速化しか見いだしていない。

この2〜4%という数字は実際に検証できる。Pythonは従来型のインタプリタ、すなわち単一のswitch文を用いる方式を、設定オプション経由で今でもサポートしているからだ。次の表は、そのインタプリタ（以下の表で「.nocg」は「no computed gotos」の意）をベンチマークした結果だ。

ベンチマークclang18clang18.nocgclang19.nocgclang19
性能変化（基準）1.01倍速い1.02倍遅い1.09倍遅い

clang19.nocgはclang18よりわずか2%遅いだけなのに、ベースのclang19ビルドは9%も遅いことに注目してほしい。この「2%」を、オペコードディスパッチの複製だけによるコスト／効果のより公平な見積もりだと私は解釈しているが、もう一方の数字については完全には理解できていない。

computed gotoは本当に必要なのか？

先ほどclang19.nocgのベンチマークについて触れなかったが、clang19よりも速いとされていることにお気づきだろう。ここで、この話のさらなる、とても面白い展開が明らかになる。

先ほど、ClangとLLVMが次のように動作すると説明した。

  1. switchをジャンプテーブルと間接ジャンプにコンパイルする。これはcomputed gotoで手作業で作るものと非常によく似ている
  2. computed gotoを、単一のオペコードディスパッチを持つ古典的なswitchグラフに酷似した制御フローグラフにコンパイルする
  3. コード生成時にその変換を反転させ、ディスパッチを複製できる

これらの事実を合わせると、「そもそもswitchベースのインタプリタから出発して、コンパイラにtail duplicationをやらせれば同じ効果が得られるのではないか？」という疑問が浮かぶかもしれない。

そして実際、答えはYesだ。

clang-18（あるいは適切なフラグを指定したclang-19）は、「古典的な」switchベースのインタプリタを与えられると、いずれにせよ各オペコード本体にディスパッチロジックを複製する。先ほどのobjdump | grepによるテストを用いて、同じビルドについて間接ジャンプの数を示したのが次の表だ。

ベンチマークclang18clang18.nocgclang19.nocgclang19
間接ジャンプの数33230633

したがって、「computed goto」インタプリタ全体が（少なくとも現代のClangにとっては）まったく不要な複雑さだったと主張する余地もある。コンパイラは同じ変換を自前で実行する能力が十分にあるし、（どうやら）computed gotoを使ってもそれが保証されるわけですらないのだ。

とはいえ、GCCでもテストしたところ、GCC（少なくとも14.2.1時点では）はswitchを複製しないが、computed gotoを用いた場合には期待通りの動作を実装する。少なくともそのケースでは期待された挙動が確認できる。

修正

LLVMプルリクエスト114990は本記事の公開直後にマージされ、リグレッションを修正した。マージ前にベンチマークして、期待通りの性能が回復することを確認できた。

その修正以前のリリースについては、リグレッションを引き起こしたPRが、tail duplicationが中断される閾値を選択する調整可能なオプションを追加していた。clang-19では単純にその制限を非常に大きな数に設定することで、同様の挙動を復元できる1。

考察

率直に認めると、私はこのテーマにかなり見事に「nerdsnipe」され、必要以上に深く潜ってしまった。とはいえ、そうしたからこそ、ソフトウェアエンジニアリングや性能エンジニアリング一般に敷衍できる興味深い教訓や考察がいくつも得られたと考えており、ここでそれらを抽出し、考察してみたい。

ベンチマークについて

システムを最適化する際、通常は何らかのベンチマーク群とベンチマーク手法を構築し、提案された変更をそれらのベンチマークを用いて評価する。

あらゆるベンチマーク群やベンチマーク手順は、（しばしば暗黙のうちに）私が「性能理論（theory of performance）」と呼んでいるものを内包している。性能理論とは、「どの変数がどのような形で性能に影響しうるか」や「ベンチマーク上の結果と『本番環境』での『真の』性能との関係は何か」といった問いに答える信念や仮定の集合だ。

tail-callインタプリタで実行されたベンチマークは、古いcomputed gotoインタプリタと比較して10〜15%の高速化を示した。それらのベンチマーク自体は正確であり、少なくとも私の知る限り、それらのビルド間の性能差を正確に測定していた。しかし、それらの特定のデータポイントを「tail-callインタプリタは一般的にcomputed gotoインタプリタより10〜15%速い」とか、さらには「tail-callインタプリタはユーザーの環境でPythonを10〜15%高速化する」といったより一般的な主張へと敷衍するためには、世界についてのさらなる仮定や信念を持ち込む必要がある。今回のケースでは話はより複雑で、それらの広範な主張は完全な一般性においては真ではなかったのだ。

（繰り返すが、Python開発者を責めるつもりはまったくない！ この種のことは本当に難しいし、やや不正確な結論に至る道は無数にある。より良い理解に到達するために、私は約3週間にわたる集中的なベンチマークと実験を要した。私が言いたいのは、これが非常に一般的な課題だということだ！）

ベースライン

この例は、ソフトウェアの性能だけでなく、他の多くの領域でも繰り返し現れる課題を浮き彫りにする。「何をベースラインとして比較するのか？」という問題だ。

ある問題に対して新しい解決策や手法を提案する際、通常は自分の手法を実行して何らかの関連する性能指標を生成する方法を持っている。

しかし、自分のシステムの指標が得られたら、それが良いものかどうかを判断するために何と比較すべきかを知る必要がある！ 何らかの絶対的な尺度で良いスコアを取ったとしても（そもそも評価に値する絶対的な尺度が存在すると仮定して）、既存の解決策より劣っていれば、おそらくあまり興味を引かない。

通常は「現在知られている最良のアプローチ」と比較したいところだ。しかし、時にはそれが難しいこともある！ 現在のアプローチを理論的には理解していても、実践的に適用する専門家であるとは限らない。ソフトウェアの文脈では、OSやコンパイラのオプション、その他のフラグをチューニングするといったことがこれに当たるかもしれない。現行の最良アプローチには公開されたベンチマークがあるかもしれないが、それらが必ずしも自分にとって適切とは限らない。たとえば、何年も前の古いハードウェアで公開されたものかもしれず、公開されている数値と直接比較できないかもしれない。あるいは、再現するには手の届かない規模でテストが実行されていたかもしれない。

私は現在Anthropicで機械学習に携わっているが、機械学習の論文ではこのことを常々目にする。ある論文が何らかのアルゴリズムの改善やその他の進歩を主張して出てくると、我々の研究者がまず尋ねるのは「何をやったのか？」ではなく「何をベースラインとして比較したのか？」であることが多い。適切にチューニングされていないベースラインと比較すれば、印象的な結果に見せるのは簡単であり、その観察結果が、うたわれる改善のかなりの割合を説明してしまうことが驚くほど多いのだ。

ソフトウェアエンジニアリングについて

私にとってもう一つのハイライトは、私たちのソフトウェアシステムがどれほど複雑で相互に絡み合っており、どれほど急速に変化し、そのすべての部品を把握することがいかに困難かということだ。

もし1か月前に、LLVMのリリースがCPythonに10%の性能リグレッションをもたらし、誰も5か月間気づかなかった可能性を見積もってほしいと尋ねられていたら、かなりありそうもない事態だと答えただろう！ どちらも広く使われているプロジェクトであり、どちらも性能をかなり気にかけているのだから、「きっと」誰かがテストして気づくだろうと。

そしておそらく、その特定の状況自体は確かに起こりにくいものだったのだろう！ しかし、世の中には非常に多くのソフトウェアプロジェクトがあり、それぞれが急速に動き、互いに依存し、また多くの他プロジェクトに利用されているため、何らかの「あのような」リグレッションが、ほぼ常時発生することは実質的に不可避なのだ。

最適化コンパイラ

computed gotoインタプリタをめぐる一連の経緯は、オプティマイザや最適化コンパイラをめぐる繰り返し現れる緊張関係や未解決の問いを浮き彫りにしており、分野としてまだ合意された答えを持っていない問題でもある。

一般的に、コンパイラにはプログラマの意図を尊重し、書かれたコードをその意図を保つ形でコンパイルすることが期待されている。

しかし同時に、コンパイラにはコードを最適化し、より高速に実行するために潜在的に複雑で直感に反する方法で変換することも期待されている。

これらの期待は緊張関係にあり、コンパイラに対して「なぜ」さまざまな方法でコードを書いたのか、そして特定の出力を意図的に引き起こそうとしたのか、あるいは性能に関わる何らかの判断を下したのかどうかを説明するためのパターンやイディオムが不足している。

コンパイラが通常保証するのは、書いたコードと「同じ振る舞い」をするコードを出力することだけであり、性能はその保証の上に成り立つベストエフォート的な機能に過ぎない。

こうして我々は、clang-19がcomputed gotoインタプリタを「正しく」コンパイルする — 生成されたバイナリが期待通りの同じ値をすべて生成するという意味で — 一方で、最適化の意図とは完全に相反する出力を生成するという奇妙な世界に行き着く。さらに、コンパイラの他のバージョンが「素朴な」switch()ベースのインタプリタに最適化を適用し、ソースコードを書き換えることで「意図した」のとまったく同じ最適化を実装している例も見てきた。

振り返ってみると、ソースコードレベルでの「computed goto」インタプリタと、機械語レベルでの「ディスパッチの複製」は、ほぼ直交する概念であることがわかる！ 結果として得られる2×2のマトリクスのあらゆる組み合わせの例を見てきたのだ！ なぜなら、それらのpythonバイナリはすべて実行時に同じ値を計算するので、現行のツールではそれらの間の区別を一貫した形で語ることが本質的にできないからだ。

この混乱は、tail-callインタプリタ（およびその背後にあるコンパイラ機能）が、技術水準における真の、そして有用な前進を示していると私が考える理由の一つでもある。tail-callインタプリタはそのmusttail属性に基づいて構築されており、これは比較的新しい種類のコンパイラ機能を表す。musttailは、コンパイラが考える古典的な意味での「観測可能なプログラムの振る舞い」には影響しないが、むしろオプティマイザとの対話である。コンパイラが特定の最適化を行えることを要求し、もしそれらの最適化が行われなければコンパイルを失敗させるのだ。

私は、このフレームワークが、特に長期的にコンパイラが進化していく中で、性能に敏感なコードを書くためのより堅牢なスタイルになることを期待している。こうしたカテゴリの機能を用いた継続的な実験を楽しみにしている。

具体的には、computed gotoインタプリタを、インタプリタのwhileループに（仮の）[[clang::musttailduplicate]]属性のようなものを付与する形で置き換えることが可能ではないかと考えている。関連するIRやパスすべてに十分精通しているわけではないので、この提案に自信があるわけではないが、この実現可能性についてより詳しい誰かが意見を寄せてくれるかもしれない。

もう一つ：nixについて

最後に、このプロジェクトでnixがどれほど役に立ったかを強調して締めくくりたい。私はこの1年ほど個人のインフラにnixやNixOSを試してきたが、今回の調査ではまさに救世主となった。

この一連の実験を通じて、私は4つの異なるコンパイラ（gcc、clang-18、clang-19、clang-20）にわたり、数多くのコンパイラフラグの組み合わせを用いて、数十種類もの異なるPythonインタプリタをビルドしベンチマークしてきた。すべてを手作業で管理していたら正気を保てなかっただろうし、どのコンパイラとどのフラグがどのビルドに対応するのかを取り違えるといったミスを数多く犯していたことは間違いない。

nixを使うことで、これら並行するすべてのバージョンを整理して管理し、再現可能でhermeticなスタイルでビルドすることができた。非常に簡単に定義できる短い抽象化を書くことができ、nixストア内の特定のビルドがどのコンパイラとどのフラグでどこから来たのかを絶対的な確信を持って知ることができた。ヘルパー関数を作るための少しの作業の後、ビルドマトリクスの核となる定義は驚くほど簡潔になった。次にその一端を示す。

{
    base = callPackage buildPython { python3 = python313; };
    optimized = withOptimizations base;
    optLTO = withLTO optimized;

    clang18 = withLLVM llvmPackages_18 optLTO;
    clang19 = withLLVM llvmPackages_19 optLTO;
    clang20 = withLLVM llvmPackages_20 optLTO;

    clang18nozero = noZeroCallUsed clang18;
    clang18nocg = withoutCG clang18;

    clang19taildup = withTailDup clang19;
}

LLVMのカスタムバージョン（バグ修正パッチを当てたもの）をビルドし、そのコンパイラを使ってPythonをビルドすることさえできた。それに必要だったのはわずか10行ほどのコードだった。

とはいえ、すべてが順調だったわけではない。まず、nixは必然的に、「普通の人」がソフトウェアを使う方法と比べてさまざまな点で「風変わり」であり、その風変わりさの一部が、気づかない形でベンチマークや結論の一部に影響を与えたのではないかと心配している。たとえば、早い段階で、nixがデフォルトで特定のハードニングフラグを使ってプロジェクトをビルドしており、それがtail-callインタプリタに不釣り合いな影響を与えることを発見した。この件は対処したが、他にもあるだろうか？

加えて、Nixは信じられないほど拡張性とカスタマイズ性に優れているが、特定のカスタマイズをどう行うかを理解するのは本当に険しい道のりで、多くの試行錯誤やソースコードの読解を伴う。私のパッチ適用済みLLVMビルドは最終的にはかなり短くきれいなものになったが、そこに至るまでにはnixpkgsのソースコードを大量に読み、十分に文書化されていない2つの拡張メカニズム（extendとoverrideAttrs — 他で使われるoverrideと混同しないように）を組み合わせ、さらに一度失敗した試みも経験した。その失敗ではlibllvmへのパッチは成功したものの、新しいclangがパッチ未適用のバージョンに対してサイレントにビルドされてしまった。

それでも、nixはここで明らかに非常に大きな助けとなり、全体として、この種のマルチバージョンベースの探索やデバッグを、他に想像しうるどんなアプローチよりもはるかに健全なものにしてくれたことは間違いない。

  1. このオプションの設定は、LTOを使用する場合にはやや複雑になることに注意してほしい。末尾複製はコード生成時に行われ、LTOビルドではコード生成は実際にはコンパイル時ではなくリンク時に行われる。したがって、フラグがコンパイラだけでなくlldにまで確実に渡されるようにする必要がある。私はPythonを./configure時に次の変数で設定することでうまく動作させることができた。

    ./configure [other flags] \
  "OPT=-g -O3 -Wall -mllvm -tail-dup-pred-size=5000" \
  "LDFLAGS=-fuse-ld=lld -Wl,-mllvm -Wl,-tail-dup-pred-size=5000"
    ↩︎

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。

コメント