Gauche:VMの最適化:optional引数

Gauche:VMの最適化:optional引数

2009/02/18 23:54:10 PST: Schemeの仕様では、省略可能引数はリストにまとめて渡すことになっている。 これは仕様としてはシンプルで綺麗なのだけれど、欠点もある。「残りの全ての引数(rest引数)」 が欲しい場合でない限り、callee側ではリストを直ちにアンパックして必要な引数を 取り出すので、このリストは作るだけ無駄なのだ (しかもScheme仕様ではrest引数は 安全に変更可能でなければならないので、apply経由でもともと引数リストが渡された 場合でも新しいリストを作り直さないとならない)。これは、特に性能が重要なinner loopで 省略可能引数を使うことの足枷になっていた。

Gauche:VMの最適化:Flonumの扱いで述べたfast flonum extention (ffx)が入っていると さらに問題は大きくなる。ffxでは、VMスタックにflonumを置くのはほとんどノーコスト だが、リストにパックする時点でヒープに移さなければならないのでffxのメリットが 享受できない。

そこで、段階的になるべく一時リストの生成を避ける仕組みを入れて行く。

0.8.14現在のプロトコル

0.8.14現在のプロトコルは次のとおり。

手続きfooがrequired=2, optional=1の場合:

(foo 'a 'b) と呼んだ場合:

     SP>|         |       NARGS=3
        |   ()    |
        |   b     |
   ARGP>|   a     |

(foo 'a 'b 'c) と呼んだ場合:

     SP>|         |       NARGS=3
        |   (c)   |
        |   b     |
   ARGP>|   a     |

(foo 'a 'b 'c 'd 'e) と呼んだ場合:

     SP>|         |       NARGS=3
        | (c d e) |
        |   b     |
   ARGP>|   a     |

いずれもNARGS = required+1 で変わらず。最後の引数は常にリスト。

optional引数をスタックに

ここで、fooは実は3個のoptional引数を取るものだとしよう。 (どうやってそれを知るかは今は考えない。) Common Lisp風に書けば

  (defun foo (a b &optional c  d e) ...)

ということだ。この場合、受け取る側はc,d,eをリストでもらってもすぐに分解しちゃうので、 それなら最初から別々にスタックに積んでもらった方がいい。

そこで、ScmProcedure->optionalの意味を拡張して、optional=Mの場合、

ということにする。fooの場合ならM=4だ。 (M=3にしてrest引数の有無を別フラグで持ってもいいのだが、既にcaller側では M=0とそうでない場合との場合分けがあり、さらに場合分けを増やすのは 複雑になるだけなので、caller側ではM>0の場合は常にスタックの最後にリストを 積むことで統一する。rest引数を持たないfooに過剰な引数が与えられた場合の チェックはcallee側で行う。過剰な引数が与えられてエラーになるケースが スピードのクリティカルパスにあるとは考えにくいので、その場合のオーバヘッドは 問題にならない。)

(foo 'a 'b) と呼んだ場合:

     SP>|         |       NARGS=3
        |   ()    |
        |   b     |
   ARGP>|   a     |

(foo 'a 'b 'c) と呼んだ場合:

     SP>|         |       NARGS=4
        |   ()    |
        |   c     |
        |   b     |
   ARGP>|   a     |

(foo 'a 'b 'c 'd 'e) と呼んだ場合:

     SP>|         |       NARGS=6
        |   ()    |
        |   e     |
        |   d     |
        |   c     |
        |   b     |
   ARGP>|   a     |

(foo 'a 'b 'c 'd 'e 'f) と呼んだ場合 (callee側でエラー):

     SP>|         |       NARGS=6
        |  (f)    |
        |   e     |
        |   d     |
        |   c     |
        |   b     |
   ARGP>|   a     |

NARGSは required+1からrequired+M までの間の値を取る。

なおrest引数を取るケース、Common Lispで言えば

  (defun foo (a b &optional c d e &rest f) ...)

の場合の引数の積み方も同じ。optionalの値も4のまま。

optional引数の数をどうやって出すか

Common Lispと違って、 Schemeの手続き定義構文ではlambdaリストそのものからは関数がrest引数を取るか どうかしかわからない。しかし…

最後のやつはソース解析しないとならないので後回しにするとしても、 最初のやつはすぐにでも実装できて効果があるだろう。

ここまでのベンチ

subrの:optionalについて、上記の最適化を行った。マイクロベンチで0.8.14と比較。

コード:

(use srfi-27)

(define (main args)
  (dotimes [i 10000000]
    (clamp (random-real) (random-real) (random-real)))
  0)

結果:

0.8.14 最適化
6.42s 5.69s

rest引数もスタックに?

optional引数を取った後に残るrest引数については意味的にはリストにするしかないのだが、 ここでもリスト作成を避けたい場合がある。例えば不定長の要素を取るコンストラクタだ。 具体的には次のようなもの:

  (vector 1 2 3)
  (f32vector 1.0 2.0 3.0)

こういったものの場合、渡されたリストは各要素がvectorやf32vectorを作るのに 使われるだけで、リストそのものはすぐに捨てられる。f32vectorやf64vectorについては、 せっかくrefやset!ではffxが効くのにコンストラクタではリスト渡しになるせいで flonumのアロケーションが入っちゃうのも惜しい。

このうちvectorについてはVMが直接サポートしているのでリストを作らずに 引数をスタックに積む→VECインストラクション実行、となるのだけれど、 この手の全てのコンストラクタに対応するVMインストラクションを作るのは スマートじゃないし、拡張性もない。

こういうのは何らかの方法で、プロトコル上は optional引数10個、あとはrestで (つまりM=11)としておいて、callee側で「最初の10個まではスタック、 残りはリスト」と取り出すのが良かろう。callee側の処理が面倒だが そんなにたくさんのケースでこういう処理が必要なわけじゃないし、 当面の懸念であるf32vector, f64vectorなどについてはgenstubをごにょごにょ すれば煩雑な処理の部分は自動生成できるんじゃないか、と目論む。

なお、「すべてスタックに積んでしまう」というのは避ける。スタックの 大きさに限りがあるので。

結局、define-cprocに新しい引数形式を追加してみた。 指定個数までのoptional引数をScmObjの配列で、それ以降をリストとしてrest引数で受け取れる。 詳しくはlib/gauche/cgen/stub.scmのコメント参照。

More ...