Gauche:VMの最適化:For 0.8.4

0.8.4に入った最適化についてのメモ。

中間コード形式の置き換え

(2004/12/22 15:46:21 PST)

0.8.3までの中間コードは、有向グラフを使っていた。基本的にはコンパイル結果は単なるVM instructionのリストで、リスト終端に達したらcontinuation stackのトップをpopする。オペランドの必要なVM instructionはリストの次の要素に直接オペランドが入っている。また、いくつかのinstructionでは分岐が入る(例えばIFは、次のセルのcarがthen節、cdrがelse節)。合流やループにjump命令は要らない。

この表現は簡単だし、コンパイルが1パスで済むし、面倒な中間コードフォーマットを考えなくてもいいんで、とりあえずの形式として採用していた。ただ、欠点もある。コードをただベクタに並べた形式に比べ、インストラクションへのアクセスでメモリ参照が倍になるとか、デバッグ情報をつけにくい (現在のpcの後しか見えないので、広いコンテキストで見ることができない)、等だ。また、コンパイラに入れたい最適化がいくつも溜っているのだが、現在の1パスコンパイラの形を保ったまま最適化コードを入れて行くことにも限界がある。本音では、SchemeコンパイラをCで書くのはいいかげん面倒になってきたということもある。

というわけで、中間コード表現をベクタ形式に変えたいというのをもう2年前くらいから考えていたのだが、ようやくまとまった時間と気合いが取れそうなのでここで一気にやることにした。

戦略

中間コード表現は、コンパイラとVMのインタフェースでもあるんで、それを変えるには、コンパイラとVMの両方を変更しなければならない。しかし、「2箇所を同時に変える」というのは鬼門である。特に今回のような大きめの変更では、破滅へのレシピになり得る。そこで、まず現在のコンパイラ出力を新しい形式に変換するスタブを開発し、 VMをそれにあわせて変更し、動作を確認した上でコンパイラを変更することにする。

さらに、「常に動くコードを手元に持っておく」方針から、一回一回の変更をマネージ可能な大きさにブレークダウンし、各段階で十分な検証とベンチマークを取りながら進める。

Step 1. 旧コンパイラ出力から新形式への変換スタブ (了)

新形式では、コードを従来のリスト構造からベクタにパックする。合流やループの部分はJUMPインストラクションで置き換える。

即値データは従来通りコードベクタ中に直接配置するが、コードベクタ全体をGCにスキャンさせるのは無駄が多いので、コードベクタ自体はatomic (GCがスキャンしない) としてアロケートしておき、保護の必要な即値データだけを別ベクタで持つ。

デバッグ情報はとりあえず無視。

この段階で、新形式のコードをダンプする一種のディスアセンブラも作成し、変換スタブとディスアセンブラをSchemeから呼べるようにしておく。そうすればインタラクティブに試せて、目視ながら動作確認もできる。

Step 2. VMの変更 (了)

VMを変更。run_loop自体はさほど面倒ではなかったが、 VMApplyとかグラフ形式べったりの部分が結構多くて手間取った。

この段階では、#ifdef で変更箇所を区切っておいて、トラブったらいつでも戻して比較できるようにしとく。

テストを通してバグを取り、アプリケーションコードを使ってベンチマークを取りながら、新形式を若干調整。この段階で十分バグを叩き出しておくと後が楽。 (この段階でフルセットのサポート、つまり以前のVMと完全互換になるようにしておく。後でサポートを追加した際に予期せぬVMの変更が必要になって、複数箇所を同時にいじる羽目になるのが嫌だから。)

この過程で、ベンチマーク用に内部の統計情報を取る必要が頻繁に出てきたので、実行時フラグによって統計情報を集められるコードをVMに追加した。

Step 3. デバッグ情報の追加 (了)

新形式にデバッグ情報を追加し、VMでのエラー時に取り出せるように変更。 compiled codeとその時点でのpcの値からデバッグ情報を検索する。これに伴い、コンパイラの方にも一ヶ所手を入れる。以前の方法では PRE-CALL/PRE-TAILに呼ぶべき関数の情報がついていたのだが、それを CALL/TAIL-CALLの方に移す。pcから探すのにそっちの方が都合がいい。

環境フレームのinfoの位置づけが曖昧になった。LET/RECEIVEで導入されるフレームの変数が何かって情報を効率良く付加したいのでちょっと置いておく。 pc位置と継続フレームから手繰れるなら1ワード減るから好都合なんだが。

一応、旧バージョンと同じ機能はほぼ達成されたので、ここで#ifdefを消す。 gauche.vm.debuggerが動かないが、これは改めて考えるしかなかろう。 gauche.vm.disasmは、同等の機能がstep.1で実現されてしまったので削除。

とりあえずここまでのをNVM0_8_3ブランチとしてcommitしとく。

Step 4. 中間コード形式のチューニング (了)

step.3 までの段階でベンチを取ると、意外なことに0.8.3より遅くなるケースがある。んー、スタブによる変換のオーバヘッドはコンパイル時だけだし、メモリアクセスが減る分、多少速くなるんじゃないかと思っていたのだが。

本格的に速度を目指すのはコンパイラに手をつけてからだが、前より遅いのは悔しいのでちょっと中間コード形式をいじる。

VM_INSNオブジェクトではなく、タグ無しのVM instructionを使う。もうリストじゃないから、インストラクションがScmObjである必要はない。タグ無しにすることで、ディスパッチの際のシフトが不要になる。
JUMP等の飛び先を、オフセットでなくコードベクタのアドレスにする。これも、コードベクタの内容がScmObjである必要がないからできた。
即値オブジェクトを直接置くんじゃなくて、CONSTというinstructionのオペランドにする。昔の形式では、VM_INSN以外のオブジェクトが出てきたら即値、ということにしていたのだが、実は即値ってそんなに多くない (頻繁に出る小さな整数や() はinstructionに取り込まれているため)。ディスパッチの度に、VM_INSNか否かの判定が入るのは無駄。

これで、多少だが0.8.3より速くなった。

Step 5. 中間コード→Cのデータへの変換 (了)

コンパイルしたコードベクタをCコードのstatic dataとして吐き出し、 libgaucheにリンクできるようにする。コンパイラ自身をSchemeで書くのに必要。

留意点。

あらゆるGaucheコードに対応するのはかなり大仕事になるので、とりあえずコンパイラを書くのに必要な分だけをサポートすることを考える。ただ、どれくらいのサポートが必要かはコンパイラを書いてみないとわからないから、基本的なところを動くようにしておいて、後はコンパイラを書きながら徐々に足して行くことにする。
一度Scheme->Cを使って得たCコードをlibgaucheにリンクしてて、それにバグがあってgoshが実行できなかった場合、リリース版goshではこのScheme->Cスクリプトを走らせることが出来ないので、はまる。 Scheme->Cスクリプトが走る暫定版を適宜インストールしながら作業を進めることになる。

もうひとつ落し穴があったのでメモ。

このステップは、その時点でインストールされているGauche (host) を使って実装中のコンパイラ (target) をコンパイルし、得られた VMコードをダンプする。これでは、新しいVMインストラクションを追加したり、 VMインストラクションの順番を変えたりした場合、hostでコンパイルした結果をtargetとなるGaucheで実行することが出来ない。生成したコードベクタのVMインストラクションと、targetのVMが使うインストラクションが一致しないからだ。

現在は、hostは自身を使ってコンパイルした命令列を自身のVM インストラクションセットを使ってニーモニックに変換し、それを targetのインストラクションセットを使って命令コードに直してダンプするようにしている。ニーモニックのリネームが若干トリッキー。

Step 6. コンパイラの変更#1 (了)

まずは現在のCで書かれたコンパイラをSchemeにして、 Step 4.の変換を通してlibgaucheにリンクし、動作を確認。

旧コンパイラは大きくわけて次の3つのコンポーネントから成っていた。

ドライバ (再帰的にフォームを手繰って、変数参照や関数呼び出しを処理し、また適切なマクロや構文ハンドラを呼び出す)
組み込み構文ハンドラ
マクロ

当初はそれぞれを順次置き換えてゆく予定だったが、各コンポーネント間のAPIはCで呼ぶことを前提に作られているため、 Scheme側とのやりとりが面倒になることに気づいた。特にドライバと組み込み構文ハンドラのインタフェースが 1パスコンパイラに特化していてむしろいじりにくかったので、結局ドライバと構文ハンドラを同時に置き換えてしまった。

R5RSマクロはちゃんと作るのが少し面倒なので、スタブを噛ませてしばらく古いCの実装を流用する。

組み込み関数のインライン展開部分も、旧コンパイラはCに特化したAPIで使いにくいのでばっさり削って、新しく作りなおす。

この段階での注意点だが、コンパイラ自身が使う関数は全てコンパイルインされていなければならない。外部Schemeライブラリの関数を呼んだりすると、それをloadする際にコンパイラに再入してしまうからだ。このため、いくつかのsrfi-1関数などをコンパイラ自身が重複して持つことになった。このへんは後で整理しなければならない。

構文ハンドラの部分はGaucheRefj:matchが使えるのでえらく楽に書けた。 matchはマクロで、展開された結果には基本的な関数しか含まれないから、上に述べたブートストラップ問題が発生しない。それ以外でもマクロを多用している。

Step 7. プロファイラ (了)

こっから先は最適化だ、とはりきっていたのはいいが、使い物になる(Schemeレベルで何が起こっているかわかる)プロファイラが無いとまともな最適化など出来ないことに気づく。

というわけで横道に逸れてプロファイラを書く。まずはITIMER_PROFを使ったサンプリングプロファイラ。 itimer回りはどのくらいポータビリティがあるかよくわからないし、マルチスレッド環境下での動作についてのドキュメントがあんまり見つからないんで、正式サポートまでは時間がかかるかもしれんが、シングルスレッド、Linuxという条件ではすぐに出来た。

ところが、コンパイル時にScheme関数は全て無名lambdaになってるので、「現在実行中のコード片」をサンプルできたはいいが、それがどの関数なのかわからない。そこでわかる範囲でコードのデバッグ情報に名前を付加して行くしくみを組み込む。

プロファイラを作る方に真面目に取り組んだのは初めてだが、プログラムの中で何が起きているのかがだんだん目に見えるようになって来るのは楽しい。

続いてcall counterも付加。これは若干intrusiveで、プロファイラが走っていない時でもScheme関数呼び出し一回毎にフラグ一回のチェックが入る。この影響は計測によれば1%程度なので、今のところは利便性が勝るだろう。

まだマルチスレッド対応などに課題はあるものの、単一スレッドではそれなりに使い物になるようになってきた。これは現段階でのプロファイラの出力の一例：

Profiler statistics (total 1521 samples, 15.21 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
call-syntax-compiler                                168420  0.0062   105(  6%)
iacc-emit!                                         1338220  0.0007    92(  6%)
pass3/rec                                           878080  0.0010    90(  5%)
cenv-lookup-rec                                    2426220  0.0004    87(  5%)
(make <class>)                                       13200  0.0576    76(  4%)
pass1/expand-inliner                                 67260  0.0110    74(  4%)
require                                               3080  0.2110    65(  4%)
vm-insn                                            1348560  0.0004    60(  3%)
pass1/global-call                                   367560  0.0014    50(  3%)
pass1                                               677620  0.0007    49(  3%)
find-binding                                        427260  0.0011    47(  3%)
vm-insn-inspect                                     502960  0.0008    38(  2%)
vm-pack-code                                         56400  0.0062    35(  2%)
(pass1/body pick-intdefs #f)                         70260  0.0040    28(  1%)
cons/info                                           960400  0.0002    23(  1%)
(pass1/global-call %internal-apply)                 185640  0.0012    23(  1%)
...

まだgcを分離して測っていないので、gcの時間はそれが起きた時点で実行されていた関数に算入される。allocation intensiveなプログラムでは特にgc別のプロファイリングも欲しくなりそうだ。

ただ、現段階のデータでも、ソースをいじりながら眺めていると色々わかることがある。

クロージャの作成が結構重い。これはクロージャ作成時点で外側の環境フレームをスタックからヒープへセーブするためだろう。特にinner loopで呼ばれる関数内で深くネストしたスコープの奥でクロージャを作っていると、セーブされる環境フレームのチェインが長くなるので重くなる。やはりちゃんとクロージャの束縛の追跡を行って、インライン展開やトップレベルへの括り出しを行わないといかんだろう。
一方、関数の呼び出しは思ったより軽い。グローバルな関数をマクロにしてインライン展開させるのは、よほど対象関数の本体が小さな処理でない限りはあまりメリットがない。まあ、使いどころが無いわけではないので、define-inlineみたいなのを将来つけても良いだろう。
インストラクションセットをいじる (頻出するsubrを専用インストラクションに置き換えたり、インストラクション結合を行ったり) のは、劇的な速度向上には結びつかなさそう。ひとつ改善するたびに1%の向上とか、そんなもん。 (もちろん、その改善がinner loopで効いてくるようなベンチを使えば改善効果は大きく出るけれど、現実のアプリで測るとその効果はずっと薄まる)。積み重ねてゆけば馬鹿にはできないけれど、順序としてはむしろ後回しにすべきだろう。フロー解析を真面目にやる方が改善のオーダーが大きいようだ。

コンパイラ自身の動作がCで書いていた頃に比べもっさりするのが嫌なので、プロファイリングしながらコンパイラ自身をチューニングしている。

Step 8. コンパイラの変更#2 (了)

コンパイラが直接新形式のコードベクタを吐くようにする。これを以ってStep 1.のスタブは役目を終了することになるので、コードを一気に整理。以前のcompile.cはほとんど中身が無くなってユーティリティ関数だけになったのでcompaux.cと改名し、 Schemeで書かれたコンパイラ本体をcompile.scmとした。

ここまでで当初の目的は達したのだが、VM最適化の過程でインストラクションセットをいろいろいじっていて、ビルドプロセスが面倒なのだ。(インストラクションセットを変えた場合、既存のgoshで一回「インライン展開無し」でcompile.scmをコンパイルして、出来たgoshを使ってもう一回普通にcompile.scmをコンパイルする必要がある)。インストラクションセットがもう少し落ち着いたらtruncにマージするつもり。

VMレジスタの持ち方

現在のVMでは、pc, sp, val0 (値レジスタ), env (環境へのポインタ), cont (継続フレーム), argp (積みかけの引数フレームの底) をVMレジスタとしてループの頭でローカル変数として宣言している。レジスタリッチなプロセッサならこれらがレジスタに載ってくれるんじゃないか、という期待でそうしていたんだが、ループの外の手続きを呼び出す場合の多くはこれらをvmの中に一端セーブして、戻って来たところでリストアしなければならない。

x86だとこれらの「レジスタ」は結局スタックアロケートされちゃうようなんで、実はあまりメリットは無いのかもしれず、むしろSAVE_REGSとRESTORE_REGSの分がオーバヘッドになっている気がしてきた。そもそもひとつだけマシンレジスタに載せられるならVMへのポインタが載ってくれれば、他はそこからのレジスタ相対でのアクセスになるから、スタックアロケートされたローカル変数へのアクセスと変わらん。

そこで色々レジスタの組合せを変えてベンチを取ってみる。やっぱり相対アクセスが一段増えるデメリットと、SAVE_REGS/RESTORE_REGSが軽くなるメリットがせめぎあっているようで、アプリのインストラクションのパターンによって良くなったり悪くなったりするが、大まかな傾向としては下手にローカル変数化しない方がよさげ。なんと、ローカル変数無しでVMへのポインタから相対アクセスしても、現状より若干速くなるのだ。結構意外。

これは現在のスナップショットでのベンチの一部。 'o' はレジスタをローカル変数にしたこと、 '-' はレジスタを vm->pc 等のようにアクセスしていることを示す。最後のカラムは0.8.3での数値 (CPU時間)。

VM regs   pc   o      o      o      o      -  |
on local  sp   o      o      o      o      -  |
        val0   o      o      o      -      -  |
         env   o      o      -      -      -  | 0.8.3
        cont   o      -      -      -      -  |
        argp   o      -      -      -      -  |
Bench                                         |
-----------+------+------+------+------+------+------+
tak         42.51  39.03  44.73  40.40  37.60 | 51.42
compplot    23.41  22.95  23.03  22.72  23.19 | 23.31
ssax        16.52  16.32  16.11  16.24  16.47 | 19.20
tex2page    60.90  58.55  60.75  57.32  57.17 | 65.84
-----------+------+------+------+------+------+------+

別のCPUでやったらどうなるかわからんし、gccのバージョンでも変わるかもしれんし、今後コンパイラや VMインストラクションセットもいじるので、まだ結論は出さずにおく。

registerつけておまじないをかけてみれば？
Shiro: 今手をつけている変更が一段落したらやってみます。ただ感触として、 Gauche VMの個々のインストラクション自体が中でやっている処理が多くて、レジスタを食うんですよね(しかもその傾向は今後複合インストラクションを増やすにつれ顕著になる)。だからpcやsp へのアクセス頻度って思っている程高くないのかなと。もしそれらをレジスタに貼りつけて、そのせいで他の一時変数がスピルするとしたら、あまりメリットも出ないんじゃないか、というのが今の予想。それと、registerの解釈はコンパイラ任せなんで、gccのあるバージョンでよかったからといって全面的に採用して良いものかどうかってことも (registerが効かなくてもまあ良い、というならともかく、今回の場合 registerが効かないのならvmポインタからの間接参照の方が良い、という話なので)。
gniibe: 最近のGCCでは、-On (n>0)の場合、registerの指定は(ほぼ)なんの意味もない...となっていると思います。うーんと、説明は見つからないのですけど、マニュアルの関連記述。http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Hints-implementation.html#Hints-implementation

(2005/04/11 03:21:42 PDT): ライブラリ呼び出しをほとんど行わない、takのようなベンチマーク関数の場合、vmへのポインタがレジスタに載らずにspillするとそれだけで50%くらい性能が低下する。もっとも現実的なアプリの場合は影響がせいぜい3%くらいなんで、 takのような特殊なベンチマークの数字だけを見てあまり神経質にならなくてもよいのかもしれないが。spillする条件がようわからんのがいやな感じだ(必ずしもコードが多くなるとspillするわけではなく、コードを削ってspillすることもある)。

(このことは、ベンチマーク関数の選定の危険性も示している。 VMのタイトループ内での性能差が現実のアプリで観測されるものより誇張されるようなベンチを使っていると、重箱の隅をつつくような最適化に走りがちだ。実際には、よりグローバルな最適化、例えばクロージャ解析に力を注いだ方がずっと得られるものが大きい。もちろん、最後の数%を詰めて行く時に敢えてその差が強調されるようなベンチを使うことは意味があるだろうが。)

Inlining map, for-each

(2005/05/14 12:36:59 PDT) mapやfor-eachに直接lambdaフォームが渡されている場合、 map、for-each自体をインライン展開すれば、lambdaフォームもインライン展開される。クロージャ作成が重い現状では結構なgainになるかもしれない。

と思ってやってみたんだが、意外にたいしたことはなかった。わずかに改善される場合もあるが、コード量の増大に見合うメリットでもないような気がする。

クロージャを作るlossと、mapがCで書かれていることによるgainがほぼ相殺してるってことかね。とするとVMの性能全般を上げてゆくか、あとはクロージャのfree variable追跡をやってdisplay frameを作ることで、クロージャ作成時に環境フレームをひとつだけ保存すれば良いようにする (mapが使われる場面のほとんどはそういうクロージャのはず)か。ただfree variable追跡はコンパイルがさらに重くなるから考えもんだなあ。

Lazy compilation

(2005/05/15 03:51:13 PDT) コンパイラをがんばったおかげで、実行時性能は0.8.3に比べかなり改善した。現時点でのいくつかのベンチマークはこんな感じ。 (user timeの平均 on Pen4 2GHz/Linux/gcc-3.2.2)。

	HEAD	0.8.3	備考
tak	27.80	52.83	(tak 24 18 6)
anc2	12.42	21.55	Scheme:アンカーパチンコ
rgs	8.41	13.48	Random Graph Server
ssax	12.89	21.80	XMLのパーズ
compplot	13.94	23.09	複素関数のグラフ

まぁ、改善と言ってもいきなり10倍とかは無理。もひとつ飛躍するには型推論してboxしてないデータで演算するとかしないとダメかも。あと、Object System回りは最適化に全然手をつけてないのでそんなに効果が現れないだろう。また、VM回りを最適化したせいでGCの占める割合が相対的にかなり高くなってきている (25〜40%)。そっちのチューニングも必要。

さて、コンパイラががんばった副作用として、コンパイル時間は増大した。 1パスでやってたものを色々最適化をかける3パスにしたんだから無理もないんだが、スクリプトインタプリタとしてはコンパイル時間も無視出来ないファクタだ。実際、実用サイズのプログラムを読ませると、ロード時間そのものは倍くらいになっている。

	HEAD	0.8.3
gosh -uscmail -Eexit	0.32	0.16
gosh -uwiliki -Eexit	0.55	0.27

これはあんまり嬉しくない。コンパイラそのものは既にかなりかりかりとチューンしていて、劇的な速度向上は無いだろう。

ロードしたコードが全部使われるということはあんまり無いだろうから、ロード時に例えばPass 1だけコンパイルした状態にしておき、実行が必要になった時点でPass 2とPass 3を走らせるという手を検討してみよう。

skimu: をを、この数字僕がなんとなく予想してたよりずっといいです。コンパイラが VM で実行されてしかも最適かもこんだけ頑張っても時間が倍にしかならないなんて意外です。すごい。　ファイルの読み込みが占める時間が結構あるのでしょうか？
Shiro: コンパイラ自身にかなり最適化をかけていて、上記Step 8の時点からすると3倍くらいのスピードになっています。最もクリティカルなルーチンは Cで改めて書き直していますし。

基本的には、compileでpass1だけを走らせた時点で中間表現IFormを保存した <compiled-code>を返し、実行中にコンパイルが済んでいない<compiled-code>に当たった時点でpass2, pass3を走らせてコードベクタを生成すれば良い。ただ、マルチスレッド環境下では、同じ<compiled-code>に対して複数のスレッドが pass2-3に同時に入ってしまう可能性がある。コンパイラ本体はreentrantに書いてあるのだけれど、中間表現であるIFormは一時的なデータ構造ということで pass2で破壊的変更をしまくるので、複数スレッドに触らせるのはまずい。

<compiled-code>にmutexを持たせるのは重くなり過ぎて論外。 pass2で関数的にIFormを再構成するようにすれば綺麗だけど、アロケーションが増えるなあ。アトミックな1ポインタのみの変更で、pass2への突入を排他制御できる方法はないだろうか…

skimu: マルチスレッド対応ならば、コンパイル専用のスレッドを走らせて、コンパイルはすべてそのスレッドに任せる、というのはいかがでしょう？マルチスレッド対応でない環境ではそれをエミュレートするコードを入れておく、といった具合。思いつきですが。。。

色々調べながらやるので別ページに移動→Gauche:LazyCompilation

(2005/05/23 04:12:12 PDT): あまりここにこだわっていても先に進まないので、 0.8.4はLazy Compilation無しでゆくことにする。ちなみにさらにコンパイラのチューンを進めた結果、コンパイル時間は倍よりは少し小さくなった。

	HEAD	0.8.3
gosh -uscmail -Eexit	0.27	0.16
gosh -uwiliki -Eexit	0.47	0.27