Shiro Kawai
shiro****@lava*****
2005年 9月 4日 (日) 10:26:39 JST
From: Kazuki Ohta <mover****@hct*****> Subject: [Anthy-dev 2353] ScmObjInternalのCompacting Date: Sun, 4 Sep 2005 08:34:19 +0900 > 1. mark_tableの作成 > gcデータ(mark or unmarked)用に独自のテーブルを持ちます。1ビットの情報しか > いらないので、int mark_table[HEAP_SIZE / 32]とする事でスペースを削減でき > ます。mark_tableのインデックスは対応するheap上のScmObjInternalのインデック > スと対応します。 Boehm GCもこの方法を使っていますね。SigSchemeが常に連続した ヒープ領域しか使わないのなら簡単で良い方法だと思います。 実行中にヒープの拡張などがあって不連続な領域を取り得る場合は 面倒になります。領域を常にページ境界に合わせられるなら 上位ビットでインデックスされるテーブルでヒープかどうかを 判断できますが(*1)、そうでないとビットマップへのマッピングに コストがかかりすぎるのであまり良くないです。 (*1)64bitアーキテクチャの場合は単純なテーブルでは大きくなり すぎるのでハッシュテーブルにする等の工夫が必要。 > 2. 型毎にヒープを分ける > すべてのヒープの開始アドレスと終端アドレスをチェックして、ここのヒープに含まれて > いるから、このデータ型だという様に判断する。 32bit時代が来る前(VAX以前?)は、ページ毎に格納する型を分ける のが主流でBIBOPと呼ばれていました。(32bitになって全メモリ空間を BIBOPで使いきるのが大変になった時に、オブジェクトの下位ビットを タグに使うことを発案したのがJonathan Reesだったかな。) ヒープ領域が連続していて、各型の領域をページ境界に揃えられるなら、 型の判定は上位ビットをシフトしてテーブルを引けば良いのでO(1)で いけます。もしこの条件が揃うなら、gcビットも別テーブルで持てるので 使える案だと思います。 ヒープ領域が不連続の場合は1.の場合と同様、難しくなります。 --shiro
