インライン展開その3 - Scheme VM を書く

インライン展開をしても思ったよりも速くない原因を考える。

事実

まずは事実から。
gosh -ptime で実行すると最適化前と比べて

VM の実行命令数が1.5倍
スタック操作の index/push が2倍

と遅くなっている。

考察

最適化の過程でコードサイズが増加するのだけどこれの影響が大きそう。
具体的には

ソースコード
↓
α変換
↓
A正規化 ← (1)コードサイズ増加
↓
β簡約
↓
不要定義削除 ← コードサイズが微妙に減少
↓
インライン展開 ← (2)コードサイズ増加
↓
コンパイル
↓
VMで実行

と2箇所でコードサイズの増加がおきる。
それぞれのコードサイズ増加が今のコンパイラ/VM に与えるインパクトを考えてみよう。

(1)A正規化時の増加
計算の途中経過を変数に保持するような変換を行うので、ブロック(let1) のコードが大量に増える。
その結果

サイズ増加によるコンパイル速度が遅くなる
実行命令数が増え VM が遅くなる

となってしまう。

ただし命令実行数が増えるのは現在の実装が、中間コードであるはずのものを何も考えずコンパイル/実行しているからであることに注意しないといけない。
let1 ブロックを全てスタックに変数を push する形でコンパイルするようになってしまっている。このうち一部の安全な（？）let1 の途中経過をレジスタに積むようにコンパイラを変更すれば断然速くなるのではなかろうか。

(2)インライン展開時のコードサイズ増加
あまりに大きな手続きを、何か所にも展開するとコードが大きくなる。ただし大きくなっても理論上は VM での命令数はほとんど変わらないはず。
コンパイル時間を稼ぐために、インライン展開をした手続きの定義を削除したいのだけ load とかがあるからうまく削除できるか微妙。

結論

中間表現として使っているA正規形の let1 をレジスタをうまく使い効率的にコンパイルするべし。
正解が分からないのでとりあえずやってみよう。

追記

う。しかしスタックマシンなので一時変数はスタックに積むのが筋だろうか。何か見落としているかな。
レジスタ割りあて？
ところで仮想スタックマシンで仮想レジスタに変数を割り付けるメリットてあるんだろうか。うーん。まだ分からない。

追記2

だいありー
お。2003頃にささださんも悩まれていたようですね。