Gauche:VMの最適化:For 0.8.4

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より 遅くなるケースがある。んー、スタブによる変換のオーバヘッドは コンパイル時だけだし、メモリアクセスが減る分、多少速くなるんじゃ ないかと思っていたのだが。

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

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

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

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

留意点。

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

このステップは、その時点でインストールされている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別のプロファイリング も欲しくなりそうだ。

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

コンパイラ自身の動作が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インストラクションセットもいじるので、まだ結論は出さずにおく。

(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を走らせるという手を検討してみよう。

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

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

色々調べながらやるので別ページに移動→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
More ...