- Tail Call: 関数が返る直前に行われる関数呼び出し。Tail Call最適化が発生すると
jmp 命令が使われ、呼び出しスタックを削減する。
- 利点:
- スタックメモリ使用量を O(n) から O(1) に削減する。
- 関数呼び出しの性能オーバーヘッドを取り除き、効率的な反復制御構造として利用できる。
インタプリタループの問題点
- 問題点:
- 関数が大きくなり制御フローが複雑になるほど、重要なデータをレジスタに保持しにくくなる。
- 高速パスと低速パスが混在すると、コード品質が低下する。
Tail Callを活用したインタプリタループ改善
- 解決策: Tail Callを使って各処理を小さな関数に分離し、各関数が次の処理をTail Callで呼び出す。
- 利点:
- レジスタ割り当てを制御できる。
- 高速パスと低速パスを分離してコード品質を維持できる。
- 独立した命令シーケンスを最適化できる。
限界
- 非Tail Callが存在する場合の問題: 非Tail Callがあるとスタックフレームが生成され、データがスタックに保存されて性能が低下する。
- 複雑な例外処理: 例外処理が複雑な場合、コードの重複と複雑さが増す。
- 移植性の問題:
musttail 属性は標準ではないため、すべてのコンパイラでサポートされているわけではない。
GN⁺の要約
- Tail Call最適化は性能向上に重要な役割を果たし、特にProtobufパースで大きな成果を示す。
- この技術は、Cで書かれた主要言語インタプリタ（Python、Ruby、PHP、Luaなど）にも適用できる。
musttail 属性の移植性の問題は解決すべき課題である。- 類似の機能を提供するプロジェクトとして、LuaJIT、wasm3 WebAssemblyインタプリタなどがある。
1件のコメント
Hacker Newsのコメント
C標準の提案書には、
return goto (expression);という形式で末尾呼び出しが含まれている[[musttail]]を標準化するよりも、ローカルオブジェクトの寿命が保証され、広範なエスケープ解析を必要としないRust愛好家向けには、
becomeキーワードを追加する古いRFCがあったC++でインタープリタを高速化する方法は、主に computed goto を使うことだ
末尾呼び出しを使ってコンテキストを切り替える問題では、呼び出し規約を使う関数が必要になる
[[musttail]]属性が GCC、Visual C++、その他の人気コンパイラにも広がることを期待している[[musttail]]属性は GCC に追加されつつあるC++対応に触れつつ、C++では末尾呼び出しがほとんどないと指摘している
C++の
[[musttail]]関数で例外を投げたらどうなるのか気にしている単純な例では、良いコード生成のために
__attribute__((musttail))は必要ないと述べているトランポリンを使い、返された関数ポインタを外側のループで呼び出す方式の速度を気にしている
[[musttail]]でラップされた例外パスの例を明確にしてほしいという要望がある[[musttail]]がスタックフレームの構築とレジスタスピルを防ぐ理由を説明している