Gauche:VMの最適化:For 0.6.3

0.6.3に入れた最適化についてのメモ。

VMの手続き呼び出しシーケンス周りのチューニング

applyのチューニング

以前のapplyの実装 (Scm_VMApply) は、「与えられた引数をpushして与えられた手続きをcallする」という一連のVMプログラムをon the fly で生成し、Scm_VMApplyから戻った後にそのコードが実行されるようにしていた。確かかなり前のフレーム構造で何か問題があってそういう手段を必要としたんだったと思う。

これを、Scm_VMApply内で引数フレームをスタック内に準備して、 Scm_VMApplyからリターン後直ちにSCM_VM_CALLインストラクションが実行されるようにした。

ものによってはこれでかなり速くなる。

  ;; 0.6.2
  shiro:toccata% time gosh -I. -I../lib -e "(for-each + (make-list 1000000 1))" -e "(exit)"
  6.650u 0.130s 0:06.83 99.2%   0+0k 0+0io 301pf+0w

  ;; 新バージョン
  shiro:toccata% time ./gosh -I. -I../lib -e "(for-each + (make-list 1000000 1))" -e "(exit)"
  2.830u 0.200s 0:03.05 99.3%   0+0k 0+0io 301pf+0w

環境フレームの構造の変更

以前のバージョンでは、環境フレームはフレームヘッダをまずスタックに積んで、その上にデータが来ていた。

        :          :
        +----------+
        | arg[N-1] |   |
        :    :     :   |  frame data
        |  arg[1]  |   |
        |..arg[0]..|   |
        |  size=N  |   -  frame size
        |   info   |   -  debug info
  envp->|    up    |   -  static link
        +----------+
        :          :

これを、データの後にフレームヘッダ (ヘッダじゃないけど) を積むように変更した。

        :          :
        +----------+
        |  size=N  |   -  frame size
        |   info   |   -  debug info
  envp->|....up....|   -  static link
        | arg[N-1] |   |
        :    :     :   |
        |  arg[1]  |   |  frame data
        |  arg[0]  |   |
        +----------+
        :          :

この方式の直接的なメリットは、継続がヒープに移される際の転送量が減ることくらいである (継続がセーブされる際には、「作りかけの引数フレーム」も一緒にコピーされる。後者の方式では作りかけの引数フレームはヘッダを含まないのでそのぶん小さい)。ただ、継続がヒープに移されるのはcall/ccを呼んだ時かスタックがオーバーフローした時くらいなので、あまり有難みはない。

しかし、後者の方式にしておくと、下に挙げるさらなる最適化が可能になるのだ。

SUBR呼び出しの際の引数フレームヘッダの省略

Cで定義された手続き(subr)をSchemeから呼び出す際には、スタックに積まれた引数の配列へのポインタが直接Cの関数に渡され、引数フレームヘッダの情報は使われない。したがって引数フレームヘッダを積む必要がない。

呼ばれる手続きがsubrかどうかは呼ぶ直前までわからないので、以前のフレーム構造では必ずフレームヘッダを積む必要があった。新しいフレーム構造ではフレームヘッダを積むのは呼び出し直前なので、subrの場合はヘッダ積みを省略できる。

特に、引数を取らないsubrを呼ぶ際にはスタック操作が全く生じない。

空の環境フレームの省略

引数を取らないScheme手続きの引数フレームは情報を持たないから、省略したい。しかし、以前のフレーム構造だと呼ばれる手続きが本当に引数を取らないのか、0個以上の引数を取るのか直前までわからなかったため、やはりフレームヘッダを積む必要があった。

これも新しい構造では呼び出し直前に判断してフレームの作成を避けることができる。

ここまでの結果

  プログラム           0.6.2     新バージョン 
  --------------------------------------------
  N queen (8x8)         2.61        2.49
  morph (形態素解析)    2.40        1.47
  compplot (複素演算)  93.6        83.6

インストラクションのコンバイン

何か処理をしてPUSH、というパターンは非常に多く出てくる。良く出てくるパターンに関しては、処理のインストラクション自体に PUSHの機能も持たせた複合インストラクションを作ったら良いだろう。

というわけで、LREFx, CONS, CAR, CDRに対してLREFx-PUSH, CONS-PUSH, CAR-PUSH, CDR-PUSHを追加。また、小さなimmediate integer constantをロードしてすぐPUSH、というのも多いので、 constantをインストラクションに取り込んだPUSHIというのも追加。ついでにPUSHNILも。

ベンチマーク。上の結果からさらに5〜10%のスピードアップ。

どんどんVMの方向がCISC的になっているが、バイトコードと違ってインストラクション空間も広いし、VMループがキャッシュに載らないほど大きくなることに気を付けていれば良いだろう。

将来の課題

trivial peephole optimizaiton。例えばLETのbindingでLSETした後、その値がレジスタに残っているのに同じ変数をLREFするようなコードが結構ある。現在のレジスタの有効値を追っていればそういうのを除けるのではないか。

closeしないclosure : 手続きの中で作成される手続きでも、外側の束縛を参照していないものに関しては、あたかもそれがトップレベルで定義されたかのようにコンパイルすることができる。するとそれは呼ばれる環境に対して不変なので、定数のclosureオブジェクトとすることができる。実現には、lambdaフォームをコンパイルする際に外側の束縛を参照したかどうかの情報を返す必要がある。

lambdaのインライン展開：ローカルでしか使われないclosureはインライン展開が可能。lambdaフォームが束縛されたローカル変数の使用を追跡する必要があるので、現在の1パスコンパイラでできるかどうか微妙。

common expression elimitaion.

constant expression folding.