Gauche:VMの最適化:VMLoopの自動生成

0.8.13時点では、GaucheのVM本体はCを使って巨大なswitch文を手で書いてある(gccを使う場合はswitch文じゃなくて間接ジャンプになるけど)。 Google Tech Talkでもちょっと触れたけれど、個々のインストラクションの処理の定義をもとにこのでかいディスパッチ部分を自動生成したいというのをもう4〜5年考えていた。手動で書いてるデメリットはいくつかある。

実行頻度の高いインストラクションの組み合わせをひとつの結合インストラクションにすると性能が上がることは既にわかっているのだが、そうやって結合インストラクションを増やして行くと、vm loop内に重複するコードがたくさん出てくる。マクロとか共通部分を別ファイルにして複数回includeするなど姑息な方法で重複を回避しているのだけれど、それでもまだ重複は目立つ。
インストラクションを変えた時に複数箇所をいじらなければならない。 0.8.13現在では、例えば新しいインストラクションを追加するには(1)vminsn.scm にインストラクション定義を追加 (2)vm.cのループをいじってインストラクションの本体の処理を追加(3)結合インストラクションの場合、code.cのコード生成部に結合ルールを追加。これはとても煩わしい。
変更が面倒だと、色々試すのが億劫になるため、vmがいつまでたっても最適化されない。

で、最近性能面でライバルが出現したのでよっこらしょと手をつけることにした。既にレールは敷いてあったので一息であった。

vminsn.scmの変更

vminsn.scmのdefine-insn本体に処理内容を含める。これは cise (gauche.cgen.cise) を使って記述。マクロが使えるので細かいバリエーションがある場合も記述を共通化できる。

ciseマクロは、インストラクション結合による処理のちょっとした変化を隠蔽するのにも使っている。

結合インストラクションは原則として「どのインストラクションを結合しているか」だけ定義しておき、元となるインストラクションの処理内容をもとにコードを合成する。

vm loopの置き換え

vminsn.scmから生成されるvminsn.cに処理の本体部分がずらずらと並んでいるので、それをvmのrun_loopの中から#includeする。

インストラクション結合器の置き換え

vminsn.scmのインストラクション結合の定義から、インストラクション結合器が取るべき状態遷移ネットワークを生成し、code.cのコード生成部をそれを使うように変更。

実は状態遷移ネットワークを出すところまではもうずいぶん前に出来ていたので、code.cの方をちょろっと変えるだけだった。

ここまでの結果

これで、例えば頻度の高いLREFとRET、LREFとNUMADDIなどを複合インストラクションにしてみると、takで25.91s -> 21.77s。 16%程度の高速化である。

(注：2008/07/03 01:28:47 PDT現在、まだこれらの複合インストラクションは commitしてないので、trunkをそのままコンパイルしても速くはならない。)

インストラクションの幅

これまでは、1ワードのインストラクションのうち下から8bitをopcode、そこから20bitをパラメータとして使っていた。4bit余っているのはインストラクションが ScmObjだった頃にタグがついていた名残り。

結合インストラクションが増えてくると8bitでは足りないので 12bitに拡張することにする。

既にプリコンパイル済みのvm codeバイナリとは互換性が無くなるので、trunkを追ってる人は svn upしたらmake cleanして綺麗な状態からビルドすべし。

単純な命令結合では嬉しくない場合

命令結合の第一の効果はVM命令フェッチとディスパッチのコストの削減だが、「操作対象をPOPしている命令」のPOP元がLREFだった場合、すなわち

  LREF             ; 最初の操作対象(a)をval0にロード
  PUSH             ; そいつをスタックにpush
  LREF' or CONST   ; 次の操作対象(b)をval0にロード
  op               ; (a)と(b)にopを適用

というシーケンスにおいて、LREF-opという命令を用意し、「LREFで持ってきた(a)とVAL0にある(b)とにopを適用」というふうにするとスタック操作が二つ減る。これは多分大きい。

ところがこの場合、結合後のインストラクション列は次のようになる。

  LREF' or CONST   ; (b)をval0にロード
  LREF-op          ; (a)をLREFで持ってきて(a)と(b)にopを適用

現在の結合器は隣接するインストラクションしか見ていないのでこういう変換はできない。

これはむしろコードジェネレータじゃなくてcompile.scm側でやるべきかな。

試しに数値比較分岐 (BNLTとか) でやってみた。takで3%程度の高速化。

*-PUSHなどの命令の共通化

複合命令追加の土台が整ったので色々試してみた。 takで20sを切る(23%高速化)くらいまでは確かめた。

ただ、簡単に命令数が爆発する。LREF*と融合させると10個単位で増えるし。

で、値を生成するインストラクションについてはPUSHと複合させることが多いから、いっそのこと値をVAL0に残すかPUSHするかはインストラクション内に設けたフラグで判別したらどうかと思った。それならインストラクション総数を増やさずに全てのインストラクションにPUSHのバリエーションをつけられる。

懸念としては、インストラクションの処理中にフラグを見て分岐が入ることだ。ほぼ全てのインストラクションで起きるのでペナルティが大きそうな気はするが、やってみないと本当のところはわからない。 (なおこの実験ではインストラクションコードが変わるので、 Gauche:VM命令セットの変更とビルドで述べたように0.8.13で素直にコンパイルできなくなる。なので含めるとしても0.8.14より後になるだろう)