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

scheme mosh

Mosh のコンパイラ高速化で悩み中の続き。
id:koguroさんにアドバイスいただき一晩考えた末、%set-union の呼び出し回数が減らせないかという視点でコードをもう一度読み込むことにした。
いくつか改善出来たのでメモ。

%set-union の呼び出し回数を半減

%set-union の一部は append2 の呼び出しで全く同じ効果が得られていたので改善。これは id:koguro さんのアドバイスによるものです。ありがとうございます。

# 変更前
time%        msec      calls   name
19%          430       8694   %set-union
3%           70       17783   append2

# 変更後
        10          210       4347   %set-union
 8          170      22130   append2

無駄な append2 を減らす

  10          210       4347   %set-union
   3           60      22279   append2

set-union, set-intersect を廃止

慎重に慎重にコードを読み進め不要処理を削り set-union が論理的に必要ない構造に書き換えた。
書き換える部分はごく小さな範囲だが、設計というか調査に時間をかけた。
append2 の呼び出しコストが大きくなった。

  16          280      22279   append2

sets

set! される lvar のリスト sets は最終的に pass3/$local-ref で INDIRECT を発行するかどうかにだけ使われるので hash-table でも良い。
hash-table であれば

  • 長いリストを append していくよりは要素の追加が速い
    • これは注意が必要、hash-table はその都度コピー渡しする必要があるので実際に速いかどうかは実装次第。
  • memq でチェックするより hash-table-ref する方が圧倒的に速い。

のでやる価値があると思う。

いまここを実装しています。

今日終わった分の成果のグラフ

縦軸が実行時間、横軸は改善の様子。赤い線は目標値。
青い円で囲んでいるのが今日の改善。
少しずつ目標値に近づいている