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

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

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

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

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より後になるだろう)

More ...