関数型言語の勉強にSICPを読もう - (66) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう15
いろいろな構文が動いたので悪ノリしてパフォーマンスを測定してみたら恐ろしい罠が!
計測対象
(begin
(define count (lambda (x)
(if (= 5000 x)
x
(begin
(count (+ x 1))))))
(display (count 0)))条件分岐・変数の参照・再帰・値の比較などなどの要素を盛り込んであります。
結果
Gaucheでは一瞬で実行が終わるのに、数十秒かかる。。。
どうして遅いのか?
ループの回数を増やすと極端に遅くなるということから、変数のlookupのあたりが怪しいなぁとあたりをつけます。
で、gprof を使って見たところ。
% cumulative self self total time seconds seconds calls us/call us/call name 49.79 4.65 4.65 37537506 0.12 0.21 monash::Frame::lookup(monash::Variable*)
やはりlookupに時間がかかっていますね。ん？callの回数が37,537,506 回！
今のlookupは FrameのリストからFrameを取り出してhashmapで変数を名前からlookupします。
そのFrameに変数が見つからなければ、次のFrameに対して同じことをやります。
例えば + をlookupした場合、最上位のFrameに束縛されているので、Frameのリストを最後までたどってやっと変数が見つかります。
で、問題は5000回目のループの時点でFrameのリストの要素が5000個あって、更に最悪の場合その全ての要素に対してlookupするという状況が発生するということです。
再帰呼び出しで、再帰の回数分Frameができてしまうのがしょうがないならば、変数のlookup処理を工夫すれば良さそうです。
例えば、グローバルなhashmapにlookupテーブルを作っておけばかなり速くなると思う。
再帰の回数分Frameができるってのは結局 inlineで展開しているようなもので何かおかしい気がするけどもう少し考えてみます。
竹内関数
コメントにて竹内関数というものを教えていただいた。
どうもこの関数はベンチマーク関数として有名らしい。
(begin
(define tak (lambda (x y z)
(cond
((> x y) (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))) (#t y)))) (tak 12 6 0))一瞬で終わった。これは速かった。
ん？でも tak の戻り値がGacheの結果と違うなぁ。
計算機プログラムの構造と解釈
posted with amazlet on 06.05.31
