VM の高速化のために Context Threading を学ぶ - Scheme VM を書く

「GWもする事はコーディング」の会で VM のディスパッチの高速化に Context threading なる手法があることを教わりました。
現在採用している Direct Threaded という手法よりも高速になったという論文を読みます。
「Context Threading: A flexible and efficient dispatch technique for virtual machine interpreters - Marc Berndl, Benjamin Vitale, Mathew Zaleski and Angela Demke Brown」。

まだ理解度4割ほどですが Abstract やら本文を読んだまとめです。

まとめ

最近の深いパイプラインの CPU アーキテクチャでは分岐予測によりパフォーマンスを向上させておりそれに頼っている部分がある。
Direct-threaded インタプリタはバイトコードのディスパッチに間接分岐（indirect branch）を使うが、これだとVMのプログラムの制御フローと、ハードウェアのプログラムカウンタが関連づいていないため予測が限られパフォーマンスの足かせになる。
つまりハードウェアの分岐予測器は、ネイティブコードに現れる、とても偏った分岐を利用するために PC を用いるのだけど、Direct-threaded VM ではせっかく仮想命令列にも分岐や、ループなどのパターンがあるのにハードウェアからは見えず分岐予測のための情報源になっていない。

Context Threading ではハードウェアとVMの状態を整列することで分岐予測を改善する。
つまり VM の制御フローがハードウェアに見えるようなテクニックを用いて分岐予測を向上させる。

具体的にはリニアな VM 命令列をネイティブの call とreturn によりディスパッチするようにするらしい。
こうすることでネイティブスタックに積まれた return アドレスを利用した分岐予測が出来る。
Direct-threaded と比べて call と return が増える分コストが増えるように見えて直感とはあわないが分岐予測ミスの減少によりパフォーマンスが良くなるらしい。

論文では効果を Pentium 4と PowerPC 上の Java と OCaml で評価。
Pentium 4 では分岐予測ミスが 95% 減り、PowerPC では分岐ストールサイクルが Ocaml で 75%、Java で 82% 減った。
分岐予測ミスの現象により実行時間が Java では 25 %、Ocaml はP4 で19%、PPC970 では37%短くなったらしい。

まだ理解できていない branch-inlining などは実装例を見つけてあとからまとめるかもしれない。