2008年06月
細々と続けている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倍以上速くなった。めでたしめでたし。
コメント(1) | トラックバック(0) | ゲーム機の技術
米国内で働いている人は、例外を除いてみんなそろって年度末（毎年四月）に確定申告（Tax Return）をする。寄付や経費の控除も（知っていれば）できるのでみんな真剣だ。確定申告締め切りの四月十五日前後に、郵便局が混雑するのも街の風物詩である。
Tax Returnをすると税制がよくわかるので、全員Tax Returnすることに、僕は賛成。ただし、みんなが申告する分、税務調査（Tax Audit）の恐怖も皆に等しく訪れる。多くの人が語るところではTax Auditは抜き取り式の調査で、よっぽど運が悪くないと引っかからないらしい。ただし万一引っかかると、徴税ノルマを抱えた税務官が隅から隅まで本気（マジ）で調査するということで、とてもとても恐ろしい。
さて、これは本当にあった恐怖のお話。
二月某日
税務署（IRS）から分厚い封筒が届く。分厚い時点で中身はひとつしかないのだけれど、ビクビクしながら開封。
まずは車一台分くらいの請求書を見て、夢を見ているのかと思いたくなる。
内容は一年近く前の2007年度分のTax Returnについて、支払い請求書だ。質問ではなくて、いきなり請求書から来るところがまた怖い。
申請してから一年近く経っているので、10％程度の利子もバッチリ請求。利子を増やすためにワザと寝かせているのでは、と邪推してしまうが多分そのとおりなんだろう。
中身は前職での社内持ち株会（ESPP）の申請について、ということで実は一安心。これまでも、同じ内容のAuditが何回かあったため。
給与処理の都合で、ESPPで得た利益は給与明細にすでに含まれているので、あえて別枠の株取引としては申請していなかった点への指摘。確かに通常の株式売買の申請方法とは違うため、まぁチェックが入ったとしてもおかしくはない。株式売買や銀行の利子、給与明細などの書類は税務署に電子的に転送されているため、これをきっちり申請しないと機械的に監査の対象になる。
こういうときは、あわてず騒がずお手紙（Letter）を書く。Letterの内容は恥ずかしながらこんな感じ。文中"W-2"とあるのは所得明細のフォームのこと。
Dear IRS.
Re: notice of proposed changes (Notice Number: CP2000)
As I reviewed my tax return of 2007 carefully, it turned out all the points indicated are related to the employee stock purchase plan of 会社. I think all of those profits are already reported in W-2 (14 other, amount of 金額 DSQDSP) and federal income tax was withheld already.
I enclosed a copy of W-2(from 会社) and form1099-B (from broker). Please review those and process it appropriately.
Sincerely.
Hakuro Matsuda
2/**/08
証拠書類の（原本ではなく）コピー、税務署からの請求書を同封して郵送する。請求書には、「全額認めて払う」、「一部とりあえず払う」の二択しかないのだけれど、強気でどちらも選ばない。
郵送には Certified Mail（日本で言う書留）等の到着確認をつけることを忘れずに。米国の郵便事故はかなり多いし、無事に到着したとしてもCertifiedがついてないと、そのまま闇に葬られることも、時々ある。
このあと、数週間経つとIRSからお手紙が来る。
「資料は受け取りました。（必ず）連絡するから待っていてね」
トホホだ。
四月某日
忘れたころに、IRSから封筒が届く。
またしても分厚いので意気消沈しながら開封すると、前の内容については何もなかったことになっていて、ぜんぜん別件の指摘。しかも金額は1/3程度に減少している。
一歩前進ではあるが、泣ける請求であることは変わらない。
中身は、前職のストックオプション行使について。
ストックオプション取引の際に、所得税が天引きされていたのだけれども、通常の株式取引ではそんなことはしない。このためか、税金が支払われていないと扱われていて、追徴の請求。
これは奇妙な話で、ストックオプション行使の書類はIRSの元にもブローカーから届いている。ちょっと深読みしてしまうと、この辺で手打ちにしようというIRSからのシグナルとも受け取れてしまう。
と一瞬弱気になったが、弱みを見せると徹底的についてくるのがこういった家業の方々。
こちらも、あくまで強気でお手紙第二段を送る。Form1099とあるのはブローカーからの売買明細書。
Dear IRS.
Re: notice of proposed changes (Notice Number: CP2000, Control Number *****-****)
As I reviewed my tax return of 2007 carefully, I think “Amount Reported to IRS by Others” amount shown in the notice does not include Form 1099 amount that I received from ブローカー. And as I added the amount to reported number, it matches an amount that I reported in my tax return.
I enclosed a copy of 1099 from ブローカー. Please review those and process it appropriately.
Sincerely.
Hakuro Matsuda
4/**/08
数週間経って、またしてもIRSからお手紙が来る。
「資料は受け取りました。忘れず待っててね」
六月十四日
忘れたころに今度は薄っぺらい封書がIRSから届いた。
勝利の瞬間:)
CLOSING NOTICE
Thank you for providing us with additional information about the issue we recently wrote to you about. We are pleased to tll you that , with your help, we were able to clear up the differences btween your records and your payers record. （以下略、全部なかったことにね♪）
こうして、今年も無事にTaxAuditを乗り切ることができた。神様ありがとう。
特にやましい事がないとしても、巨額の請求書を見るのは気分の良いものではない。トラブルを避けるという観点からは税理士に申告をしてもらうのも割に合っているだろう。
とはいえ、自分でAuditを乗り切ることも中々面白いものだ。自分の正当性を合理的に主張して押し切るっていうのはアメリカ人は小学校から訓練されているけれども、自分にとってはまだまだ未知なことも多い領域。偶にはAuditを受けるのも悪くはないな、と1マイクロ秒位は思ってしまった今日この頃だ。
Tax Auditに関する日本語の顛末は下のBLOGにも詳しい。みなさん苦労してますなぁ。
http://www.cotton-tree.com/garyu/archives/2007/01/irs_tax_audit.html
コメント(3) | トラックバック(0) | お猿なひととき
