JavaScriptエンジンの最適化(1) – JITC, Adaptive Compilation

1.はじめに

JavaScriptコードを実装する際に「パフォーマンスを考慮して避けるべきコーディングスタイルがあるか」質問されたことがあります。そこで今回は、JavaScriptエンジンについて共有したいと思います。単に動作だけを説明するのではなく、エンジンの立場から、良いコードとはどのようなのものかに焦点を合わせ、1つずつ答えを探していきましょう。
ここでは、最近ほとんどのJavaScriptエンジンで使用されている、Just-in-Time compilation方式とAdaptive compilation方式について紹介します。

2. Just-in-Time Compilation(JITC)

現在よく使用されているJavaScriptエンジン(Safari、Chrome、FireFoxなど)は、すべてJITC方式を利用しています。JavaScriptエンジンはinterpreterのように動作し、初期バージョンのJavaScriptCore(WebKitのJSエンジンはSafariブラウザに含まれる)やV8(Chrome)は、実行されるすべてのJavaScriptコードをnative codeにコンパイルする方法を取っています。
JavaScript JITCは通常、次の図のような方法で行われます。

JavaScriptは基本的にtext形式で配布されますので、これを行うには変換が必要です。最初にsource codeをparsingして、中間言語(IR、intermediate representation)であるbytecode形式に変換します。次に、interpreterモードからbytecodeを1つずつ読みながら操作を実行して、JITモードの場合は生成されたbytecodeに基づいてnative codeにコンパイルして実行します。元々JITCはJava VMでよく使用される方式ですが、Javaは通常、bytecode形態である.classファイルとして配布されるため、parsing過程が省略されます。

当然ながらinterpreterで実行するよりもnative codeで実行する方が速いのですが、JITCの場合は当てはまりません。GCCのようなstatic compilerの場合、native codeを生成する途中で多くの最適化アルゴリズムを適用するため、生成されるコードの性能が良いからです(これは通常code qualityが高いと表現される)。JITCはコンパイルプロセス自体が実行中に発生することからoverheadになり、コンパイルに多くの時間を費やすことができません。したがって、コード全体を見据えて最適化する方法(data flow analysisが必要な最適化)ではなく、通常は極めて最小限の最適化のみ適用してnative codeを生成します。

それにもかかわらず、interpreterの実行時間よりnative codeの実行性能が格段に良く、JITCにoverheadがあったとしてもinterpreterより速く実行されることから、Java VMではJITCがよく利用されています。

3. JavaScriptではJITCよりinterpreterの方がよい?

JavaScript JITCが最小限の最適化を適用するという点の他に、2つの問題があります。

よく知られているように、JavaScriptは変数タイプが実行時に変更する可能性があり、classの代わりにobjectに継承されるprototype-based方式を使用しています。
非常に動的な言語のため、JavaScript JIT compilerはすべての例外的なケースを考慮して、コードを生成する必要があります。単純な変数を2つ加える加算のような場合でも、例外ケースを考慮すると、下図のように大量のnative codeが生成されます。(ARM)

もし加算の両方のoperandがすべてint型(JavaScriptはタイプがない代わりにエンジン内部で型を持っている)であれば、それだけ加えて変数の値に保存すればよいのですが、加算のoperandのうち、どちらかがint型ではない、あるいは加算するとintegerの範囲を超える、などの例外ケースが発生すると、slow caseにスキップされます。
slow caseはnative codeで生成するのが困難(正確にはnative codeで表現すると量が多くなる)な動作をnative codeで引き出す代わりに、あらかじめエンジン内部にCで実装されたfunction(helper function)を呼び出して動作を行います。もし、加算からint+int、string+string、string+intなどのケースをすべてnative codeに引き出すと、単純な足し算のため信じられないほど多くのnative codeが必要になり、helper functionを呼び出すことになります。

なお、このようなhelper functionは、interpreterモードで実行するときと同じコードを使用します。つまりJIT compilerでnative codeを実行しても、多くの部分はinterpreterと別段違いがありません。さらに、compilation overheadが加わることになるので、JavaScript JITCは、Javaよりもはるかに非効率的です。

また他の問題としては、JavaScriptで実装されたプログラムのコードの特性が、Javaとかなり異なるという点です。
Javaは演算(compute-intensive)プログラムが多く、一方でJavaScriptは主にWebページのlayoutを処理したり、ユーザーの入力に反応する方式のプログラムが多いです。2つの最大の違いは、頻繁に繰り返されて実行される区間(hotspot)の数で、JavaScriptは比較的、hotspotが非常に少ないです。つまり、loopが少なく、一度や二度実行されるコードがほとんどであるということです。(もちろん、HTML5が登場したことでcompute-intensiveなプログラムも多くなりました。)
hotspotが少なくなると、native codeを実行する時間に比べて、当該native codeを作る時間、すなわちcompile overheadが相対的に大きくなる問題があります。その結果、compilation overhead+nativeがinterpreterの実行時間よりも短いというJITCの仮定が崩れてしまいます。このようなことから、applicationの特性を比較してJavaScript JITCが性能向上に寄与したことはほとんどないという研究も行われています。

参考資料
An Analysis of the Dynamic Behavior of JavaScript Programs, PLDI 2010
JSMeter: Comparing Real-World Behavior of JavaScript Programs, USENIX 2010

このようなことから、hotspotがあまりないJavaScriptは、interpreterで実行した方がよいでしょう。ところが最近では、必ずしもそうだとは言い難くなっています。JavaScriptは単にWebからevent処理に限定して用いられるのではなく、ビジネスロジックにもある程度関与する多くの作業を実行するように要求したり、徐々にcompute-intensiveなプログラムも実装されてきています。JITCを完全に捨てることはできないでしょう。

では、古典的な方式のJavaScriptコードとcompute-intensiveコードの実行性能をすべて満足させる方法とは一体何でしょうか?

4. Adaptive JIT Compilation

最近のJavaScriptエンジンは、ほとんどがadaptive compilation方式を選択しています。Adaptive compilationとは、すべてのコードを一括して同レベルの最適化に適用するのではなく、繰り返し実行される程度によって流動的に(adaptive)異なる最適化レベルを適用する方法です。

基本的にすべてのコードは最初にinterpreterで実行します。そして頻繁に繰り返される部分(hotspot)が発見されると、その部分にのみJITCを適用してnative codeを実行します。最近のエンジンはJITCも複数段階に分けて適用します。最初は最小限の最適化のみ適用するJITC(baseline-JITC)でコンパイルして、実行途中でより頻繁に繰り返されるコードには、より多くの最適化を適用するJITC(Optimizing-JITC)をコンパイルすることでcode qualityの高いコードを生成します。

以下はChrome V8エンジンのadaptive JITCであるcrankshaftの動作を簡単に表したものです。

(Crankshaftはinterpreterではなくbaseline JITCから開始する)

一般的にadaptive JITCを使用するエンジンは、runtime profilerがあり、関数の実行頻度を記録します。それだけでなく、profilerは使用されている変数のタイプや値をprofileして、optimizing JITを適用するときに、これらの情報を使って従来のJITCで作成された例外処理ルーチンを大幅に省略した効率的なコードを生成します。

ただこのようにコードを生成すると例外的な状況が発生することがあります。たとえば、loopを100万回実行している間に、xという変数がずっとintegerであったのに、次のiterationで突然stringに変わってしまうことがあります。このような場合には、optimizing JITCで生成されたコードはもはや有効ではなく、再度以前のbaseline-JITCに生成されたコードで実行されます。このように例外が発生すると、overheadが途方もなく大きくなります。これは「profilingを実行中に、特定の変数のタイプが変わっていなければ、その後もその変数はタイプが変わらない可能性が非常に高い」という仮定に基づいた最適化と言えます。

実際にJavaScriptエンジンで実行される多くの最適化は(hidden class、inline cachingなど)、このような方法で実行され、変数のタイプやobject propertyが変わるなど動的な状況が発生する可能性もありますが、実際には動的な変化はあまり起こらないと仮定しています。したがって、動的な変化が発生したときはペナルティが大きいですが、変化がない場合は大きくパフォーマンスが向上します。代表的な最適化として、大半のJavaScript JITCで用いられているhidden classやinline cachingが挙げられます。
これについては、2部で詳しく紹介します。

5.結論

これまでの内容を要約すると次のとおりです。

• hotspotがあまりない古典的なJavaScriptプログラムには、interpreterの方がJITCより効率が良い
• 最近よく使用されているcompute-intensiveなJavaScriptプログラムには、JITCが良い
• 2つの傾向のコードに対するパフォーマンスをすべて満足させるため、最近のエンジンではadaptive JITCを採用している
• Adaptive JITCはtype profilingを実行するので、変数のタイプが変わらなければ、高い性能を得られる

最後の項目は、頻繁に繰り返されるloop内で、実行途中に変数のタイプが変わると、多くのペナルティが発生することになる、と言い換えることができます。実際にコードを実装するとき、そのような状況はほとんどありませんが、知っておくと有用です。

TOAST Meetup 編集部

TOASTの技術ナレッジやお得なイベント情報を発信していきます
pagetop