2005年のそれほど新しくないものだが、Context Threading: A flexible and efficient dispatch technique for virtual
machine interpreters という論文を読んだので、内容について少しまとめておく。
前提知識: 既存のThreading手法
http://www.complang.tuwien.ac.at/forth/threaded-code.html にまとまっているが、この論文では以下の2つが関係している:
- Direct threading: ラベルのアドレスを取得するGCC拡張などを使い、VMのprogram counterからVM命令の実装のアドレスをディスパッチしてそこにジャンプする
- Subroutine threading: VM命令の実装を関数にしておき、それをcallする命令を並べたネイティブコードをバイトコード(メソッド)ごとに生成しそれを命令ディスパッチに使う
Context Threadingの論文内ではDirect threadingがstate-of-the art dispatch techniqueということになっている。
(本筋からズレた余談だけど、JavaScriptCoreでは "given the average complexity of the bytecode instructions in JSC we did not expect the dispatch overhead to play a meaningful role in the overall performance of the interpreter." ということでDirect threadingをやめている。)
Context Threadingが解決する問題: Context Problem
モダンなCPUが高速に動作するためには、分岐予測を正しく当てることでパイプラインをフルに使い続ける必要がある。
Indirect branch predictorsは分岐先とIndirect branch命令自体のアドレスが強い相関関係を持つことを仮定しているが、Direct threadingのワークロードでは通常これが成立しないため、分岐予測が当たりにくくなっているという問題がContext Problem。
これはDirect threadingのディスパッチが、CPUが分岐予測のインプットとして使うハードウェアprogram counterではなく、VM用のバーチャルなprogram counterに依存していることにより発生する。
Context Threadingとは
VMが実行するプログラムには、以下の種類のcontrol flowが含まれる。
- straight-line virtual instructions: 普通に直列に命令を実行していくケース
- conditional and unconditional branches: 分岐のあるジャンプとgoto的ジャンプ命令
- calls and returns: メソッド呼び出し命令とそのreturn命令
Context Threadingでは、これらのcontrol flowに対して別々の方法でContext Problemに対処している。
Subroutine Threading
straight-line virtual instructions用。
上記に書いた通りVM命令の実装を呼び出すcall命令を並べたネイティブコードを生成して実行するというもの。このコードがContext Threading Tableと呼ばれている。
オペランドを取り出す関係上、Direct threadingで元々使っていたDirect Threading Table (バイトコード) も必要である、と書いてある。(それはそう)
Direct threadingでは間接ジャンプ命令1つで良かったのが、callとreturn命令が必要になってしまいディスパッチの処理は複雑になってしまうように見えるが、VMのバーチャルなprogram counterがハードウェアprogram counterに置き換えられて分岐予測の入力に使われ、またモダンなCPUではreturn address stackというreturn先の予測に使うハードウェアを持っていることで、分岐予測が当たる分トータルでは速くなる、としている。
Branch Replication/Inlining
conditional and unconditional branches用。
conditionalかどうかで対応方法が異なっている:
- indirect virtual branches and exceptions: 分岐命令本体の大部分はcallして共有するが、そこでジャンプ先を計算した直後の間接ジャンプ命令に相当する部分だけネイティブコードに書く (branch replication)
- all other branches (分岐なしジャンプ命令など): 命令全体をインライン化する。その際可能な限りindirect branchはdirect branchに変換してBranch Target Bufferへのプレッシャーを減らす。 (branch inlining)
後者で完全にインライン化するのは、前者ではcall/return/実際のブランチで3つhardware control transferが必要になり、単純な分岐命令にとっては必要以上に一般化されている上、conditional branch predictorのリソースをフルに活用できなくなるため。
インライン化するとコードサイズが増えてキャッシュミスするリスクがあるため、branch inliningは単純なジャンプにしか使わない。
これらを適用することにより、分岐命令たちがそれぞれ特有のハードウェアコンテキストを持つようになり、分岐予測が効きやすくなる。
Apply/Return Inlining
calls and returns用。
VMのcallとreturn命令に対して、以下の対応を加える。
- VMのcall: VMのcall命令のメインの部分は他のSubroutine Threading同様にネイティブなcall命令で呼び出してネイティブなreturn命令で返し、呼び出し先が決まった後のネイティブなindirect call命令は個別のバイトコード用の生成コード内にインライン化する。VMのcall命令のジャンプ元が共有アドレスではなくバイトコードごとに個別のものになる。
- VMのreturn: Subroutine Threadingとは異なり、(return address stackへの影響を避けるため、ネイティブなcall命令を使わず)ネイティブなjmp命令でVM命令のreturnの実装に飛び、そこでネイティブなreturn命令を呼ぶことで、上記のVMのcallでreturn address stackに積んだ情報を元にVMのcall命令を呼ぶ前の場所にジャンプする。
文字で説明するとVMのcall/returnとネイティブなcall/returnが混ざってちょっとわかりにくいので、論文のFigure 4の図を見た方がわかりやすいかもしれない。
VM上のバーチャルなcontrol flowがネイティブなflowに一致するようになるので分岐予測が効きやすくなるが、この場合VMで大域脱出を実装した際にハードウェアスタックも巻き戻す必要があったり、いくつかの環境はネイティブなスタックポインタをシグナルハンドリングなどに使うのでハードウェアスタック操作にsensitiveであることに注意する必要がある。
ベンチマーク
詳細は論文を参照。個人的にはRubyのVMの関連でこれを読んでいるのと、PowerPCは僕は使うことがないので以下のものが主に参考になった:
- Figure 6 (a): Java (SableVM) on Pentium IV でのDirect threadingと比較した分岐ミス数
- Figure 8 (a): Java (SableVM) on Pentium IV でのDirect threadingと比較した実行時間
SELECTがDirect threadingに加えてSableVMが持っているSelective Inliningを使ったもの、SUBがSubroutine Threadingのみ、BRANCHがそれにBranch Inliningを加えたもの、CONTEXTがそれにApply/Return Inliningが入ってContext Threadingになった奴で、TINYがそれにTiny Inliningという軽いインライン化の実装をいれた奴。
上記のcontrol flowの中ではstraight-line virtual instructionsを実行している時間が一番長いので、Context ThredingにおいてはSubroutine Threading部分が一番パフォーマンスにインパクト(Pentium IV上で、OCamlで平均75%, SableVMで85%)を持っており、Branch Inliningが次に大きなインパクトを持っていることが観測されている。
僕が見ていたグラフではSelective Inliningが速いな…という印象で、しかも結局 We conclude that, for general usage, subroutine threading plus branch inlining provides the best trade-off とか言われており、トータルの実行速度上はTiny Inliningをいれない限りApply/Return Inliningは不要なように見える。
Tiny Inlining
Selective InliningありのSableVMが速いが、それに近い性能を出すため、Context Threadingを実装することによってContext Threading Table上に実装が容易になった、簡単なインライン化手法が紹介されている。
命令ディスパッチのコードの4倍より命令本体のコードの方が小さい場合はインライン化するというヒューリスティックにより、call/returnのオーバーヘッドを軽減するというもの。ConclusionではこれでSableVMのSelective Inliningの1%以内になったと書いているが、そうでもないベンチマークが割とあるようにも見える。
所感
Context Threading Tableの管理 (メモリ領域の確保/GC、およびネイティブコードのアセンブル) に関して一切触れられていないが、実際に実装しようとするとそこが大変になるのは明らかなので、 "Context threading is easy to implement" というようにはいかないと思われる。
あと、やや情報が古いので、最近のCPUだとcall/returnのオーバーヘッドはどうか、という状況も違っているかもしれない。が、VMで分岐予測ミスを減らしたくなった時に今でも有効そうな手法だと感じた。