Mosh のコンパイラ高速化で悩み中

問題点と目標

psyntax.pp の実行に 3 sec かかるが 500msec にしたい。

プロファイラ結果

実行時間の 27% を %set-union の実行が占めておりこれを改善すれば速度向上が見込める

%set-unionとは何か？

2つのリストを引数にとり和集合を返す手続き。
結果として返るリストは新しくアロケートされたものである。（後述の使われ方ではリストが新しくアロケートされることが必要とされている）

%set-union はどこで使われているか？

pass3/$lambda や pass3/$let で使われている。
pass3 中は free variable の候補となる変数をリストとして保持し、引数で各処理に渡している。
「free variable の候補となる変数をリスト」は、find-free という手続きで使われる。この手続きはある lambda 式の中にある free variable を探し出すという手続きである。
「free variable の候補となる変数のリスト」は lambda や let の中に入るたびに更新されて増えていく。lambda の仮引数は、lambdaの body の中にある lambda にとって free variable だからである。

速くする方法候補

思いつくままに列挙する。すでに実施済みのものもある。

%set-union を C++ で書き直す（実施済み）
%set-union のアルゴリズムを memq を使用するものからハッシュを使うものに変更（実施済み）
%set-union の呼ばれる回数を減らす方法を考える
%set-union で「free variable の候補となる変数のリスト」を作らなくても良いような free variable の管理方法を考える
- free variables の lookup を独立して行わず parse のときにやってしまうとか。（最適化のあとじゃないとだめじゃん）

うーん。どうしよう。良い方法思いつかない。コンパイラのソース。
しばらく寝かすかな。