LLVMとコンパイラとVM

某会場のLT(5min)において、Dart VMの普及を願い紹介させていただきました。
煽りの入ったLTですが、以下の理由から作成することにしました。

Dart VMを開発しているGoogleのVMチームは、
古くはSunでSelf Hotspot OOVM V8 Dart VMと開発してきた経緯からすると、
HotspotやV8は当時の目標や技術的な課題、制約等あったわけで、
単純に速い遅いと比較するわけにもいかないはずです。
またDart VMもV8も同じ会社で開発している関係上、パフォーマンスがでない理由は百も承知なはずですし、
表立ってdisりにくいのかなと思ったわけです。
私みたいなDart VM WatcherがV8を一人disるくらい問題ないよね、と。

ちょっと補足説明させていただきますと、
Dart VMはia32に限っていうと、各種マイクロベンチマークではよい成績ですし、
fibonacchi界で非常に速いです。
しかしマイクロベンチマークの成績は、
各実行環境の一側面しか測定できていないことに注意する必要があると思います。

ぶっちゃけていうと、たしかにOctane系のベンチマークではV8よりも2倍近く速いし、
DeltaBlueにおいてはJVMより良い成績を出していますが、
それらは一般的な結果ではありません。
Computer Language Benchmark GamesでもV8のほうが速いものがまだまだあります。
JVMとの比較に関しても、Smi(31bitに収まる整数)を積極的に使ったマイクロベンチマークでは
よい勝負ができると考えていますが、
それ以外のベンチマークではJVMのほうが高速であると思います。
Dart VMとJVMとのアーキテクチャ上の比較はこちらでまとめています。
JVM(HotSpot) VS. Dart VM

とはいえ、
Dart VMにOptimizerが追加され、スコアが上がってきたここ1年の経緯は非常に面白いです。
Fibonacchiでなぜ速いのか、
どのような最適化が実装され、効果が上がっているのかを紹介してみます。

(1) Fibonacchi界での比較
(2) SelectRepresentation & TypePropagator
(3) Inlining
(4) Field Type Feedback
(5) Polymorphic Inlining
(6) Store Sinking

-----------------------------------------------------------------------------------------
(1) Fibonacchi界での比較
Dart VM Advent Calendar
Fibonacchi界での比較は、上記リンクで既に行っていますが、
Dart VMを測定した2012/12当時は900 msでした。
今は408msと非常に高速です。
その理由は再帰関数のinliningが効いています。

clang/gcc/iccは再帰関数のInliningを行わないのですが、
Dart VMとJVMはInliningします。その結果、Dart VMとJVMは似たようなスコアとアセンブラを生成し、
約400 ms強の結果となっています。

もっとも素直なアセンブラを生成するclangは置いておくと、
gccとiccのパフォーマンスと最適化が非常に面白いです。
上記Cコンパイラは、どれも再帰関数のInliningは抑止されているのですが、
gccとiccは、関数fibo()をpureな関数であると解析し、pureな関数の末尾再帰最適化を行います。
※gccは宗教上の理由によりソースコードを拝見できないため詳細不明です、、
※-O2で有効になる、-foptimize-sibling-callsの効果のようです。

return fibo(n-1) + fibo(n-2)
↓↓↓
for (;n>1;n-=2) sum += fibo(n)
というような変換を行います。

iccのほうは、前提条件を確認する処理が大量にはいっているため遅いように思います。
もしかしたら、iccのほうが一般的な最適化になっているかもしれません。。

(2) SelectRepresentation & TypePropagator
これはV8やDart VMのようなdynamic typingな言語固有の最適化になるのですが、
Type Feedbackした起点からType propagateした結果を踏まえて、
不要なBoxing処理、Unboxing処理を除去します。
具体的には、可能な限りUnboxingされたSmi値やDouble値で計算を行い、
Storeの直前などの副作用完了点でのみBoxingを行い、オブジェクトを格納します。

(3) Inlining
がっつが足りない。

(4) Field Type Feedback
前回のblog記事が該当します。

(5) Polymorphic Inlining
がっつが足りない。

(6) Store Sinking
最初Store SinkingときいてLua JITかよと思ったのですが、違います。
やっていることは、JVMのopto(C2)における、
Escape Analysis + Scalar Repl of Aggregatesのような最適化を行います。
つまり、一時オブジェクトのAllocationをHeapではなくStackへの確保に置換する最適化です。

具体的には、1個しか使用点を持たないsmall objectのallocationを、
stack確保に置換します。
こういう最適化はOctaneベンチマークのTracerでも効果が現れており、
Tracerような一時オブジェクトを使用して計算するようなベンチマークで効果があります。
また、JavaのAOBenchにおいてescape analysisを無効化すると、
20-30％程度パフォーマンスが落ちるくらいであり、
Store Sinking追加によるTracerのパフォーマンス向上は妥当だと考えています。

Inlining系に関してはまた後日。
Dart VMのinliningはAn adaptive strategy for inline substitutionが元になっています。
またJVM(opto)の評価アルゴリズムと、polymorphismとの絡みも合わせて紹介できたらなと思います。