Gauche:VMの最適化:For 0.6.3

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ループがキャッシュに 載らないほど大きくなることに気を付けていれば良いだろう。

将来の課題

More ...