Gauche:util.matchのinline-let

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して、

あと、..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%強の改善になった。 これなら入れる意味がある。

More ...