習作GCライブラリ(1) exact copying gc

習作として単純なGCライブラリを実装してみました。とりあえず面倒だったのでヒープとスタックのサイズは固定長。
githubを使って公開してみる http://github.com/hogelog/copying_gc/tree/master

こんな感じで使う。

static Memory *memory;
void test_01() {
    Object iv, fv, str, pair;
    int i;
    for (i=0;i<2000;++i) {
        fixed_memory_push(memory,
                iv = new_ivalue(memory, i));
        printf("%p: %ld\n", iv, IVALUE(iv));

        fixed_memory_push(memory,
                fv = new_fvalue(memory, (double)i));
        printf("%p: %f\n", fv, FVALUE(fv));

        fixed_memory_push(memory,
                str = new_string(memory, "hogefuga"));
        printf("%p: %s\n", str, STR_BUF(str));

        fixed_memory_push(memory,
                pair = new_pair(memory, iv, fv));
        printf("%p: (%ld . %f)\n", pair,
                IVALUE(PAIR_CAR(pair)), FVALUE(PAIR_CDR(pair)));
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
    }
}
void test_02() {
    Object iv_0 = new_ivalue(memory, 0);
    Object pair = push_pair(memory, iv_0, iv_0);
    Object *cdr = &PAIR_CDR(pair);
    int i;
    for (i=1;i<10;++i) {
        Object iv_i = new_ivalue(memory, i);
        (*cdr) = new_pair(memory, iv_i, iv_i);
        cdr = &PAIR_CDR(*cdr);
    }
    printf("%p:", pair);
    print_object(pair);
    putchar('\n');
}

int main(int argc, char **argv) {
    Memory mainmem;
    memory = &mainmem;
    fixed_memory_init(memory, 1024, 1024);
    test_01();
    test_02();
    fixed_memory_printinfo(memory);
    fixed_memory_sweep(memory);
    puts("# run sweep");
    fixed_memory_printinfo(memory);
    return 0;
}
0x9d73008: 0
0x9d73018: 0.000000
0x9d73028: hogefuga
0x9d73038: (0 . 0.000000)
0x9d73048: 1
0x9d73058: 1.000000
0x9d73068: hogefuga
0x9d73078: (1 . 1.000000)
...
0x9d7a390: 1998
0x9d7a3a0: 1998.000000
0x9d7a3b0: hogefuga
0x9d7a3c0: (1998 . 1998.000000)
0x9d7a3d0: 1999
0x9d7a3e0: 1999.000000
0x9d7a3f0: hogefuga
0x9d7a400: (1999 . 1999.000000)
0x9d7b018:(0 . (1 . (2 . (3 . 
(4 . (5 . (6 . (7 . (8 . (9 . 9))))))))))
heap: 851 / 1024
stack: 1 / 1024
# run sweep
heap: 19 / 1024
stack: 1 / 1024

ここではヒープ長を固定長の1024としているのにアロケーション命令を8000回以上呼んでいますが、足りなくなるたびにfixed_memory_sweepが走っているので大丈夫。mainの最後で意図的にGCを走らせた後はtest_02で作った、スタックから辿ることのできる19個のオブジェクトのみ生存しています。

特におもしろいことはしていない。まあ一度は書いておかないとなあと思って書いた。しかしGC処理部分は100行もいかない程度で書けたのがおもしろかった。

2009/2/18 14:03 追記

GC処理部分だけ切り出すとこれだけ。一般教養としてのGarbage Collection片手に「こんな感じかなー」と書きました。

/* Cheney compacting Algorithm */
#define COPY_TO(obj) do {\
    if(FORWARD(obj)==NULL) {\
        Object *forward = &FORWARD(obj);\
        obj = fixed_array_push(to, obj);\
        *forward = obj;\
    } else {\
        obj = FORWARD(obj);\
    }\
} while (0)
static void copy_space(Array *from, Array *to) {
    Object scanned = from->head;
    while(scanned!=from->current) {
        switch(TYPE(scanned)) {
            case T_PAIR:
                COPY_TO(PAIR_CAR(scanned));
                COPY_TO(PAIR_CDR(scanned));
                break;
            default:
                break;
        }
        ++scanned;
    }
}
size_t fixed_memory_sweep(Memory *mem) {
    Array *stack = mem->stack;
    Array *from = mem->heap;
    Array *to = from==&mem->h1 ? &mem->h2 : &mem->h1;
    Object scanned;
 
    to->current = to->head;

    scanned = from->head;
    while(scanned!=from->current) {
        FORWARD(scanned) = NULL;
        ++scanned;
    }
    /* copy object referenced from stack */
    copy_space(stack, to);

    copy_space(to, to);

    scanned = from->head;
    while(scanned!=from->current) {
        if(FORWARD(scanned)==NULL && TYPE(scanned)==T_STR) {
            free(STR_BUF(scanned));
        }
        ++scanned;
    }

既にfromからtoへコピーされているかチェックしている処理がなんかかなしいことになっている。結局fromスペースを走査すんのかよと。既存のcopying gcの実装をちゃんと読んだことないのだが、この辺はたぶんもっとうまい方法あるんじゃないかと思う。

2009/2/21 17:15追記

電車の中でGC論文読んでて気付いたんだけど、fowarding pointerを記録の仕方が非常に阿呆だったので修正。diffで示すにこういう変更をしました。

 enum Type {
     T_INT, T_FLOAT, T_STR,
-    T_PAIR
+    T_PAIR, T_FORWARD
 };
 union Value {
     long ivalue;
     double fvalue;
     String str;
     Pair pair;
+    Object forward;
 };
 struct Object {
     Type type;
     Value value;
-    Object forward;
 };

最初の書き方だと全てのオブジェクトの構造にforward pointerを書き込む場所があった。GCの時にしか使わないのに! そんなことせずに、移動したらT_FORWARD型にして参照先を値として記録すればいいのでした。データ構造の変更に従い、アルゴリズムも変更。

/* Cheney compacting Algorithm */
#define COPY_TO(obj) do {\
    if(TYPE(obj)==T_FORWARD) {\
        obj = FORWARD(obj);\
    } else {\
        Object new = fixed_array_push(to, obj);\
        FORWARD_SET(obj,new);\
    }\
} while (0)
static void copy_space(Array *from, Array *to) {
    Object scanned = from->head;
    while(scanned!=from->current) {
        switch(TYPE(scanned)) {
            case T_PAIR:
                COPY_TO(PAIR_CAR(scanned));
                COPY_TO(PAIR_CDR(scanned));
                break;
            default:
                break;
        }
        ++scanned;
    }
}
size_t fixed_memory_sweep(Memory *mem) {
    Array *stack = mem->stack;
    Array *from = mem->heap;
    Array *to = from==&mem->h1 ? &mem->h2 : &mem->h1;
    Object scanned;

    to->current = to->head;

    /* copy object referenced from stack */
    copy_space(stack, to);
    
    copy_space(to, to);

    scanned = from->head;
    while(scanned!=from->current) {
        if(TYPE(scanned)==T_STR) {
            free(STR_BUF(scanned));
        }
        ++scanned;
    }

    mem->heap = to;
    return (from->current-from->head) - (to->current-to->head);
}

短かくなってくれましたね、ありがたいありがたい。COPY_TOがマクロなのは、ついなんとなくなんだけど今どきこういうの関数にするでしょうとかそんな意見はありえますねううん

test