2012-02-29

Gaucheと深い再帰

これは末尾再帰で木を走査で色々調べたときの副産物だけど、Gauche ユーザリファレンス3.6.2 パフォーマンスに関するヒント曰く、

深い再帰: Gauche の仮想機械(VM)は効率的なローカルフレーム割り当てのためにスタックを使っています。再帰が深くなって(プログラムにもよりますが、大体数百回から千回) スタックがオーバーフローするとスタックの内容をヒープに退避するというオーバーヘッドが生じます。 あるデータ量を越えたところでパフォーマンスの低下が見られたならば、深い再帰がないか調べてみて下さい。

とのこと。マジですかと思って、件のエントリで使った非末尾再帰のcopy-treeに10^6の要素を持つリストを渡してみたら、スタックがあふれることなく普通に動いた。これは便利。

0 件のコメント: