2GB/s超でprotobufをパースする：Cでtail callを活用した高速インタプリタ設計（2021）
(blog.reverberate.org)- Clangに
musttailが追加されたことで、C系言語でも保証されたtail callを活用できるようになり、これをprotobufパーサに適用して2GB/s超の性能を実証 - 核心は、関数呼び出しを
callではなくjmpに近い形にし、連続呼び出しのスタック使用量を O(n) から O(1) に減らし、反復ループのように扱う点にある - protobuf wire formatはタグ/値を解釈し、任意順序のフィールドへ分岐する必要があるため、従来の
while+switch構造はインタプリタのopcodeディスパッチに似た最適化問題を持つ - upbの実験的パーサは、大きな関数1つではなく小さなパーサ関数群をtail callでつなぎ、高速パスでスタック使用・レジスタspill・プロローグ/エピローグを避ける
- この方式はnon-tail callが混ざるとコード品質が大きく悪化し、
musttailが非標準拡張であるという制約もあるため、高速パーサを実際に配布するには呼び出し規律と移植性対策が必要
Clang musttail が開いた高速protobufパース
- Clang mainブランチに
[[clang::musttail]]/__attribute__((musttail))文属性が追加され、C、C++、Objective-Cでtail call保証を得られる - ここでのtail callは関数型プログラミングの技法ではなく、パーサとインタプリタの分岐コストを下げる最適化ツールとして使われる
- protobufパースにこの技法を適用した結果、
upbpull/310で2GB/s超のパース性能を実証- 以前の最高水準より2倍以上速い結果として紹介された
- 複数の技法がともに寄与しているため、「tail callだけで2倍速くなった」という解釈は正しくない
- tail callは、この性能向上を可能にした主要要素の1つ
- その後の変化は A Tail Calling Interpreter For Python (And Other Updates) で扱っている
Tail callが反復構造のように動作する理由
- tail callとは、関数が戻る直前に実行する最後の関数呼び出し
- tail call最適化が適用されると、コンパイラは通常の
callの代わりにjmp命令を生成する- 新しいスタックフレームの作成や戻りアドレスの保存を省く
- 呼び出し元
f()は呼び出し先g()へ直接ジャンプする g()はf()を呼び出した関数へそのまま戻る
- この性質により、tail callは反復構造を置き換えられる
- 連続する
n回のtail callでも、スタック使用量が O(n) から O(1) に減る callのオーバーヘッドがなくなり、関数呼び出しを通常の分岐のように扱える
- 連続する
- このアイデアは新しいものではなく、Guy Steeleの1977年の論文と、1975〜1980年の「Lambda Papers」にまでさかのぼる
- Clangはすでに
-O2のような最適化ビルドでtail callを最適化できたが、従来の挙動はbest-effortに近かった- 非最適化ビルドでは実際の
callにコンパイルされる可能性が高い - tail callを反復構造として安全に使うには、すべてのビルドモードで最適化が保証される必要がある
musttailはこの保証を提供する
- 非最適化ビルドでは実際の
インタプリタループとprotobufパーサが抱える同じボトルネック
- LuaJITのMike PallはLuaJIT 2.xインタプリタをCではなくアセンブリで書き、これを高速インタプリタの主な理由と見ている
- Cコンパイラはインタプリタのメインループで、とくに2つの問題に直面する
- 関数が大きくなり制御フローが複雑になるほど、レジスタアロケータが重要なデータをレジスタに保持しにくくなる
- 高速パスと低速パスが同じ関数内に混ざると、低速パスが高速パスのコード品質まで低下させる
- protobuf wire formatもインタプリタに似た構造を持つ
- wire formatはタグ/値ペアの連続
- タグはフィールド番号とwire typeを含む
- タグは、そのフィールドデータをどうパースするかを示すopcodeのように動作する
- フィールド番号は任意の順序で現れ得るため、コードのどの部分へでもディスパッチできる準備が必要
- 従来のprotobufパーサは通常、
whileループの中にswitchを置く構造で、protobufが存在してきた期間の大半でこの方式が最高水準として使われていた - 実際のパースでは、wire typeの不一致、破損データ、バッファ終端への到達といった例外がほぼすべての段階で起こり得る
- 高速パスは可能な限り短く安定して保つ必要がある
- 難しいケースでは、より大きく複雑なfallbackコードが必要で、場合によってはout-of-line関数呼び出しも行う
Tail callベースのupbパーサ設計
- upbの実験的パーサは、大きなパース関数を1つ置くのではなく、各操作を小さな関数1つに分離する
- 各関数は次の操作をtail callで呼び出す
- x86-64呼び出し規約により、共通のパース引数はレジスタで渡される
- すべてのパース関数が同じ引数セットを使い、呼び出し間の値の移動を減らす
- 例の4バイト固定幅フィールド用パーサ関数は、次の流れで動作する
dataからフィールド情報をデコードする- wire typeが合わなければ
fallback()へMUSTTAIL returnする - タグをスキップしてメッセージにデータを保存する
- 次のタグを読んだあと、適切なフィールドパーサへ分岐する
dispatch()をtail callする
- Clangが生成したアセンブリは、高速パスでプロローグ・エピローグ・レジスタspill・スタック使用がない
- 終了地点は
fallbackまたはdispatchへのjmpだけ - 引数はすでに正しいレジスタにあるため、追加のパラメータ受け渡しコードも不要
- 終了地点は
- この構造は大きなインタプリタループを概念上は1つの複雑な関数と見なしつつ、実装上は基本ブロック単位の関数に分割し、tail callで制御フローを渡す
- 高速パスと低速パスを別関数に分けると、fallbackコードの変更が高速パスのコード品質を揺らす可能性が下がる
- 必要なら
noinlineでインライン化を防げる - 高速パスのアセンブリシーケンスを事実上固定できる
- 必要なら
LuaJITの例に見えるCコード生成品質
- LuaJITの例にも同じパターンを適用すると、手書きアセンブリに近い結果をCコードで得られる
- 例の
ADDVN関数は次の操作を行う- 命令からレジスタと定数インデックスを抽出する
- 型検査に失敗した場合はfallbackへ移動する
- レジスタ値に定数を加える
- 次のopcodeを読み、opcodeテーブルの関数へtail callする
- 生成されたアセンブリで残る改善点は比較的小さい
- 条件分岐の後に別の
jmpが生じる jmp qword ptr [rsi + 8*rax]の代わりにraxへロードしてからjmp raxを使う
- 条件分岐の後に別の
- こうした点は、Clangで改善可能な小さなコード生成上の課題として扱われる
non-tail callと移植性という制約
- この方式で最大の注意点は、関数内にnon-tail callが入るとアセンブリ品質が大きく悪化すること
- non-tail callが1つあるだけでスタックフレーム生成が強制される
- 多くのデータがスタックへspillされ得る
- これを避けるには、他の関数呼び出しをインライン化するか、tail callだけで行う規律が必要
- protobufパースではvarint処理が代表的な難点
- 一般的で高速なケースは1バイトvarint
- より長いvarintはエラーではないが、一般的ではないケース
- この例外処理をinlineすると、高速パスのコード品質が悪化し得る
- fallback関数へtail callすると、処理後に元の操作を簡単に再開できないため、fallbackが操作を最後まで処理しなければならない
- その結果、コード重複と複雑さが生じる
- 2025-01-27の更新では、呼び出し規約でこの問題を緩和する方法が追加された
__attribute__((preserve_most))はfallback関数に使える呼び出し規約で、ほぼすべてのレジスタ保存責任をcallee側へ移し、spillコストをfallback側へ移動する- この属性に関連するClangクラッシュバグは2023年に修正済み
__attribute__((preserve_none))はtail calling関数に使える呼び出し規約で、レジスタ保存の負担をなくし、引数により多くのレジスタを使う- 2つの方式のうち
preserve_noneのほうが侵襲性が低く、より良い選択肢と評価されている
- もう1つの制約は、
musttailが非標準のコンパイラ拡張であること- GCC、Visual C++などへ広がり標準化されることが期待されるが、近い話ではない
musttailがない場合は、概念上のループ反復ごとに少なくとも1つの実際のreturnが必要- upbにはまだこのfallbackは実装されておらず、
musttailの利用可否に応じてdispatchへtail callするか単にreturnするマクロが必要になると予想される
upbでの適用状況と拡張可能性
- 2GB/s超のパーサは、Cで書かれた小さなprotobufライブラリである
upbに提出された - 該当コードは完全に動作し、protobuf conformance testをすべて通過するが、執筆時点ではどこにもrolloutされていなかった
- C++版protobufには、この設計は実装されていない
- その後、
upbがmusttailを使うよう更新されたことで、高速パーサをプロダクション化する大きな障壁の1つが取り除かれた - 同じ技法は、Cで書かれた主要な言語インタプリタであるPython、Ruby、PHP、Luaなどにも大きな性能上の利点をもたらし得る
1件のコメント
Hacker News の意見
C 標準の提案には末尾呼び出し用の構文があり、形は
return goto (expression);です標準の
[[musttail]]より気に入っている点は、ローカルオブジェクトの寿命が終了することが保証される点です。そのため、広範なエスケープ解析なしでも実装可能になります[0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...
return gotoがなぜより実装しやすいのか気になります。[[musttail]]も見たところ、ローカルオブジェクトの寿命を終了させるように見えますざっと見たところ、末尾位置で呼び出される関数は呼び出し先と同一の型でなければならないとされています。戻り値の変換が不要で、引数渡し領域と呼び出し規約が維持されることを保証するための条件です
私が Clang に実装した
[[musttail]]についてよく見かけた不満は、この制約が不必要に厳しいというものです。一部のアーキテクチャでは、型が完全に一致していなくても末尾呼び出しを許可します: https://github.com/llvm/llvm-project/issues/54964「ではコードが移植不能になる」という指摘は正しいですが、末尾呼び出し最適化自体が本質的に移植可能ではありません。たとえば末尾呼び出し拡張のない WASM のように、対象によっては根本的に末尾呼び出し最適化をサポートしていないものがあります
必ず入れるべき変更や追加、さらには明確化すべきアイデアもあるので期待はしていますが、C++ の攻撃的な更新サイクルは結局、こぶの上にさらにこぶを継ぎ足したような形になった気がします
特に、機能同士が予想よりずっと早い段階で悪い相互作用を起こす場合が問題です。標準化プロセスが根拠文書だけに頼らず、大規模で多様なコードベースで機能を十分にテストしながら、非常に保守的に選択してほしいです
Rust に関心があるなら、保証された末尾呼び出し最適化を提供する
becomeキーワードを追加しようとした古い RFC がありますもともとは 2018 エディションの目標に集中するため延期され、その判断は正しかったのですが、最近この構想が再検討されました。戻ってくる可能性もあります
[0]: https://github.com/rust-lang/rfcs/pull/1888
[1]: https://github.com/rust-lang/rfcs/pull/3407
インタプリタが C++ で通常このような速度向上を得る方法は、computed goto を使うことです。そうすると、ある opcode から次の opcode へ進む経路に呼び出し規約関連のノイズがありません
computed goto 方式や末尾呼び出し方式が古典的な
switchループより速い主な理由は、分岐予測器の負担を減らすためです。静的に opcode ごとに 1 つの間接分岐が生じ、静的にたった 1 つの間接分岐しかない構造ではなくなります各関数が小さく、重要な変数を引数として受け取るなら、レジスタ割り当てははるかに脆弱でなくなります
ただ、インタプリタのサイズが大きくなってもその話が引き続き正しいのかは気になります
コンテキスト切り替えに末尾呼び出しを使ううえで残る問題は、呼び出し規約を使わなければならない関数を利用する点です。残念ながら、関数終了時に状態を復元するためにレジスタを無駄にします
詳しい分析と中間コンパイラを使う代替案は LuaJIT リメイクのブログにあります: https://sillycross.github.io/2022/11/22/2022-11-22/
コンピュータサイエンスの他のすべてと同じく、演算種類ごとのコストバランスが変わると、最善のアルゴリズムが 15 年、20 年前に使っていた方式へ戻ることがあります。だからプログラミングには流行のように見える面が大きいのです。何かを復活させることに理由がないわけではありませんが、前回それが万能薬ではなかった理由を忘れてしまうことは、依然として問題です
メイン JIT が速くなったり遅くなったりすると、実行コストに対する利益が変わり、それをトリガーするしきい値も調整されます。すると別の層で実行されるコード量が変わり、その層の償却コストも悪化し得ます。二重振り子のバランスを取るようなものです
JIT 層を十分に速く粗く作れるなら、インタプリタを完全に飛ばすこともできます。外から見ると、インタプリタと 2 つ程度の JIT の間で帳尻を合わせる認知負荷が大きいため、いくつかの言語はインタプリタを保留し、出力速度よりコンパイル時間に最適化した JIT を使ったように見えます
どの言語だったかは覚えていませんが、少なくとも 1 つのチームは、このバランス問題のために中間コンパイラも最終的に削除したと理解しています。3 つを扱うより、2 つに集中するほうがよかったのです
名前は毎回混乱しますが、
preserve_allかpreserve_noneのはずです。保存の観点が誰基準なのかが問題ですmusttail属性は GCC に追加されつつあると理解している。パッチはレビュー中で、セマンティクスは Clang と互換性があるpreserve_most属性はどうなるのか気になる。似たものが GCC に入る可能性はあるのだろうか。これがないと非テールコールがインタプリタを台なしにするClang には、
musttail呼び出しに対して呼び出しシーケンスを変更するヒューリスティックがあるように見える。たとえば i686 ではnoplt呼び出しに変える。こうした内容は Clang のドキュメントにはない: https://clang.llvm.org/docs/AttributeReference.html#musttail現実的に可能なのは、コンパイラがテールコールを生成できないときに診断メッセージを出す程度だ。多くのユーザーにとってはそれで十分な可能性が高い。Scheme のようにテールコールを保証するのは難しそうだ
C++ サポートにも触れられているが、C++ ではテールコールはかなり少なそうだ
たとえば
foo() { auto a = SomeClassWithADestructor(); return bar(); }は、bar()呼び出しの後にaの破棄が行われるのでテールコールではないbarを実行する前にデストラクタを呼べるのではないだろうか。C++ 標準がデストラクタを必ずブロック末尾で呼ぶべきだと言っているのか、それとも変数がもう使われないと分かった時点で呼んでもよいのかは気になる
例が単純すぎるのかもしれないが、良いコード生成のために
__attribute__((musttail))が必須には見えないエラー処理関数がまれな経路なら、呼び出し速度もそれほど重要ではなさそうだ
if (unlikely(malformed)) return error(); switch (data_type) { case x: return handle_x(); case y: return handle_y(); }のような構造は、かなり安定して良いジャンプテーブルを生成するように見えるそうでなければこの構造は動作せず、すぐにスタックが破裂する。
[[musttail]]の要点は、テールコール除去が必須だという点にある。コンパイラに他の選択肢はないもちろん「強制する」という表現は正確でないかもしれない。コンパイラが関数のすべての実行経路に単一のスタックフレーム構造を持たせなければならないと決まっているわけではなく、アドレスが取得されない内部リンケージ関数や無名名前空間の関数に標準 ABI を使わなければならないと決まっているわけでもない。だが私が見たすべてのコンパイラ、Clang も含めて実際にはそうしている。だから ABI の心配をせず、呼び出し間のレジスタ保存に時間を浪費するなと伝える方法が必要だ
ジャンプテーブルはもちろんうまく作られる。だがその結果を
perf reportのようなもので見て、テスト用バイトコードが短いループを表していないなら、次のどちらかを見ることになる。ディスパッチごとに分岐予測ミスがあるか、コンパイラが「インタプリタを書こうとしているようだ」と判断して各 case の末尾へ間接ジャンプを移動するかだ。Clang でこういうものを見たことがある。どちらにせよ、結果のコードのレジスタ割り当てはたいていひどいものになる可能性が高いトランポリン、つまり次の関数を関数ポインタとして返し、外側のループで呼び出す方式ならどれくらい速いのか気になる。利点は移植可能な C であることだ
Scheme プログラミング言語は、すべてのテールコールがスタックを増やしてはならないことを要求する。そのため実装者たちは、トランポリンを含めてさまざまな手法を探ってきた
引用できる資料はないが、Scheme を C にコンパイルする論文群に答えが見つかるはずだ。ターゲット言語にテールコール最適化の保証がなければ、生成されたプログラムは遅くなるだろう
付け加えると、特に高水準言語の実装者たちが JavaScript 仕様からテールコール最適化が削除されたことに不満を持つ理由もこれだ。テールコール最適化とスタック検査を両方維持する解法もある
https://github.com/schemedoc/bibliography/blob/master/page8....
関数ポインタでジャンプすると、おそらくそれほど予測可能ではなく、同じ利点は得にくいだろう
もちろん測定してみる必要があり、私はまだ試していない
CでProtobufデコーダー／エンコーダーとIMLパーサー、Pythonバインディングを書いたことがあり、パース速度の測定について言いたいことがある
このライブラリがマネージド言語向けのバインディングとしてだけ提供されるなら、性能面で他のすべてを圧倒する追加要因が生まれる。RubyやPHPは分からないが、Pythonでは列挙子を使わないときに劇的な速度向上が見られた。Protobufの列挙子をPythonの列挙子に変換すると、Cコードで得られるどんな利得も、さまざまなPythonオブジェクトの生成時間に踏みつぶされる。差は桁違いの規模になる。さらに、補助的なデータ構造をすべてCで実装し、Pythonには最小限のインターフェースだけを公開することもできる。こうした比較が、Pythonの組み込み構造を使うコードと比べてどれほど公平なのかは答えにくい
GoogleのPython向けProtobufパーサーは、今でも2GB/s超より「速い」可能性がある。理由は、最上位メッセージ以外は何もパースしないためだ。メッセージ内部の構造は必要になったときにパースされる。パース済みの内容をコードが直ちにすべて読むなら2GB/sより遅い可能性があるが、問題はこの2つのアプローチを実用上どう比較できるのかという点だ。アプリケーションの性質によって実際の結果が変わるため、明確な答えはない
一般的な場合、Protobufのパースは重複処理のためストリーミングできない。実際にProtobufの内容をパースするコードはI/Oボトルネックにぶつかる。パースを始める前にメッセージの終端を待つ必要があるためだ。それとは別に、アプリケーションで典型的に使われるProtobufメッセージによってはパースの並列化が可能な場合があり、その場合は単一スレッドのパーサーをほぼ上回れる可能性が高い。しかし前述の例と同じく、一般的に勝てる戦略だとは言えない
通常は、パースとドメインオブジェクト生成を結合するほうがはるかに効率的だ。アプリケーションはほぼ常にこの段階を経る必要がある。パーサーからこの機能にどうアクセスできるかが、多くの場合どのパーサーが勝つかを決める
結論として、Protobuf、あるいはパーサー一般は、速度測定や比較対象として適していない。低レベルすぎるうえ設計も良くないため、性能ベンチマークの基準にするのは難しい
最後のフィールドが勝つという規則が、ストリーミングパースをどう妨げるのか詳しく説明してほしい
GCCとClangには以前から
-foptimize-sibling-callsオプションがあり、デバッグビルドでも末尾呼び出しを得ることができたもちろん、この機能が標準化され、保証され、関数レベルで制御できるようになるのは大きな改善だ
[1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
[2] https://clang.llvm.org/docs/ClangCommandLineReference.html#t...