Skip to content
2008/09/19 / highmt

スタックをヒープで差し替えてみる(1)

Schemeを勉強しはじめたころ http://www.cs.indiana.edu/~dyb/pubs.htmlThree Implementation Models for Scheme を流し読みしたときに頭に残っていたヒープベースの実行モデルを、最近ふと思いたってCで実装してみた。

  • スタックベースよりやっぱり遅い。呼び出しのオーバーヘッドが支配的になってくるとスタックベースより100倍ぐらい遅い。もっと軽いアロケータでやるべきなんだろう。
  • 最大スタックサイズを決めないといけないのが面倒くさい。
  • 再帰呼び出しでのスタックオーバーフローはまず起きなくなる。
  • でもCで再帰呼び出しって。Cが必要な状況ではふつう再帰は除去する方向だと思う。
  • スタック巻き戻しとか対応してない気がする。
  • 割り当てたスタックの回収方法(いまは単純にfree)に手を加えると、継続っぽいものができるようになる。
  • 再帰方法を自分で選べば末尾再帰になる。でも選ぶくらいならgotoするし。

ちなみに、

  • スタックベースで継続を支援するライブラリ:libcont。作者は有名な人。
  • ruby(<=1.8)のスレッドもlibcontみたいな実装になっている。1.9以降は知らない。

——–
2008/11/24 リンク先を変更。

2009/01/12 カテゴリ変更

広告
%d人のブロガーが「いいね」をつけました。