Jun Inoue
jun.l****@gmail*****
2005年 9月 4日 (日) 20:53:03 JST
On Sun, 4 Sep 2005 08:34:19 +0900 Kazuki Ohta <mover****@hct*****> wrote: > ScmObjInternal *obj; > ScmObjInternal*: [ -- 29 bit -- ] [ABC] (car部) > ScmObjInternal*: [ -- 29 bit -- ] [XYZ] (cdr部) > > 王道ですが、最下位ビット(C と Z)が立っている時は即値と見なします。 > [-- 29bit --][001]や[-- 29bit --][101]等の値は全て即値と見なされます。 > 逆に、即値でない場合は次のようになります。 んー、吉田さんのとちょっと被る質問ですが、即値にも ScmObjInternal を一つ 確保してしまうんですか? 即値であることを判定するために dereference しな いといけないのでは、即値の意味が無いような。 > 後残っているのはA,B,X,Yの部分です。ここにgcのデータ(marked or unmarked) > とScmObjの型情報(Cons? String? Port?)が入ります。まずAにgc用のデータを > 割り当てたとして、残りB,X,Yの部分に型情報を詰め込む必要が有ります。 > > しかし現在 ScmObjType は15種類有って、少なくとも4bit必要です。どう考えて > も足りませんね...これを解決する為に僕が思い付いたのは、次の2つの方法です。 [...] 私もまた違った方向で考えていたので、投稿してみます。参考にしてください。 ツッコミ or 却下お願いします。主に guile のパクリです。でも guile の構造 はあんまり理解してません。でもパクったんです。そういうことなんです。 基本的な考え方は、ポインタの指す cell にある 2 ワードの内、一方はポイン タでない事が多いので、そういうときは比較的多めのビットを使える。よって使 う。ということです。 ScmObj 型のデータ S があったとする。それの指す構造体の中身を struct { X, Y }; とおく。 (注: ... 001 とかいうのは、下 3bit が 001 である任意のデータをあらわす) (0) S の LSB は gc に使う。以下、このビットは g。もうちょっと上のビット にした方がいいかも…詰めきれてない。 (1) S = ... 00g なら S は cons。S->X の g ビットが gc_mark ビットで、 S->Y は必ず 0 (重要) (2) S = ... 01g なら S は即値。(unsigned)S >> 3 として得られる値の下位数 bit で integer/char/()/#f/... を判定する。この手のオブジェクトはヒープ上 には実体を持たず、ポインタそのものが実体。よって gc 情報無し。 (3) S = ... 10g なら S は closure。S->X の g ビットが GC mark bit で、 S->Y は必ず 0 (重要) (4) S = ... 11g なら S は その他。このとき、S->Y は ScmObj 型のポインタ ではないので、ルール (1)〜(3) に縛られないことに注意する。ただし S->Y の g ビットは必ず 1。で、S->Y = ... 0011 なら vector, S->Y = ... 0111 な ら string, 等々。freecell 型も用意するならここ。 S->Y の g ビットが 0 だの 1 だの言ってるのは、sweep 時に見分ける手がかり として必要だから。 この方法なら、小さいオブジェクト、特に integer と char は cell を消費し ません。また、GC_MARK() を "g=0" という操作で定義すると、cons はビット 演算を施すことなく dereference できます。(型チェックしない場合) GC も mark_table を用意しなくて良いので、shiro さんが指摘されているよう な、ヒープの連続性の心配もありません。メリットはそれぐらいです。パフォー マンスに関する事柄を並べてありますが、現実にこれらがどれぐらい速く、メモ リを効率的に使用するかはわかりません。 見ての通り、拡張性は既にいっぱいいっぱいです。X も Y もポインタでなくて はならないような型はもう追加できません。でも多分 cons/closure だけじゃな いのかなぁと…祈ってますw。どうしても必要なら closure を (4) に押し込め られますが、それをすると今の状態と本質的に同じになりますしねぇ。 それから、vector や string の長さがやや制限されます。(4) に当てはまる型 は今のところ symbol, string, func, vector, port, continuation, cpointer, cfuncpointer の丁度 8 つなので、g ビットと合わせて S->Y は型情報に 4 bit 費すことになります。UTF-8 char を、何の変換もなしに格納したいのであ れば char 型も (4) に入ってくるので 5 bit になります。ですから最大長は 32bit 環境では最大 2**(32-4 or 5) = 256 or 128 M となります。型部分を可 変長にすることもできますが、勿論パフォーマンスに響きます。 最後に incremental GC について。Incremental にするなら、破壊的代入の度 に g ビットが上書きされないような write barrier を設けることになります。 って、SETCDR とか使ってないのは私の quasiquote コードだけじゃないか(吐血) どんなもんでしょ。っていうかこんな説明でわかってもらえるでしょうか。 -- Jun Inoue jun.l****@gmail*****
