fault on continuation (Gauche-devel-jp) - Gauche

From: Tetsuya Okada <okaya****@c-cre*****>
Subject: [Gauche-devel-jp] fault on continuation
Date: Mon, 18 Nov 2002 15:22:44 +0900

> 継続を使ってバックトラックするプログラムを書いていまして、以下のような
> ベンチマークを作ったのですが Gauche 0.6.5 が segmentation fault してい
> まいます。

確認しました。
doループがコンパイルされるあるVMインストラクションで
スタックハンドリングをしくじってしまったようです。

とりあえずの回避策としては、named letを使えば動作します。
(コンパイラの最適化をさぼっているせいで、今のところ
named letは常にdoよりも効率の悪い方法に展開されます。
あと数リリースのうちにこのへんは大幅に改善したいと考えて
いるのですが…)

> 処理系によって、得手不得手が極端に現れますね。

継続の実装は、何を重視するかでかなり違ってくるせいでしょうね。

full continuationの実装は、スタックエリアのコピーという観点
から見ると、次のように分類されます。

 (1) 継続作成時にスタックからヒープへのコピーを行い、
     継続呼び出し時にヒープからスタックへのコピーを行う

 (2) 継続作成時にスタックからヒープへのコピーを行うが、
     継続呼び出し時にはコピーを行わない

 (3) 継続作成時にはコピーを行わず、
     継続呼び出し時にコピーを行う

 (4) 継続作成時にも継続呼び出し時にもコピーは行わない

guileやSCMは(1)のタイプです。このタイプは、CとSchemeの
スタックが自由にインターリーブできるのが特徴です(Scheme
ルーチンから呼んだCルーチンからさらにSchemeルーチンを
簡単に呼べる)。したがってC APIが単純になります。また、
スタックエリアのGCを必要としません。しかしコピーの回数が
多いため、継続は非常に重くなります。
SCMよりguileがかなり重いのは何故だかわかりません。

Gaucheは(2)の方法を利用しています。(1)と同様にスタック
エリアのGCが不要で、コピーの回数が少ないのが特徴です。
しかし、呼ばれない継続でも作られる時点でコピーする必要が
あるのであまり良い方法ではないです。将来、スタックエリア
のGCを実装できたら(3)か(4)に移りたいと考えています。

(3)はChez Schemeへの実装の論文があります。Petite Chez
Schemeで使われているかどうかは知りませんが、おそらく
使われているんではないでしょうか。スタックエリアのGCと、
スタックアンダーフローを検出する一種のバリアが必要です。
継続の作成はほぼノーコストです。継続の呼び出しには若干の
オーバヘッドがあります。

(4)は実装技術的にはさらに2つに分かれます。継続を全て
ヒープアロケートする方法と、スタックフレームをポップしない
方法です。完全なcontinuation passing styleなので、
継続の作成、起動ともに理論上ノーコストでできる方法です。
しかし、継続を全てヒープアロケートするのはメモリアクセスの
ローカリティが悪く、最近のCPUでは不利になります。
Chickenは後者の方法 (ポップしないスタックフレーム)を使って
います。理屈の上ではこれが一番良い方法のはずですが、スタック
エリアのGC回数が(3)よりずっと多くなるため、総合的な性能で
比較すると微妙なところです。

--shiro