Gaucheと深い再帰
これは末尾再帰で木を走査で色々調べたときの副産物だけど、Gauche ユーザリファレンスの3.6.2 パフォーマンスに関するヒント曰く、
深い再帰: Gauche の仮想機械(VM)は効率的なローカルフレーム割り当てのためにスタックを使っています。再帰が深くなって(プログラムにもよりますが、大体数百回から千回) スタックがオーバーフローするとスタックの内容をヒープに退避するというオーバーヘッドが生じます。 あるデータ量を越えたところでパフォーマンスの低下が見られたならば、深い再帰がないか調べてみて下さい。
とのこと。マジですかと思って、件のエントリで使った非末尾再帰のcopy-treeに10^6の要素を持つリストを渡してみたら、スタックがあふれることなく普通に動いた。これは便利。
0 件のコメント:
コメントを投稿