consセルの型情報をどこで保持するかで悩む

scheme 研究開発 diary

要約: オブジェクト自身に型を持たせようと考えていたが、それだとメモリを食うので、変数側でだけ型を持たせる方法で何とかできないか考え中。




メモリがたった4Mなので、大量に生成する筈のconsセルのサイズはなるべく小さくしたい。
普通に考えるならconsセルの最小サイズはポインタ二つ分。
そして、ポインタの使用されていない下位2bitを使用して、car/cdrの指し示す先がconsセルなのか、或いは別の何かのポインタなのか、それとも即値なのかを表すのが効率が良いと思う(Gauche方式)。

しかし、scheme側から見た場合、あらゆる値には型(数値だとか文字列だとかclosureだとか、そういうのを判別する為の何か)を持たせたい。これにはconsセルも例外ではない。
つまり、実質的には、以下のどちらかの構造にする必要がある。

/* gauche.h より */
struct ScmPairRec {
    ScmObj car;                 /* should be accessed via macros */
    ScmObj cdr;                 /* ditto */
};

/* パターン1 */
struct Pattern1 {
    void *class; /* クラス情報をポインタとして保持(仮) */
    struct ScmPairRec pair; /* 実体として保持 */
};

/* パターン2 */
struct Pattern2 {
    void *class; /* クラス情報をポインタとして保持(仮) */
    struct ScmPairRec *pair; /* ポインタとして保持 */
};

最初はパターン1で考えていたが、これだとconsセルのサイズはポインタ三つ分になってしまう。
(ちゃんと調べていないが、Gaucheではこれに近い構造になっていると思われる(ヒープから確保したオブジェクトは常にScmHeaderを持つ、ようなので。多分))
そこでパターン2の構造を考えた。
これならconsセル同士が組み合わさってtree状になっている部分には、class情報を持つ必要がなくなる。
'(1 2 3) のようにリストを構築しても、先頭(及びcarに入った値部分)にのみクラス情報を持つ事になるので、consセルの消費するメモリ量は小さくなる。
ややっこしいのは、scheme側でcons手続きやcdr手続きを使った時だ。
cons時は、rootでなくなったconsセルの皮を剥くだけで問題ないだろう。
cdr時は、新たにPattern2の皮を生成して、それを返す事にする事になると思う。
すると、tree構造をscheme側からtraverseしていくだけで、どんどん不要な皮が作られてはすぐに捨てられる事を繰り返される事になると思われる。
これは、ちょっとGCの負荷を高めそうに思える。
そして、組み込み用途なので、GCの負荷が高まるのはちょっと避けたい。


更に色々考えた結果、オブジェクト自身が型を持たずに、変数側で型を保持しても何とかなるような気がしてきたので、その方法で作り直してみる事にする。