2008年06月27日(金)
VMの高速化にチャレンジ
細々と続けているCriScript(http://www.criscript.com)。
今回はVMの高速化に挑んでみた。高速化は機能実装を進めてから手をつけようと思っていたのだが、魔がさしてちょっと現状を計測してみようと思ってしまったのが運の尽き。
計測に使用したのは↓のサイトにある100x100のマンデルブロート集合を算出するもの。
http://shootout.alioth.debian.org/
こちらのサイトでは各種言語でのベンチマークを比較していて面白い。
C++やJScriptはもちろん、LUAやPython用等等のスクリプトファイルが用意されているのもうれしいところ。
早速Python、LUA(非JIT)と比較計測してみると、、、
| Python 2.5.1 | 320msec |
| LUA 5.1.3 | 190msec |
| CRIScript 0.9.10 | 690msec |
５回程度計測してベストタイムを採用
遅い、あまりに遅すぎて蝿がとまりそうだ。
これだけ遅いと流石に放置もできないので、予定を繰り上げて最適化することに。
なお、LUA、Pythonと比較しているのは、ゲームエンジンへの組み込み実績としてはダントツLUA、時点Pythonといったところによる。
●準備
最適化環境にはまずはプロファイラが必須。今回はPC上での最適化のためIntelVtuneを使った。
http://www.intel.com/cd/software/products/asmo-na/eng/vtune/239144.htm
Vtuneは30日まで使用可能な評価版が上記リンクからダウンロードできる。
機能的には関数毎の経過時間しかわからないためやや物足りないが、所期の目的としては必要十分だろう。
また、IA32の最適化はPentium3以来なので、マニュアル等も下記から取得。
http://www.intel.com/products/processor/manuals/index.htm
特にOptimizationReferenceManualは有用だ。
●方針
バイトコード実行式のVMの場合、実行時間の最適化を行なう余地は大別して三つ。
1)VM最適化
VMの実行速度を最適化
2)コード生成最適化
コンパイラの生成するバイトコード列を最適化
3)元コード
いわゆる最後の手段としてここでは考えない
汎用性から言うと
VM>>コード生成>>>>>元コード
となるため、このプライオリティで最適化に励むこととする。
IA32は、大抵のコードでIPC(Instruction Per Cycle：1サイクルあたりの命令実行数)が1.0近辺がでるという素晴らしいCPUだ、最高。このため基本的には命令数を削減した分、素直に実行時パフォーマンスが改善すると想定して良いかと思う。（なお、Core2Duoの理論IPCは5だが、理論IPCという場合、命令発行ユニットの幅を示しているだけなので実際の値とは乖離しているのが普通）
一方、例えばIPCが0.2に届かないようなアーキテクチャの場合、パイプライン・ストール/フラッシュをチクチク潰していく様な最適化がより有効になる。
最適化の手順としてはアルゴリズムの最適化が重要と一般に言われる。これは8割5分がた正しく多くのケースでアルゴリズムの最適化がかなり効果的だ。
ただし、残り1割5分のボトルネックを潰していく作業では、アセンブリのリスティング出力を見ながらの最適化がとても重要。とはいえアセンブリを直接、またはインラインアセンブリで書くのではなく、修正はあくまでC++のコード上で行なうのが良い。深いパイプラインを意識した命令並び替えは今日びのコンパイラに任せたほうがずっと楽だし、後述のようにインラインアセンブリコードを含む関数はコンパイラの最適化効率がグッと落ちてしまう。
●最適化作業
まず、VTuneでCRIScriptを計測した場合もほぼ1.0近辺のIPCとなった。いい感じだ。
VMのコードは主に下記のコードに。興味ある方はどうぞ。
0)VM処理をswitchからDirectThreadedへ
ContextThreadingの論文を参考にしてswitch処理からDirectThreaded処理へ。
ContextThreading処理を実装するにはJITに近いフレームワークを実装する必要があるため、JIT実装時に先延ばしに。
DirectThreadedにラベルの参照テーブルとテーブル内ラベルへのJumpが必要なためinlineAssemblyを使っている。たいていのコンパイラでInlineAssemblyを使った場合、その関数内の最適化はしないか最低限になるためやや微妙。
果たして、実行速度も変わらず。
なお、GNUの場合はローカルラベルを参照できる&&拡張演算子（この定義は良くないが）が使えるので、もう少し違った結果が出るのかもしれない。
1)バイトコードアクセスをvectorからポインタ経由に
アセンブリ出力をみるとリリースビルドであってもSTLベクタの配列インデックス（[])アクセス時に冗長な範囲チェックコードが生成されている。
これはSTL"yvals.h"内の下記定義をコメントアウトすると回避することができる。
#define _SECURE_SCL 1
が、STLヘッダに手を加えるのも感触が悪いので、STL::vectorの使用をVMコアコードから排除することにした。
まずはバイトコードへのアクセスをポインタ経由で行なうように修正。
結果→648.015 msec
2)0)で行なったDirectThreadedディスパッチャのコード生成が芳しくないため、switch文に戻した
結果→552.092 msec.
この段階で20%削減。
このとき、VM上で実行されているバイトコード命令数は計11312209命令。
3)StaticFieldをベクタ配列としていたものをお取り潰し
結果→532.15 msec.
4)EvalStackをベクタ配列としていたものをお取り潰し
結果→359.839 msec.
一気に33%削減。
5)今度は汎用変数クラスCVariableに手をつける
実行インストラクション数を減らす方向で最適化
結果→303msec
6)一通り煮詰ったため、気分転換にコンパイラ・コード生成の最適化に手をつける
バイトコード生成後のストリームに対してパタンマッチングによる最適化を行なう、Peepholeオプティマイザ用のフレームワークを作成して、いくつかの最適化ルーチンを組み入れてみた
元命令数：11312209 inctructions
・フラグチェック命令と条件分岐命令を合成
命令数：11017964inctructions
・不要なDUP/POP命令を削除
命令数：10487276inctructions
・for(;;)条件式の分岐命令を最適化
命令数：9976788inctructions
・for(;;)条件式の分岐命令をさらに最適化
命令数：9725506 inctructions
・Logical ORのコード生成を最適化
命令数：8959774 inctructions
・LOOP末尾に出現するld/inc/st命令の合成
命令数：8429086 inctructions
上記のようなステップで実行命令数を約25%削減した。
結果→220msec
7)evalStackへのアクセスをインデクス→直接ポインタに
結果→203msec
8)evalStackのPOP時の変数内容クリアを最適化
結果→186msec
と、現状がここまで。当初実行時間の73%を削減できた。
まだ各種オペレータの最適化が手付かずのため、もう少し粘りたい。
●ついでにコンパイラの最適化も
ネストが深いスクリプトのコンパイルが妙に遅いという問題が前々からあったため、こちらもボトルネックを同定して最適化。
ボトルネックは LookUpSymbolInformationでの変数参照時の再帰処理時のstring処理。
(cilSymbolInfo.cpp内のCCilCodeGen::LookUpSymbolInformationSub)
元々手を抜いていた部分だったため驚愕のコードに。すみません治します。
これを修正したところ、体感では特定のスクリプトコンパイル時に10倍以上速くなった。めでたしめでたし。
リンク元(referer)
コメント
当社比3.7xは目を見張るものがありますな。さすが。
ch3 2008年7月7日 11:10
