LL Future, tracing jit, IBM Java Just-in-Time Compiler

.NET

寝過ごして事実上午後から参加の LL Future．終了後は，さくら水産にてみなさんと晩ご飯．魚類は控えめ．
そろそろ寝ないとまた明日(というか今日)も寝過ごしそうなのですが，記憶が飛ぶ前に tracing jit 絡みの話だけメモ．
要は私が読み飛ばしていた omo さんのエントリがあって，今回 LL Future で「なるほどそういう話だったのか」と把握できたという話なんですが．

つまり, こんな AS のコードから...:

 ##GooglePrettify
 public class Foo {
    public function bar() : void {
     doSomething();
    }
 }
 
 ...
 foo = new Foo();
 ...
 foo.bar();

こんなかんじのネイティブコードができると考えればいい:

 ##GooglePrettify
 // クラス定義は省略
 ...
 Foo* foo = new (gc) Foo();
 ...
 // 呼び出すメソッドをチェックする. vtbl は仮想関数テーブルをあらわす空想上の変数
 if (Foo::vtbl.bar != foo->vtbl->bar) { goto side_exit_at_path_1; }
 doSomething(); // インライン化された bar() の実装. ほんとは更にこいつもインライン化されるはず. 
 ...

ガードを入れながらトレースするだけの至ってシンプルな仕組みで, 仮想関数がインライン化された. JIT の力を痛感する.

インライン化されれば関数をまたいだ最適化の恩恵にも与れる. また tamarin-devel での議論をみていると, 将来の改善ではガードをループの外に追い出すような高速化も目論みにあるようす. ABC のメソッドだけでなく, forth をコンパイルしてできた IL ランタイムも同様にインライン展開される.

なお Sun の Hotspot Java VM は, クラス階層を分析することでチェックのいらない仮想関数をインライン化するという. いまどき仮想関数テーブルとかいってるのは C++ だけかもしらん. あー, JIT いいなあ...

MS CLR でも似た最適化をやっているという記事があるのでご紹介．

ここでの主役はインターフェイス経由の callvirt．愚直な CLI 実装では 2 回も仮想関数テーブルのルックアップが必要なところを，理想的なケースでのコードパスを「比較1回+ジャンプ1回」に変換してやるぜ，というお話．

One of the interface implementations is called considerably more frequently than others, at a given call site. This can be determined by dynamically profiling and patching the code or by some kind of hint from the programmer. (See http://www.sable.mcgill.ca/publications/papers/2005-4/sable-paper-2005-4.ps and http://www.research.ibm.com/journal/sj/391/suganuma.html for more information on the topic in general and its JVM implementation in particular.) In this case, the interface method dispatch for that specific interface can be modified to direct dispatch or even inlined, as follows:

if (obj->MethodTable == expectedMethodTable) {
      // Inlined code of "hot" method
}
else {
      // Normal interface method dispatch code
}

上のあたりに IBM Java Just-in-Time Compiler の話がでてくる．上記の例にはインライン化とあるけどこれは JVM 実装の話っぽい．では CLR だとどうかというのがこれ．

Summarized in pseudo-code, this looks somewhat like the following:

start: if (obj->Type == expectedType) {
      // Jump to the expected implementation
}
else {
      expectedType = obj->Type;
      goto start;
}

This is the final behavior that we get for the entire course of the program. It means that per call site, we get a one-shot counter (initialized to 100) which counts the times the "hot" implementation was missed. After the counter decays below 0, JIT back-patching is triggered and the code is replaced with the version we just saw, that alternates the "hot" implementation with each miss.

こっちが MS CLR (x86) の話と．カウンタを用意して予想が外れまくった場合に備えているあたりが特色なんですかね．
とまあメモ完了なのでお休みなさいのお時間．皆様お休みなさいませ．

その他関連資料

以下は直接は関係ないんだけどおもしろい (含コメント欄)．