Gauche:util.matchのinline-let
Shiro(2011/03/06 01:57:06 PST): コンパイラの最適化をやっていたら、util.matchの inline-let中のloopがプロファイラに上がってきたのでちょっと調べたメモ。
inline-letの役割
matchの展開中にletによる束縛が導入されることがある。またその束縛がlambda式である ことが多い。こんな形:
(let ((x (lambda (..) ...)) (y (lambda (..) ...)) ...) ...)
そんで、ここで導入されるlambda式の多くはごく小さい。
これをナイーブにコンパイルすると、ごく単純な式のためにクロージャが作られまくるので 性能上あまりうれしくない。そこで中身まで全部展開した後で、作ったletフォームをwalkして、
- 導入したローカル束縛が一度も使われていなかったら削除
- 一度しか使われていない、あるいは複数回使われていても値であるlambda式がごく 単純な場合は、束縛を削除し、ローカル変数が使われている場所に直接lambda式を埋め込む。 これによって、((lambda (..) ...) ...) の形の式がたくさんできるが、 これはよっぽどナイーブな処理系でも最適化される公算が大きい。
あと、..k という回数指定のマッチを実現するために リストの長さを計る操作が必要なんだけど、それが必要な可能性が出てきたところで 次のような束縛を入れている (実際はlength>=のところはgensymしたシンボルを使用)。
(let ((length>= (lambda (n) (lambda (l) (>= (length l) n)))) ...) ...)
カリー化されているのは、おそらく埋め込まれた時にインライン展開をやりやすくするため。 また、..kの形を使っていなければinline-letによってこの束縛自体は除かれる。
なので、inline-let自体はmatchの出力を単純化するのにかなり役立ってるはず。
Gaucheで要る?
でも、Gaucheのコンパイラはinline-letがやっているような最適化は
自前で持っているので、マクロ展開時に頑張ってもらわなくても多分大丈夫。
使われない束縛は消されるし、 (let ((x (lambda (..) ...))) ... (x ..) ...)
の形の式ならlambdaはインライン展開される。
inline-letを行わないとpass1が処理すべきフォームがでかくなるので そこでオーバヘッドは生じるけれど、 inline-letは何度もフォームをwalkしないとならないから、それがコンパイラ側で 既にやっている分でカバーできるなら有利。
あと、length>= についても、define-inline使えばグローバルに定義しておいても インライン展開できるので、ローカルに束縛する必要は多分無い。
やってみた
とりあえずinline-letをidentityにしてざっと試したところ、 match自体の展開形はかなり違うけれども、コンパイル結果は同じになる。 従って展開後の実行時のペナルティは無い。
展開時の性能だけど、もともといろんなプログラムをがーっとloadするだけの ベンチマークでinline-letが3%弱上がってたのがなくなった。ただ、pass1自体が 1%ちょい増えて、トータルでは1%ちょっとの削減。 微妙な数字ではある。
いや、length>= をグローバルな定義にしたら2%強の改善になった。 これなら入れる意味がある。