なかなか感動した次の記事を翻訳しました。翻訳とか初めてなので、意訳とかがところどころあれかも知れません。
The Ins and Outs of Invalidation | JavaScript
Firefox18で追加されたJITコンパイラ「IonMonkey」で、どうやってJITコンパイル時の型についての仮定を守りつつ、効率的にJITコンパイルを行うかの話です。「型推論ｗ どうせJSのJITコンパイルとか、『大体Intが来るっぽいからInt向けにコンパイルしとこう』、みたいな感じでしょ？ｗ」って思ってませんか？もっともっと、凄まじいですよ。
この記事のライセンスは元記事と同じ、「Creative Commons Attribution Share-Alike License v3.0 or any later version.」となります。
もくじ
The Ins and Outs of Invalidation
動的言語のJITエンジンの主な目的の一つは、高水準な言語を効率的な機械語にコンパイルすることだ。しかしながら、コンパイルされたコードはすべて、元のJavaScriptのコードがインタプリタで実行されたときと同じように振舞わなければならない。つまり、コンパイルされたコードの「正しさ」を保つことがJITコンパイラに求められる基本的な問題なんだ。
しかし、効率的かつ正しいコードを生成するのは難しい。なぜなら、JavaScriptは非常に高い多態性を持つからだ。すべての変数はどんなタイプの値でも持つことができるし、一般的に言って実行時にどんな型の値が代入されるかを事前に知ることは出来ない。たとえば、常に２つのintegerを足し合わせるようなコードがプログラム上のどこかにあったとしても、実行エンジン自体はintegerじゃない値が来ることを許さなければならないんだ。
この問題に対処するためのテクニックが、大まかに言って２つある。ひとつは「guarding」だ。実行エンジンが実行前に型について仮定したことが守られているか実行時にチェックするようなコードを生成するんだ。さっきの例で言えば、JITコンパイラは2つのintegerを足し合わせる機械語を生成するけど、そのコードが実行される前に本当にそれらの２つの値がintegerであることを確かめるような機械語も追加する。もしそのチェックが失敗してしまったら、機械語は処理を明け渡し、稀なケースを処理するための、汎用的で遅い方法で実行を続ける。もしチェックが成功すれば、高速な（あるいは最適化された）機械語が実行される。このチェックは大体成功するから、速い方法がたいていは実行される。
このguradingはよい方法だけど、パフォーマンス上のペナルティがある。仮定が守られてるかのチェックには時間が掛かるし、何度も実行されるコードではそれがパフォーマンス上の重大な損失になってしまう。もうひとつの効率的なコードを生成しつつ正しさを守る方法は、invalidationだ。それが今回の記事で私が話したいこと。これからSpider Monkeyの新しいJITであるIonMonkeyを例として使うよ。でも、細かい点を除けば全体的な戦略は殆どのJITに適用できる。
Invalidation at 10,000 Feet
Invalidationの鍵となるアイデアは「毎回仮定が守られているかチェックする機械語を生成する代わりに、その仮定が正しく無くなったら生成した機械語を無効化（invalidate）してしまう」ということだ。ただし無効化された機械語が決して実行されないようにするために、型に対するガードとは別のガードを追加しないといけない。まずは簡単な例を見てみよう。ここにいくつかの点の間の距離の和を求める、簡単なJavaScriptプログラムがある。
function Point(x, y) {
this.x = x;
this.y = y;
}
function dist(pt1, pt2) {
var xd = pt1.x - pt2.x,
yd = pt1.y - pt2.y;
return Math.sqrt(xd*xd + yd*yd);
}
function main() {
var totalDist = 0;
var origin = new Point(0, 0);
for (var i = 0; i < 20000; i++) {
totalDist += dist(new Point(i, i), origin);
}
// The following "eval" is just there to prevent IonMonkey from
// compiling main(). Functions containing calls to eval don't
// currently get compiled by Ion.
eval("");
return totalDist;
}
main();
このプログラムを実行するとき、dist関数は大体10000繰り返し実行された後、IonMonkeyによってコンパイルされる。その時の中間言語（intermediate representation; IR)はこれだ。
[1] Parameter 0 => Value // (pt1 value) [2] Parameter 1 => Value // (pt2 value) [3] Unbox [1] => Object // (unbox pt1 to object) [4] Unbox [2] => Object // (unbox pt2 to object) [5] LoadFixedSlot(x) [3] => Int32 // (read pt1.x, unbox to Int32) [6] LoadFixedSlot(x) [4] => Int32 // (read pt2.x, unbox to Int32) [7] Sub [5] [6] => Int32 // xd = (pt1.x - pt2.x) [8] LoadFixedSlot(y) [3] => Int32 // (read pt1.y, unbox to Int32) [9] LoadFixedSlot(y) [4] => Int32 // (read pt2.y, unbox to Int32) [10] Sub [8] [9] => Int32 // yd = (pt1.y - pt2.y) [11] Mul [7] [7] => Int32 // (xd*xd) [12] Mul [10] [10] => Int32 // (yd*yd) [13] Add [11] [12] => Int32 // ( (xd*xd) + (yd*yd) ) [14] Sqrt [13] => Double // Math.sqrt(...) [15] Return [14]
上のコードは本当のコードじゃなくて、分かりやすくしたものだ。本当の、詳しい低レベルのコードが見たかったら、ここをクリックしてね。
命令の[3]と[4]で、Ionは引数をオブジェクトへのポインタであり、プリミティブでない事を一切チェックすることなく、値からオブジェクトのポインタを取り出し(unbox)てしまう。命令[5][6][8][9]では、オブジェクトからロードしたxとyをInt32に変換してしまう。
（注意：”unbox”っていうのは、この場合は汎用的なJavaScriptの値を、生の具体的な値、例えばInt32とか、Doubleとか、Objectポインタとか、Booleanとかにデコードすることだ。）
もし私達が仮定が守られていることをチェックするgurdingを使っていたら、次の余計なチェックがコードに現れていただろう。
- ２つの型チェック：[3][4]で生の値を取り出す前に「引数がオブジェクトポインタであること」を確かめる追加のチェック
- ４つの型チェック：pt1.x, pt2.x, pt1.y, and pt2.yがすべてInt32であることを確かめるチェック
でも、このIRではこの６つのチェックをスキップしていて、とても詰まったコードになっている。ふつうなら、こんなことは出来ない。もしこの仮定が守られなかったら、コードは「間違った」ものになってしまうからだ。もしdist関数がオブジェクトでない引数で呼ばれてしまったら、このJITコードはクラッシュしてしまう。もし、distがxとyのInt32プロパティをもつPointのインスタンスを引数にして呼ばれなかったら、やっぱりクラッシュしてしまう。
この生成された効率的なコードを実行を正しさを保ちつつ使うために、仮定が無効(invalid)になったら実行しない事を徹底しないといけない。そのために、SpiderMonkeyの型推論システムが必要だ。
型推論
SpiderMonkeyの型推論（type inference; TI)は動的にJavaScriptのソースとオブジェクトの型情報と、コードの所々でどういったタイプが現れるかを追跡する。このTIによってメンテナンスされてアップデートされていくデータは、プログラムについての型の知識を表している。そのデータが変更された時、実行エンジンは特定の（型に対する）仮定が壊れてしまっていないかをチェックするトリガーを発動させる。
次の図は、先述までのプログラムの、非常に単純化した型モデルに関する略図だ。
上のTypeScriptはdist関数に関する型情報を持っている。一つ目と二つ目の引数（pt1とpt2）に関連付けられた型の集合などだ。
下のTypeScriptは、Pointに関連付けられた型の情報を持っている。xとyのフィールドに関連付けられた型の集合などだ。
このデータはTIによって必要に応じてアップデートされる。たとえば、dist関数がPointのインスタンスでない引数に対して呼ばれたとすると、TIはTypeScript上の引数に対する型集合を正しくアップデートする。同様に、もしPointがInt32以外のxとyで出来たインスタンスが作られたら、TypeScript上のフィールドに対する型集合は正しくアップデートされる。
Ionが関数をJITコンパイルして、型に関する暗黙の仮定を行う時、無効化フック（invalidation hook）を適切な型集合に対してセットする。こんな感じ：
新しい型が型集合に追加されたときはいつでも、関連した無効化フックが実行され、JITコンパイルされた機械語は無効化される。
Ionで実験
上のコードを書き換えて、実験的にこれらの無効化を発生させてみよう。私はこれから、Mozillaのソースからビルドされた、スタンドアローンのJavaScriptシェルを用いる。あなたも自分でJavaScriptシェルのデバッグバージョンをビルドすることで、以下の実験結果を実際に試すことができる（詳しくはthe SpiderMonkey build documentationを見て！）。
はじめに、簡単なのからやろう。上にスクリプトを実行して、無効化が一切起こってない事を確かめるんだ。
$ IONFLAGS=osi js-debug points.js [Invalidate] Start invalidation. [Invalidate] No IonScript invalidation.
（これから出てくる、余計な嘘の「Start invalidation」は無視してほしい。これはガベージコレクションの開始によるもので、GCによって起こされる可能性のある無効化を実行エンジンがチェックするものだ。今回の記事とは関係ない）
環境変数にIONFLAGS=osiを渡すことで、Ionにすべての無効化や関連するイベントの発生を実行中にコンソールに出力させることができる。出力が示すように、このプログラムでは一切無効化が起こっていない。何一つとして型に関する仮定がコンパイルされた後に壊されていないからだ。
例 2
二番目の実験として、「dist関数の引数はすべてPointのインスタンスである」という仮定を壊して、何が起こるか見てみよう。これが新しいmain関数だ。
...
function main() {
var totalDist = 0;
var origin = new Point(0, 0);
for (var i = 0; i < 20000; i++) {
totalDist += dist(new Point(i, i), origin);
}
dist({x:3,y:9}, origin); /** NEW! **/
// The following "eval" is just there to prevent IonMonkey from
// compiling main(). Functions containing calls to eval don't
// currently get compiled by Ion.
eval("");
return totalDist;
}
...
このプログラムでは、ループ内でdist関数を何度も呼び出して「ホット」にすることで、distがJITコンパイルされるようになっている。また、dist関数に渡される引数はループ内では常にPointのインスタンスであるので、「この関数は必ずPointのインスタンスに対して実行される」という仮定でコンパイルされることになる。ループが実行されたら、もう一度dist関数が呼ばれる。しかし、今度は最初の引数はPointのインスタンスではないので、JITコードでの仮定が壊されてしまう。
$ IONFLAGS=osi js-debug points.js [Invalidate] Start invalidation. [Invalidate] No IonScript invalidation. [Invalidate] Start invalidation. [Invalidate] Invalidate points.js:6, IonScript 0x1f7e430
（もう一度言うけど、最初のStart invalidationはGC実行によって引き起こされたもので、今回の記事とは無関係）
おお！dist関数(points.js, line 6)に対しての無効化を起こせたね！すばらしいことだっ。
下の略図は何が起こったのかを示している。dist関数の最初の引数に対するTypeScriptが変更され、新しい型のTypeObjectに対する参照が追加されている。これが無効化フックを発動させ、IonScriptが無効化された：
例3
３つ目の例として、Pointのインスタンスが必ずint32の値を持っている、という仮定を壊してみよう。今度のmainはこんな感じ：
...
function main() {
var totalDist = 0;
var origin = new Point(0, 0);
for (var i = 0; i < 20000; i++) {
totalDist += dist(new Point(i, i), origin);
}
dist(new Point(1.1, 5), origin); /** NEW! **/
// The following "eval" is just there to prevent IonMonkey from
// compiling main(). Functions containing calls to eval don't
// currently get compiled by Ion.
eval("");
return totalDist;
}
...
それで、これがその結果だ：
$ IONFLAGS=osi js-debug points.js [Invalidate] Start invalidation. [Invalidate] No IonScript invalidation. [Invalidate] Start invalidation. [Invalidate] Invalidate points.js:6, IonScript 0x1f7e430
次の略図が何が起こったのか示している：
Invalidation vs. Guarding
Invalidationとguradingは与えられた操作に対してJITコードを生成する、はっきり異なったアプローチだ。与えられた任意の関数に関してJITコードを生成することについて、どちらのテクニックが使われたとしても、どちらかが必ず優っているわけではない。
今回のInvalidation-basedな最適化のアドバンテージは、仮定が守られているかの毎回のガードがなくなることでhotなコードをかなり速く実行できることだ。しかしながら、もちろん欠点もある。仮定が壊れたとき、その壊れた仮定に頼っているJITコードはすべて無効化され、実行できなくなってしまう。これはつまり、新しい仮定の元で再度JITコンパイルされるまで、遅いインタプリタで実行することになる。もし不幸にも頻繁に型に関する仮定が壊されてしまうような環境でInvalidation-basedな最適化を行なってしまった場合、悲しい事に逆に高い実行時コストがかかってしまう。
Gurad-basedな最適化であれば、生成されるコードのパフォーマンスを犠牲にするかわりに、仮定の変更につよい機械語が生成される。仮定が壊れてしまってもJITコードを捨てなくてもいい。その場合、単に遅い方法で実行されるだけだ。無効な仮定で関数が呼ばれる回数が少なければ（でも０よりは大きければ）、gurdingはinvalidationによる方式よりもよい選択だ。
どちらの方式を使うべきかという問題には簡単に答えることはできない。仮定がたびたび壊れて、高いコストを払って再コンパイルされるとしても、何度も何度も実行されるのでInvalidation-basedな最適化の方が速いかもしれない。もちろん、そうでないかもしれない。どこかの点を超えると、この２つのアプローチのどちらを選ぶかは経験とチューニングの問題となるだろう。
On-Stack Invalidation
今回の記事では無効化の基本的な原理に関する一般的な考え方を書いた。とはいうものの、すべてのJITエンジンが気をつけないといけない、たまにしか起きないが非常に重要なケースがある。
それはon-stack invalidationと呼ばれるものだ。それはコールスタック上にある関数（＝今実行中の関数を呼び出している関数）がちょうど無効化されてしまうケースだ。これはつまり、今の関数の実行が終了した後、すでにもう安全に実行できない機械語の実行に戻ろうとする、ということだ。
このケースにはすこし曲芸めいた対処が必要で、発生する可能性のある沢山の捉えづらいエラーを考慮する必要がある。続く記事でこれらに関してさらに書くことにする。
感想
なんというか凄まじいですね。ここまで型を追跡してるとは…。ちなみに最後の「これらに関してさらに書くことにする」の記事は現状ポストされてないようです。読みたいなぁ。
無効化の仮定が壊れてしまったとしても、別の型に対する新しいJITコードを作って使い分ける、とか出来ないですかね。例えば、例として出てきたdist関数ですが、int32に対してJITコンパイルしたバージョンと、floatに対してコンパイルしたバージョンの２つを作って、使い分けるとか。C++のテンプレートみたいな感じ？ここまで徹底的に型を追跡してるなら、やれてもおかしく無い気がします（適当な事を言っています）。
この仮定が壊れてしまった事のメッセージを、ブラウザで書いてる最中からも見れると嬉しいのですが…。上のdistでdoubleが指定されるのはたぶん仕様の範囲内ですが、例えばファミコンエミュレータでint32ではなくfloatで実行された場合、ただのバグなので、それは教えてほしいです。。。