Kazuki Ohta
mover****@hct*****
2005年 10月 7日 (金) 01:35:23 JST
太田です。sorry for late reply:-P 2週間ほど考えてみたのですが、確かに僕の方式だと型を判別する為にdereference が必要なので、糞ですね。Guileのパクリもなんか嫌だなーという事で色々考えてみたん ですが、Consがビット演算無しでdereferenceできるという発想に取り付かれそれ以上 良いアイデアが浮かびませんでした。という訳で井上さんの提唱された方法で行く事に します。 # 決断遅すぎ > 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 コードだけじゃないか(吐血) > > どんなもんでしょ。っていうかこんな説明でわかってもらえるでしょうか。 -- ------------------------------------------------- Kazuki Ohta : mover****@hct***** -------------------------------------------------
