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現在のプロトコルは次のとおり。

手続きScmProcedureは必須引数の数requiredと省略引数の数optionalを持つ。
固定長引数手続きはoptional=0、可変長引数手続きはoptional=1。
callerは、スタックにrequiredの分だけ引数を積み、さらに残りの引数をリストにして (残りが無ければ空リストを)積んでcalleeを呼ぶ。

手続き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の場合、

余分な引数のうち最初のM-1個まではスタックに直接積み、
最後にさらに余ってる引数をリストにして積む (余ってなければ空リストを積む)

ということにする。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引数がdefine-cprocで明示されてるのでわかる。
case-lambdaを使った場合もわかる。
(define (foo a b . rest) (let-optionals* rest ((...)) ...)) のように、直ちにlet-optionals*でoptional引数を分解し、かつrestで渡された引数を他で使っていなければoptional引数の個数がわかる。

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

ここまでのベンチ

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のコメント参照。