プロファイル - Scheme VM を書く

Bignum の実装が一段落した。
やっとプロファイラを動かしてコンパイラの実効速度が著しく遅い件を調べることができる。

事実

Wiki のコンパイルに 0.4 sec。
Wiki の実行に 0.6 sec。
Wiki の実行の 2/3 はコンパイル。
VM on Gauche が VM on C++ よりも速い場合が多い。
- VM on Gauche でのコンパイルは Gauche を利用しているので、Gaucheの速さに助けられているのだろう。
- その証拠にコンパイル済みのコードの実行は VM on C++ が5倍ほど速い

方針1

コンパイル時に Scheme / C++ 上でプロファイルをとり傾向をつかむ

Wikiのコンパイルのプロファイル

Scheme

;; 総実行時間順(名前 call回数 実行時間usec sec/call)
(compile-code 1910 7107648 3.72128167539267)
(compile-lambda 142 2868872 20.203323943661974)
(find-sets 5825 2507858 0.43053356223175965)
(expand-code 2533 1245664 0.49177418081326485)
(main 1 1201281 1201.281)
(compile-file 1 1201237 1201.237)
(compile 65 1072210 16.495538461538462)
(set-union 14834 519841 0.03504388566805987)
(find-free 142 481790 3.392887323943662)

;; sec/call 順
(main 1 1201281 1201.281)
(compile-file 1 1201237 1201.237)
(compile-lambda 142 2868872 20.203323943661974)
(compile 65 1072210 16.495538461538462)
(compile-code 1910 7107648 3.72128167539267)
(find-free 142 481790 3.392887323943662)
(named-let->lambda 7 22479 3.2112857142857143)
(make-const-table 1 936 0.936)
(let->lambda 47 25264 0.537531914893617)
(expand-code 2533 1245664 0.49177418081326485)

C++

 time   seconds   seconds    calls  ms/call  ms/call  name    
 55.77      0.29     0.29      117     2.48     4.37  scheme::VM::run(scheme::ObjectRecord*, scheme::ObjectRecord*, scheme::O
bjectRecord*, scheme::ObjectRecord*, bool)
 13.46      0.36     0.07   549790     0.00     0.00  util::UCS4HashMap<scheme::ObjectRecord*>::hash(unsigned int const*)
  9.62      0.41     0.05   272988     0.00     0.00  util::BinaryTree<scheme::ObjectRecord*>::contains(util::BinaryTree<sche
me::ObjectRecord*>::Node const*, int) const
  7.69      0.45     0.04  3872883     0.00     0.00  scheme::VM::push(scheme::ObjectRecord*, scheme::ObjectRecord*)
  1.92      0.46     0.01  2179414     0.00     0.00  util::BinaryTree<scheme::ObjectRecord*>::get(util::BinaryTree<scheme::O
bjectRecord*>::Node const*, int) const
  1.92      0.47     0.01   280659     0.00     0.00  scheme::Arithmetic::fitsInt(int)
  1.92      0.48     0.01   272988     0.00     0.00  util::UCS4HashMap<scheme::ObjectRecord*>::containsKey(unsigned int cons
t*)

プロファイル考察

Scheme 側では find-free が遅いのが際立つのと find-sets か。
C++ は目立って気になるところはない。

find-free/find-sets に共通しているのは set-member?（結果的にfind）の呼出しが多いこと。
あとは lambda が多いことか。

次の1手

ありきたりな結論だが基本部品の高速化が良さそう。

Scheme 側ではコンパイル時の lambda式の最適化
C++ 側では実装面での VMループの最適化
頻出 instruction の組合せを合成 instructionに。

まずは心当たりがあるVMループの最適化をやろう。