Skip to content
2008/11/24 / highmt

部分継続を書いてみる(1)

別の言語の実装手段としてCを使用している場合はともかく、普通のCのコードから(ある程度の制限がなるにしても)利用可能な形で継続を実装しようとすると、制約が厳しい。
普通のCでは、ポインタと値をその値から区別することはできない。
だから、ある時点のスタックを保存しておいても、それを復元するには、保存時のアドレスに復元しないといけないことになる。
つまり、スタックのコピーはほとんど避けられない。
ヒープ上に領域を取っておいて、そこをスタック領域として使用すればコピーを避けることはできそうに見えるが、継続を保存した後にそこに戻ってきて、その後スタックが変更された後にまたそこに戻ってくるには、やはりコピーせざるを得ない。また、スタックがどこまで伸びるかわからないから、メモリの効率は悪くなる。
スタックの深さによっては、保存した継続を頻繁に起動するようなことをすると、割と大きなコストになってくることが予想される。うまくスタックの変更具合を追跡するなどして、変更のなかった部分のコピーを避けるなどして凌ぐしかない。
継続は便利な道具だけれども、カリカリに速度が必要な場合には、もっと書くのに時間のかかるけど別のやり方で実装しようね、という感じで、現実に使う場合は使いわけが必要になってくるのだろう、多分。

なにはともあれ、ともかく実装はしてみないと、ということで書いてみた。

以下、メモ。

  • 前提として前に実装したGC(に手を加えたもの)を使う。GCがなくてもがんばればメモリを追跡することはできそうなのだけれども、その場合、ユーザー側が継続を保存するので、ユーザーがその継続の寿命を操作しないといけない。あと、せっかくなのでGCのテストも兼ねて。
  • せっかくなので、フル継続よりも使い勝手のよい部分継続を実装してみる。フル継続があれば部分継続は実装できるのでフル継続のほうがよりプリミティブなのだが、継続ライブラリは既に割とありそうなので。あと、フル継続にするにはスタックボトムを知る必要があるような気がして、そうするとGCのスタック管理と重なることになるのだけれども、その部分のうまい繋ぎ方が思いつかなかった。部分継続で継続が代用できるか、というと、イテレータ的な使い方、マルチプロセス的な使い方はできそうだが、脱出に使う場合は、shiftで直近のresetまで脱出、というぐらいしかできない(部分継続の呼び出しでは呼び出し元に戻ってきてしまう。) 名前つきresetみたいな拡張はできるのかも。
  • スタックコピーする。継続を復元する先のスタックは、1本だけつくる。最初はresetごと(内部的なresetを含む)にスタックを別に立てていたのだけれど、バグをいろいろ直しているうちに、どうやってもスタックコピーが避けられないことに気づき、結局1本だけになった。これなら、ガードページを使用して必要に応じてスタック領域を増やすことができるし、スタックオーバーフローも検出できる(まだ実装していないけれど。)
  • スタックの操作はえらい苦労した。GCの実装のときよりも時間がかかった。スタック領域サイズが小さすぎてそもそもスタックオーバーフローしていてヒープが壊れていたとか、スタックのコピーが考慮不足だったとか、保存された継続を呼びだしたとき既に古くなったスタックを変更してしまって、現在時点でのスタックフレームを壊してしまったとか。
  • もとにしたのはKahuaのpartcont.scm。そのもとの論文は読んでない。この動作を理解するのも時間がかかったけれども、 (reset(abort(…(call/cc:k(shift(abort(…(reset(abort(goto:k)))))))))) という形に書いてみてわかった。
  • そういえばresetの中でreset呼ぶの試してない。内部実装ではresetの中でresetは何度も使っているのだが。resetした後、だいぶスタックが深くなってからresetを呼ぶと、きっと結構な量のスタックのコピーが発生することになる。
  • 速度はかってない。速くはないはず。サンプルでは、GCのテストを兼ねてGCコレクト処理を頻繁に入れているのでそちらで重くなっている(特に今の実装だと、継続の復元先用に用意したスタック領域全部をマークしにいくので。) のでGCよりは軽そう。
  • reset以降の処理は、切り替わったスタック上で動作するので、前に実装したGCではスタックのマークがうまくいかない。結局GCにそれ用のインタフェースを追加。ひとまずいろんなところでGCコレクト処理を呼んでみたけれども落ちてないから多分うまくいっている。

——–
2009/01/12 カテゴリ変更

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