bobuhiro11's diary

scheme REPLとガベージコレクション

07 Mar 2014

REPL

普通のREPL． 相変わらずパイプで繋いでる． トップレベルにS式を打ち込む度に流し込んでやるとできた．

逆アセンブル

(disasm ..)とかいう命令を追加した． こんな感じで逆アセンブルした結果を確認できる．

>>(disasm (+ 1 2 3))
=== code ===
 0 0x12000002 ;FRAME
 1 0x0000003c ;15
 2 0x25000002 ;CONSTNUM
 3 0x0000000c ;3
 4 0x13000002 ;ARGUMEMT
 5 0x25000002 ;CONSTNUM
 6 0x00000008 ;2
 7 0x13000002 ;ARGUMEMT
 8 0x25000002 ;CONSTNUM
 9 0x00000004 ;1
10 0x13000002 ;ARGUMEMT
11 0x03000002 ;REFER_GLOBAL
12 0x094bf2f3 ;+
13 0x15000002 ;APPLY
14 0x0000000c ;3
15 0x27000002 ;DISASM
16 0x00000002 ;HALT

ガベージコレクション

cheneyのcopy gcを実装して埋め込んだ． 同じ大きさのFrom空間とTo空間という二つの領域を確保しておいて， From空間にallocateしていく． From空間が満タンになれば，ルートオブジェクト(レジスタとかシンボルテーブルとか)から たどれるオブジェクトをすべてTo空間にコピーする． 全部のコピーが終われば，From空間とTo空間を交換する． 単純なアルゴリズムともいえるけど，ルートを忘れやすいので注意が必要． ヒープの効率が悪くなったり，保守的GCじゃないなどデメリットがある． まあヒープは現状問題ないだろうし，スタックやレジスタの要素がオブジェクトかプリミティブ かは判定できるのでexactなGCで問題ない． メリットは，フラグメンテーションが起こらない，キャッシュと相性がよいなど素晴らしい． ここまでは，copy gcの話．

cheneyが発表したのは，オブジェクトの探索を幅優先で行うということ．(たぶんこれだけ??) マシンスタックの消費が少なくなり効率がよい． ただ，幅優先なので近いオブジェクト同士が離れてしまってキャッシュが効きにくくなる． (ペアオブジェクトとcarのオブジェクト，cdrのオブジェクトが離れてしまうということ) これの改善方法として，近似的に深さ優先で行うアイデアもあるみたい．

おれおれschemeでは以下のようなものがルートになる．

ボックスは元々別の方法で管理していたが，vm_obj構造体で扱うことにした． プリミティブ型以外はすべてこの構造体を利用する． (forwardingメンバはもうコピー済みのオブジェクトで使うのでわざわざいらないな…)

struct vm_obj
{
	unsigned char tag;

	/* 
	 * memory allocated size contain string, closure etc.
	 * set by myalloc() and must not change the value.
	 */
	int size;

	/* 
	 * point new memory address in to-space, used by GC
	 */
	struct vm_obj *forwarding;

	union{
		vm_data box;
		struct {
			int size;
		} stack;
		struct {	
			int size;
		} closure;
		struct {
			vm_data car;
			vm_data cdr;
		} pair;
	} u;
};

文字列やクロージャの自由変数への参照は，この直後に配置している． ここはコードを書いたほうがわかりやすいかもしれない． 普通はどうするもんなのだろう． この構造体だけGCで管理して，文字列などはmallocn()に頼ってもいけるだろうし．

size = sizeof(struct vm_obj) + strlen(str) +1;
obj = myalloc(size, reg_a, reg_c, reg_s);
obj->tag = VM_OBJ_STRING;
string = (char*)obj + sizeof(struct vm_obj);
strcpy(string,str);

あとFrom空間が満タンになったときは，自動でGCが走るようになっているが任意のタイミングでGCを動かせるように命令を追加した． +640とか+880とかいうのが今allocateされているメモリサイズ(バイト数)．

$ make run
compiler/main.scm | vm/myscmvm
=== INFO ===
HOST_BIT:            32
CODE_MAX:          2048
HEAP_CODE_BASE:    1365
STACK_MAX:         1024
=== hash table ===
y        = 0x00000400 ;256
/        = 0x08bd523b ;closure<1395,1397>
=        = 0x08bd50ab ;closure<1365,1367>
hoge     = 0x08bd5083 ;"hogehogemanju"
<        = 0x08bd514b ;closure<1377,1379>
*        = 0x08bd5213 ;closure<1392,1394>
boss     = 0x08bd506f ;("orenosubete" "damedamehime")
cons     = 0x08bd5173 ;closure<1380,1382>
x        = 0x000001ec ;123
>        = 0x08bd5123 ;closure<1374,1376>
cdr      = 0x08bd51c3 ;closure<1386,1388>
null?    = 0x08bd51eb ;closure<1389,1391>
+        = 0x08bd50fb ;closure<1371,1373>
modulo   = 0x08bd5263 ;closure<1398,1400>
-        = 0x08bd50d3 ;closure<1368,1370>
car      = 0x08bd519b ;closure<1383,1385>
>>(gcdump)
=== gc ===
from_start: 0x0000000008bd5008
from_free:  0x0000000008bd5288[+640]
to_start:   0x0000000008bd9e30
to_free:    0x0000000008bd9e30
undef
>>(list "hoge" "foo" "a-chan" "nya-")
("hoge" "foo" "a-chan" "nya-")
>>(gcdump)
=== gc ===
from_start: 0x0000000008bd5008
from_free:  0x0000000008bd5378[+880]
to_start:   0x0000000008bd9e30
to_free:    0x0000000008bd9e30
undef
>>(gcrun)
Info: collecting garbage...
undef
>>(gcdump)
=== gc ===
from_start: 0x0000000008bd9e30
from_free:  0x0000000008bda0b0[+640]
to_start:   0x0000000008bd5008
to_free:    0x0000000008bd5008
undef
>>
< scheme VMをCで書く Gentoo install on Virtualbox >