加藤＠ＯＤＮです．

In article <m3ekli5qns.fsf@nospam.maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi wrote:
>Hideki Kato <katoh@pop12.odn.ne.jp> writes:
>
>> >  そうですか? 結局mutator/collectorの速度比は調整するしかないじゃ
>> >ないですか。でもですね。定常状態のデータ構造を固定した場合、「フ
>> >ルスピードでconsし続けても決してアウトにならない」値が求められる
>> >と思いませんか。
>> 
>> それは「具体的」にはどうやって求めればいいのでしょう？　まぁ，定常状
>> 態のデータ構造が固定という仮定は，ちょっくら強すぎる仮定だと思います
>> からどうでもいいんですけど．
>> ＃この求め方はもう確立されている，というのならご免なさい．
>
>「データ構造が固定」は強すぎるかも知れませんが、
>「データ量の上限が固定」だと現実的ですよね。

う，実はそれも難しいんですよね．LISP で書いたエキスパートシステムの
類で展開されるノード数の最大値なんて．．．単純に（ワーストケースを）
求めたら非現実的な値（まず間違いなく指数関数オーダー）になるだろう
し．．．とは言え，それを前提にしないことには具体的な話ができないの
も，また確か．
＃だからＣ（か FORTRAN）で作ろう，って話になってしまう．．．言語の問
＃題じゃないんだけど．．．

>で、その場合、
>「空きメモリ容量○○MB」＝ cons ××回
>「生きているデータ量△△MB」＝ マーク ★★回
>が分かるので、
>cons1回あたり★★/××個のセルをマーク
>(○○＋△△)/××バイトをスイープ
>じゃだめですか。

ふむふむ．

>実際にはこんな手順になると思います。
>
>ヒープに余裕があるうちはGCしないでおく(ヒープの空きがあるレベルより少
>なくなったらGCを始める)方が実は効率が良いのですが、そうすると、「cons1
>回あたりの仕事量」は増えてしまいます。

これは承知してます（記憶は朧ですが，当時色々検討しましたから)．

>で、あまり時間がかかると実時間制
>約が満たせなくなるので、
>
>(1) cons1回あたり(可変長の場合は、1バイトあたり)どのくらいの時間がかかっ
>    て良いかという、許容できる上限値を決める。
>(2) それを満たすように、cons1回あたりの仕事量のパラメータを調節する。
>    (これは、比例定数を実機で測っておけば済むはずです。)
>(3) その後、扱う(生きている)データ量の最大値と、実装されているメモリの
>    比率から、いつ(たとえば空き領域の残りが何%になったとき)GCを始めれ
>    ば良いかのが決まる。

残念ながら実機は固定できません．市販ソフトウェアですから，どんなハー
ド上で使われる事になるかは，売る方の与り知らぬところです．
＃起動時にベンチマークでも測るか．．．？
＃それでも他のタスクが有ったら．．．とか考えると，専用機というか，
＃ハードと組でシステムとしてしか売れなくなっちゃうわけで．．．これも
＃困る．

>実装されているメモリやCPU速度が足りないと、
>「この停止時間を満たそうとすると、ずっとGCしていても追い付かない」
>ということになります。

ですねぇ．

>たとえば、
>「実時間制約(割り付けにどのくらい時間がかかって良いか)」
>「生きているデータ量の最大値」
>「ヒープサイズ」
>をパラメタで渡すと、後はシステムが自動でチューニングしてくれる(制約を
>満たす限り、なるべくGCを止めておくよう最適化するとか、あるいは停止時間
>をなるべく均一になるよう最適化するとか)としたらどうでしょう。これなら
>acceptableでしょうか?

上にも書いたとおり二番目が難しいんでねぇ．．．量だけなら仮想記憶にす
るとか（今はメモリも安いから）目一杯実装するという手もあるんです
が．．．
＃それに，そんな事を気にしなくて済むのが LISP を使う利点の一つではな
＃かったかな，とも思ったり．
-- 
Hideki Kato <mailto:katoh@pop12.odn.ne.jp>