Kazuki Ohta
mover****@hct*****
2005年 10月 14日 (金) 03:16:46 JST
太田です。
ぼちぼち進めていますが、書いている内に変更したい所が出てきたので、もぅ一度仕様を
投げてみます。
/*
* Object Representation Mechanism
*
* First, we assume ScmObj "S" which contains two ScmObj "X" and
* "Y" (e.g. ScmObj S { X, Y }).
*
* (0) LSB(Least Significant Bit) of "S" is called G-bit.
*
* (1) if S == "...00G", S is ConsCell. G-bit of S->X is used as
* marking bit of GC and G-bit of S-Y is always 0 for sweeping
* phase.
*
* (2) if S == "...01G", S is imeediate value. Imeediate value is
* separated into these types by the value of least 1 or 2 or 5
* bits of ((unsigned int S) >> 3).
*
* S Type
* ......1|01G : Char
* ------------------------------
* .....10|01G : Integer
* ------------------------------
* .000000|01G : #f
* .000100|01G : #t
* .001000|01G : ()
* .001100|01G : EOF
* .010000|01G : Quote
* .010100|01G : Quasiquote
* .011000|01G : Unquote
* .011100|01G : UnquoteSplicing
* .100000|01G : Unbound
* .100100|01G : Undef
*
* (3) if S == "...10G", S is Closure. G-bit of S->X is used as
* marking bit of GC and G-bit of S-Y is always 0 for sweeping
* phase.
*
* (4) if S == "...11G", S is other types. Type is separated by the
* value of least 3 or 5 bits of S->Y. Anyway, G-bit of S-Y is
* always 1 for sweeping phase.
*
* S->Y Type
* .....01|1 : Symbol
* .....11|1 : Continuation
* ------------------------------
* ...0000|1 : String
* ...0010|1 : Func
* ...0100|1 : Vector
* ...0110|1 : Port
* ...1000|1 : Values
* ...1010|1 : FreeCell
* ...1100|1 : C Pointer
* ...1110|1 : C Function Pointer
*/
[ 変更点その1 ]
まず、即値(immediate value)の部分です。char型はポインタを一つ持っているだけですが、
アラインメントの関係上(mallocは8byteにアラインメントされたメモリアドレスを返す)ので、下
位4ビットを占有出来ません。そこでCharだけを特別扱いしています。
また、なるべくintegerの取れるビット数を増やしたいと思い、Integerも特別扱いしています。
[ 変更点その2 ]
次にその他(other types)の部分です。Symbol, Continuationは共にポインタを2つ抱えてい
る為、これもまたアラインメントの関係から特別視しています。
String->len, Vector->len, Port->type等はint型なので、S-Yに無理矢理押し込めようと
思っています。
FreeCellは廃止ですかね。
こんな感じですが、もっとこうした方が良いとか有りますでしょうか？
> 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*****
-------------------------------------------------