Jun Inoue
jun.l****@gmail*****
2005年 10月 14日 (金) 18:14:24 JST
私の意図が読み取りにくくて混乱されてるようなので、用語を勝手に定義してお きます。 tag 型: 各 ScmObj の下位 bit があらわすもの。cons, closure, imm, other の 4 種類がある。tag 型の情報は当然、tag に含まれます。 imm-tag 型: 即値の種類。int, char がある。const を含めるかどうかという のを審議中。imm-tag 型の情報を含んでいる bits を imm tag と呼びます。 other-tag 型: other 型の詳しい型情報。S->Y の下位に保存。 node 型: S->Y の G bit によって定まる型。G = 1 のものを uni 型、G = 0 のものを bin 型とする。uni 型はたかだが一つの ScmObj を指し、bin 型は 二つ指す。この情報を運んでる部分の名称は S->Y->G。 scm 型: Scheme level で存在する型。int, char, cons, closure, list って いうか (), boolean, symbol, string。書き忘れは無いかな? 一番重要なのがこれ。 型の所在: 「S の (scm) 型」と言うと、XXXP(S) が真になるような XXX の事 を指すものとします。例えば "S は cons" というのは CONSP(S) と同値です。 On Fri, 14 Oct 2005 10:42:35 +0900 YamaKen <yamak****@bp*****> wrote: > At Thu, 13 Oct 2005 16:59:59 -0700, > jun.l****@gmail***** wrote: > > > > On Fri, 14 Oct 2005 07:51:04 +0900 > > YamaKen <yamak****@bp*****> wrote: > > > > > S Type > > > 0000000|00G : #f (S = 0) > > > .......|00G : Cons > > > ------------------------------ > > > 0000000|01G : () (S = 0) > > > .......|01G : Closure > > > ------------------------------ > > > 0000000|10G : Unbound (S = 0) > > > .......|10G : Others > > > ------------------------------ > > > ......0|11G : Integer (imm) > > > ------------------------------ > > > ......1|11G : Char (imm) > > > ------------------------------ > > > > ここを > > .......0|11G : Integer (imm) > > ......01|11G : Const (imm) > > ......11|11G : Char (imm) > > とすれば、#f, (), unbound, #t, EOF, undef その他入れたければ 128M 種類が > > 即値に入ります。int の表現範囲も犠牲になりません。 > > charも自由度の高いエンコーディングのためになるべく広く取っておき > たいところです。それからNULL|tag形式は後述のように実行・サイズ効 > 率のためでもあるので。 24 bit じゃ不足ですか? しかも↑だと 24 どころか 27 もあるんですが…私 は 24 bit あれば十分と考えていますが、そうすると char に 27 割り当てよ うが 26 割り当てようが使いません。でも int 型は bit はあればあるほど望 ましいといえます。だから code 空間の使用率が低いと保証されている char/const 型を迫害したんですが。 > あ、ついでですがshift無しでcharacter valueを扱う場合のためにint > じゃなくてcharの方を011Gにした方がよいと思います。 > > ......0|11G : Char (imm) > ------------------------------ > ......1|11G : Integer (imm) Shift 無しで扱う?? Tag bit の操作を思い違われていませんか? (下記参照) > > > S->Y of Others > > > O Type content of O > > > ........|001 : Symbol : vcell > > > > string name でないといけません。Others の定義は S->Y が ScmObj の > > convention に縛られない、です。 > > stringの8byte alignを保証できるならそれでもいいんですが、さすが > にちょっと移植性が気になります。heapと違って割り当てサイズ小さい > し。 vcell の tag が 001 固定だと、CONSP(VCELL(any_symbol)) が常に真になっ てしまいます。vcell は S の型ではなくて、vcell の tag 型を持っている必 要があります。いうなれば vcell の tag bits は S の所有物ではありません。 それから、vcell が生きてるのに G bit が立っている状態を許すと、CAR(), CDR() などに G bit を mask out する演算が入ってしまい、cons のtag が 00 であることが生かせません。これはどうせ incremental GC と共存できま せんが。 Alignment については、どうせいずれ posix_memalign() の代替物を用意する ことになるのでそれを使えばいいと思います。その上で symbol を優遇して other-tag に圧縮をかければ alignment の要求は 4 bytes まで落とせるので、 memory の浪費も 1 object 4 bytes までになります。Alignment をしっかり してない system ではこれはしょうがないんじゃないでしょうか。そもそも malloc() 側の book keeping が in-place で行われていると、それに関わる data が word 単位で space を消費するので、word align されていない system の方が珍しいんじゃないかという、まぁこれは希望的観測なわけです が。 そうでなくとも、module を support するときにはどうせ binding を S の外 側に押し出すことになる (i.e. vcell を廃止して module-local な gloc を 導入とかする) ので、今はこれでいいと思います。 > ScmObj の convention に縛られない、というのはわかるんですが、 > ScmObjを格納してはいけないという制約もあるんでしたっけ? G bit を立ててますから、基本的にはダメです。ただし、例えば S->Y が必ず cons 型だとわかっているなら、それをその型の other-tag として定義するこ とはできます。滅多な事で使うわけにはいきません。 > > > ........|011 : String : string length > > > ........|101 : Vector : vector length > > > .....|000111 : Values : unused, all 0 (for efficiency) > > > .....|001111 : Func : ScmFuncTypeCode > > > .....|010111 : Port : ScmPortDirection > > > .....|011111 : Continuation : unused, all 0 > > > .....|100111 : C Pointer : pointer type (0 = void *, 1 = ScmFuncType) > > > > この ScmFuncType というのは? sizeof(function pointer) != sizeof(object > > pointer) への対策でしょうか。でもこういう platform は今でも使われてるん > > ですか? C99-rationale には PDP-11 がどうとか書いてあった気がしますが。 > > ;; 何々 pointer というのは C 規格 level での用語の意味。 > > ↓こいつの事です。 > > typedef ScmObj (*ScmFuncType)(); こんな奴いたっけ(笑) > が、こっちを使う方が適切ですね。 > > typedef void (*ScmCFunc)(void); うーむ、これはそもそもどうやって使うもんなんでしょうか。 ;; 実装内容は知っています > > 何故? >NULL|tag, #f==0 > > #f == 0についてはzero register, jnz, jz, cmovnz, cmovzの類での効 > 率化期待です。 > > #fや()は井上さん形式にすると5-6bit必要になるんでアーキテクチャに > よっては最小のimmediate operand fieldに収まらなくなったりするし、 > 明示的な比較命令も必要になります。 良く使うのは 7 bit ですけど、入らんのですか。具体的にはどの architecture? (興味津々 > > CONSP() が多いので code size は増えそうな気がしますが? というか↑のように > > して他の即値と一緒に入れましょうよ。 > > 逆にNFALSEP, FALSEPではコードサイズ減少が見込めるんでそうそう肥 > 大化はしないんじゃないかと思ってます。CONSPでもレジスタに残って > る値のゼロ判定が追加されるだけだし。実際どうなるか確実な予測はで > きてませんが。 そうか、cons の下が 0 だとその辺がえらく簡略化されますね。 ;; x86 はあんまり恩恵無さそうですが でも、7 bit 以上の即値を効率的に扱えない処理系が多いのならそうしてもいい と思いますが、ちょっと正直なところ 7 bit 以下に turnover をもってる architecture がどれぐらいあるのか見せつけられないと納得いきません。とり あえず手元の M32R, PowerPC, Alpha, x86-64 を見ましたが、こいつら design が古いのでアテになりません (M32R はともかく)。 ちなみに使用頻度はこんな感じ。grep で拾って数えただけなので、不正確で す (行頭を見てわかる comment を除くぐらいはしましたが)。でも目安にはなる でしょう。集めたのは [A-Z]+P( で見つかるもの。ASSERT_ は数える直前に strip。可変引数の処理が入ると CONSP() が増えるはず。何にしても NULLP() 多すぎ。 141 : NULLP( 72 : CONSP( 62 : INTP( 28 : FALSEP( 27 : SYMBOLP( 26 : STRINGP( 15 : PORTP( 15 : NFALSEP( 14 : CHARP( 8 : PROCEDUREP( 8 : EXP( 7 : CLOSUREP( 5 : VALUEPACKETP( 3 : FUNCP( 3 : EOFP( 2 : CONTINUATIONP( 2 : BOUNDP( 1 : VALIDP( 1 : UNBOUNDP( 1 : INTERESTINGP( 1 : ENVP( > > > ・こいつらは定数ではなく普通のsyntaxやsymbolとして扱う > > > > > > - Quote > > > - Quasiquote > > > - Unquote > > > - UnquoteSplicing > > > > そういや symbol 回りを独立させるとかいう話はどうなったのかなー…なんて > > 言ってみたり > > ありゃ、なんかありましたっけ。もう思考がSigSchemeから離れて > composer branchの方に戻っちゃってるんで思い出せない… じゃぁ気にしないようにw Composer branch を守ってやってください。 -- Jun Inoue jun.l****@gmail*****
