Fujisakiなかなか感動した次の記事を翻訳しました。翻訳とか初めてなので、意訳とかがところどころあれかも知れません。JavaScriptFirefox18で追加されたJITコンパイラ「IonMonkey」で、どうやってJITコンパイル時の型についての仮定を守りつつ、効率的にJITコンパイルを行うかの話です。JSのJITコンパイルとか、『大体Intが来るっぽいからInt向けにコンパイルしとこう』、みたいな感じでしょ?w」って思ってませんか?もっともっと、凄まじいですよ。version.」となります。Invalidation動的言語のJITエンジンの主な目的の一つは、高水準な言語を効率的な機械語にコンパイルすることだ。コンパイルされたコードはすべて、元のJavaScriptのコードがインタプリタで実行されたときと同じように振舞わなければならない。コンパイルされたコードの「正しさ」を保つことがJITコンパイラに求められる基本的な問題なんだ。効率的かつ正しいコードを生成するのは難しい。JavaScriptは非常に高い多態性を持つからだ。すべての変数はどんなタイプの値でも持つことができるし、一般的に言って実行時にどんな型の値が代入されるかを事前に知ることは出来ない。常に2つのintegerを足し合わせるようなコードがプログラム上のどこかにあったとしても、実行エンジン自体はintegerじゃない値が来ることを許さなければならないんだ。この問題に対処するためのテクニックが、大まかに言って2つある。ひとつは「guarding」だ。実行エンジンが実行前に型について仮定したことが守られているか実行時にチェックするようなコードを生成するんだ。さっきの例で言えば、JITコンパイラは2つのintegerを足し合わせる機械語を生成するけど、そのコードが実行される前に本当にそれらの2つの値がintegerであることを確かめるような機械語も追加する。そのチェックが失敗してしまったら、機械語は処理を明け渡し、稀なケースを処理するための、汎用的で遅い方法で実行を続ける。チェックが成功すれば、高速な(あるいは最適化された)機械語が実行される。このチェックは大体成功するから、速い方法がたいていは実行される。このguradingはよい方法だけど、パフォーマンス上のペナルティがある。仮定が守られてるかのチェックには時間が掛かるし、何度も実行されるコードではそれがパフォーマンス上の重大な損失になってしまう。ひとつの効率的なコードを生成しつつ正しさを守る方法は、invalidationだ。それが今回の記事で私が話したいこと。Monkeyの新しいJITであるIonMonkeyを例として使うよ。細かい点を除けば全体的な戦略は殆どのJITに適用できる。FeetInvalidationの鍵となるアイデアは「毎回仮定が守られているかチェックする機械語を生成する代わりに、その仮定が正しく無くなったら生成した機械語を無効化(invalidate)してしまう」ということだ。無効化された機械語が決して実行されないようにするために、型に対するガードとは別のガードを追加しないといけない。簡単な例を見てみよう。ここにいくつかの点の間の距離の和を求める、簡単なJavaScriptプログラムがある。totalDist;}main();このプログラムを実行するとき、dist関数は大体10000繰り返し実行された後、IonMonkeyによってコンパイルされる。[14]上のコードは本当のコードじゃなくて、分かりやすくしたものだ。本当の、詳しい低レベルのコードが見たかったら、ここをクリックしてね。命令の[3]と[4]で、Ionは引数をオブジェクトへのポインタであり、プリミティブでない事を一切チェックすることなく、値からオブジェクトのポインタを取り出し(unbox)てしまう。命令[5][6][8][9]では、オブジェクトからロードしたxとyをInt32に変換してしまう。(注意:”unbox”っていうのは、この場合は汎用的なJavaScriptの値を、生の具体的な値、例えばInt32とか、Doubleとか、Objectポインタとか、Booleanとかにデコードすることだ。)もし私達が仮定が守られていることをチェックするgurdingを使っていたら、次の余計なチェックがコードに現れていただろう。pt2.yがすべてInt32であることを確かめるチェックでも、このIRではこの6つのチェックをスキップしていて、とても詰まったコードになっている。ふつうなら、こんなことは出来ない。この仮定が守られなかったら、コードは「間違った」ものになってしまうからだ。dist関数がオブジェクトでない引数で呼ばれてしまったら、このJITコードはクラッシュしてしまう。distがxとyのInt32プロパティをもつPointのインスタンスを引数にして呼ばれなかったら、やっぱりクラッシュしてしまう。この生成された効率的なコードを実行を正しさを保ちつつ使うために、仮定が無効(invalid)になったら実行しない事を徹底しないといけない。そのために、SpiderMonkeyの型推論システムが必要だ。TI)は動的にJavaScriptのソースとオブジェクトの型情報と、コードの所々でどういったタイプが現れるかを追跡する。このTIによってメンテナンスされてアップデートされていくデータは、プログラムについての型の知識を表している。そのデータが変更された時、実行エンジンは特定の(型に対する)仮定が壊れてしまっていないかをチェックするトリガーを発動させる。次の図は、先述までのプログラムの、非常に単純化した型モデルに関する略図だ。上のTypeScriptはdist関数に関する型情報を持っている。一つ目と二つ目の引数(pt1とpt2)に関連付けられた型の集合などだ。下のTypeScriptは、Pointに関連付けられた型の情報を持っている。xとyのフィールドに関連付けられた型の集合などだ。このデータはTIによって必要に応じてアップデートされる。dist関数がPointのインスタンスでない引数に対して呼ばれたとすると、TIはTypeScript上の引数に対する型集合を正しくアップデートする。同様に、もしPointがInt32以外のxとyで出来たインスタンスが作られたら、TypeScript上のフィールドに対する型集合は正しくアップデートされる。hook)を適切な型集合に対してセットする。こんな感じ:新しい型が型集合に追加されたときはいつでも、関連した無効化フックが実行され、JITコンパイルされた機械語は無効化される。上のコードを書き換えて、実験的にこれらの無効化を発生させてみよう。私はこれから、Mozillaのソースからビルドされた、スタンドアローンのJavaScriptシェルを用いる。documentationを見て!)。はじめに、簡単なのからやろう。上にスクリプトを実行して、無効化が一切起こってない事を確かめるんだ。invalidation」は無視してほしい。これはガベージコレクションの開始によるもので、GCによって起こされる可能性のある無効化を実行エンジンがチェックするものだ。今回の記事とは関係ない)環境変数にIONFLAGS=osiを渡すことで、Ionにすべての無効化や関連するイベントの発生を実行中にコンソールに出力させることができる。出力が示すように、このプログラムでは一切無効化が起こっていない。何一つとして型に関する仮定がコンパイルされた後に壊されていないからだ。2二番目の実験として、「dist関数の引数はすべてPointのインスタンスである」という仮定を壊して、何が起こるか見てみよう。これが新しいmain関数だ。totalDist;}...このプログラムでは、ループ内でdist関数を何度も呼び出して「ホット」にすることで、distがJITコンパイルされるようになっている。dist関数に渡される引数はループ内では常にPointのインスタンスであるので、「この関数は必ずPointのインスタンスに対して実行される」という仮定でコンパイルされることになる。ループが実行されたら、もう一度dist関数が呼ばれる。今度は最初の引数はPointのインスタンスではないので、JITコードでの仮定が壊されてしまう。6)に対しての無効化を起こせたね!すばらしいことだっ。下の略図は何が起こったのかを示している。dist関数の最初の引数に対するTypeScriptが変更され、新しい型のTypeObjectに対する参照が追加されている。これが無効化フックを発動させ、IonScriptが無効化された:例33つ目の例として、Pointのインスタンスが必ずint32の値を持っている、という仮定を壊してみよう。GuardingInvalidationとguradingは与えられた操作に対してJITコードを生成する、はっきり異なったアプローチだ。与えられた任意の関数に関してJITコードを生成することについて、どちらのテクニックが使われたとしても、どちらかが必ず優っているわけではない。今回のInvalidation-basedな最適化のアドバンテージは、仮定が守られているかの毎回のガードがなくなることでhotなコードをかなり速く実行できることだ。仮定が壊れたとき、その壊れた仮定に頼っているJITコードはすべて無効化され、実行できなくなってしまう。これはつまり、新しい仮定の元で再度JITコンパイルされるまで、遅いインタプリタで実行することになる。不幸にも頻繁に型に関する仮定が壊されてしまうような環境でInvalidation-basedな最適化を行なってしまった場合、悲しい事に逆に高い実行時コストがかかってしまう。Gurad-basedな最適化であれば、生成されるコードのパフォーマンスを犠牲にするかわりに、仮定の変更につよい機械語が生成される。仮定が壊れてしまってもJITコードを捨てなくてもいい。その場合、単に遅い方法で実行されるだけだ。無効な仮定で関数が呼ばれる回数が少なければ(でも0よりは大きければ)、gurdingはinvalidationによる方式よりもよい選択だ。どちらの方式を使うべきかという問題には簡単に答えることはできない。仮定がたびたび壊れて、高いコストを払って再コンパイルされるとしても、何度も何度も実行されるのでInvalidation-basedな最適化の方が速いかもしれない。どこかの点を超えると、この2つのアプローチのどちらを選ぶかは経験とチューニングの問題となるだろう。Invalidation今回の記事では無効化の基本的な原理に関する一般的な考え方を書いた。いうものの、すべてのJITエンジンが気をつけないといけない、たまにしか起きないが非常に重要なケースがある。invalidationと呼ばれるものだ。それはコールスタック上にある関数(=今実行中の関数を呼び出している関数)がちょうど無効化されてしまうケースだ。これはつまり、今の関数の実行が終了した後、すでにもう安全に実行できない機械語の実行に戻ろうとする、ということだ。このケースにはすこし曲芸めいた対処が必要で、発生する可能性のある沢山の捉えづらいエラーを考慮する必要がある。続く記事でこれらに関してさらに書くことにする。感想なんというか凄まじいですね。ここまで型を追跡してるとは...。ちなみに最後の「これらに関してさらに書くことにする」の記事は現状ポストされてないようです。無効化の仮定が壊れてしまったとしても、別の型に対する新しいJITコードを作って使い分ける、とか出来ないですかね。例として出てきたdist関数ですが、int32に対してJITコンパイルしたバージョンと、floatに対してコンパイルしたバージョンの2つを作って、使い分けるとか。C++のテンプレートみたいな感じ?ここまで徹底的に型を追跡してるなら、やれてもおかしく無い気がします(適当な事を言っています)。この仮定が壊れてしまった事のメッセージを、ブラウザで書いてる最中からも見れると嬉しいのですが...。上のdistでdoubleが指定されるのはたぶん仕様の範囲内ですが、例えばファミコンエミュレータでint32ではなくfloatで実行された場合、ただのバグなので、それは教えてほしいです。/と、いうわけで、書き換えです。githubにソースコードを置きたい...でも公開できない情報が...。ありそうなのはこんなケース?MySQLのパスワードが書いてある...完全に非公開で遊ぶために書いてたから著作権上アレゲなコンテンツが...残念な感じのコミットログが...今更その部分を隠してコミットしたって、昔のコミットログを辿られたら意味ないじゃない!んじゃあ、修正済みのやつだけコミットログ無しで公開?もっと意味ないじゃん!そこで過去の書き換えです。gitはもうぶっちゃけ何でもできるので、過去のコミットを再度やりなおして全部書き換える事ができます。以上のケースについて、修正してみましょう。MySQLのパスワードが書いてある...こんなサンプルリポジトリを考えてみましょう(github)。ファイルの一部分に公開したくない情報があるケースです。ためしにこんなファイルを考えてみましょう。以下のコードはあくまでサンプルであり、何の意味もありません。何かロード処理的なものdb.close();db.initの行でパスワードをハードコーディングしてしまいました。公開するのには問題があるかもしれません。繰り返しますが、この状態からパスワードを隠してコミットしても過去のファイルはそのままなので、意味がありません。logはこんな感じです。パスワードを追加しちゃったコミット。