Schemeをつくろう(18) GC作ってみた。

前回作ったSchemeの欠点を克服すべく第二段を作ろうかと。まったりペースでSchemeを作ります。

今回の目標は、

  1. 独自GC
  2. 末尾呼び出しの最適化

とりあえず2点を目標にしていきたいと思います。

まず

ペアと、数字オブジェクトを作りました。

これだけあればなんとかなるかな。

早速GCを作ってみた。

今回のテーマはGCっす。前回はライブラリ任せで楽チンしてましたが、今回は自作するぞぉぉぉ!!

早速ですが、初歩的なGCを作りました。マークして、スイープする奴。

まず、

mallocのついでにオブジェクトというオブジェクトを線形リストで繋ぎます。

ペア->ペア->数字->数字->ペア->NULL

ガリガリ繋いで。

GCしてみる

とりあえず全部使ってないというフラグを立てる。

ペア->ペア->数字->数字->ペア->NULL
N     N     N     N     N

オブジェクトは全部使ってないと仮定する。

使ってるオブジェクトにチェックを入れる

参照があるものはチェックを入れて、

ペア-+->数字
U    |  U
     +->ペア-+->数字
        U    |  U
             +->NULL

コレは消しちゃダメー。とフラグを立てる。

するっと

使ってないオブジェクトがわかるので、Nの立ってる奴を探して、

ペア->ペア->数字->数字->ペア->NULL
U     U     U     U     N

freeして、繋ぎなおし。

ペア->ペア->数字->数字->NULL
U     U     U     U

綺麗になる。

実装

やってみると案外簡単。

#include <stdio.h>
#include <stdlib.h>

typedef struct object* object;
typedef struct scheme* scheme;

enum {T_NUMBER, T_PAIR};
enum {GC_USE, GC_NOT_USE};

struct pair {
    object car;
    object cdr;
};

struct object {
    int type;
    union {
        int n;

        struct pair *c;
    } data;
    int gc_flag;
    struct object *gc_next;
};

int malloc_counter = 0;

void *xmalloc(int size)
{
    malloc_counter++;

    return malloc(size);
}

void xfree(void *o)
{
    malloc_counter--;

    free(o);
}

struct scheme {
    int object_counter;
    object gc_used;
};

/* object */

object new_object(scheme scm, int type)
{
    scm->object_counter++;

    object o = xmalloc(sizeof (struct object));

    o->type = type;

    o->gc_next = scm->gc_used;
    scm->gc_used = o;

    return o;
}

void free_object(scheme scm, object o)
{
    scm->object_counter--;

    switch(o->type) {
    case T_PAIR:
        xfree(o->data.c);
        break;
    }
    xfree(o);
}

/* objects */

object new_number(scheme scm, int n)
{
    object o = new_object(scm, T_NUMBER);

    o->data.n = n;

    return o;
}

object new_cons(scheme scm, object car, object cdr)
{
    object o = new_object(scm, T_PAIR);

    o->data.c = xmalloc(sizeof (struct pair));

    o->data.c->car = car;
    o->data.c->cdr = cdr;

    return o;
}

#define cons(a, d) new_cons(scm, a, d)
#define number(a) new_number(scm, a)

object car(object o)
{
    return o->data.c->car;
}

object cdr(object o)
{
    return o->data.c->cdr;
}

object null(void)
{
    return NULL;
}

int is_null(object o)
{
    return o == NULL;
}

int is_pair(object o)
{
    return !is_null(o) && o->type == T_PAIR;
}

int is_list(object o)
{
    return is_null(o) || o->type == T_PAIR;
}

void display(object o)
{
    if (o == NULL) {
        printf("()");
        return;
    }

    switch(o->type) {
    case T_NUMBER:
        printf("%d", o->data.n);
        return;
    case T_PAIR:
        printf("(");
        for (;;) {
            display(car(o));
            o = cdr(o);
            if (is_null(o)) {
                break;
            } else if (!is_pair(o)) {
                printf(" . ");
                display(o);
                break;
            } else {
                printf(" ");
            }
        }
        printf(")");
        return;
    }
}

void newline(void)
{
    printf("\n");
}

/* gc */

void gc_clean_iter(scheme scm, object o)
{
    if (o == NULL)
        return;

    gc_clean_iter(scm, o->gc_next);
    free_object(scm, o);
}

void gc_clean_all(scheme scm)
{
    gc_clean_iter(scm, scm->gc_used);
}

void gc_check(scheme scm)
{
    object o;

    for (o = scm->gc_used; o != NULL; o = o->gc_next)
        o->gc_flag = GC_NOT_USE;
}

void gc_mark_object(object o)
{
    if (o == NULL)
        return;

    o->gc_flag = GC_USE;

    switch(o->type) {
    case T_PAIR:
        gc_mark_object(car(o));
        gc_mark_object(cdr(o));
        return;
    default:
        return;
    }
}

object gc_sweep(scheme scm, object o)
{
    if (o == NULL)
        return NULL;
    else if (o->gc_flag == GC_NOT_USE) {
        object tmp = gc_sweep(scm, o->gc_next);
        free_object(scm, o);
        return tmp;
    } else {
        o->gc_next = gc_sweep(scm, o->gc_next);
        return o;
    }
}

/* scheme */

scheme scheme_init(void)
{
    scheme scm = xmalloc(sizeof (struct scheme)); 

    scm->object_counter = 0;
    scm->gc_used = NULL;

    return scm;
}

void scheme_end(scheme scm)
{
    gc_clean_all(scm);

    printf("end : %d\n", scm->object_counter);

    xfree(scm);

    printf("malloc : %d\n", malloc_counter);
}

void gc_test(scheme scm, object o)
{
    object copy = cons(car(o), cdr(o));

    printf("check : %d\n", scm->object_counter);
    gc_check(scm);

    printf("copyを残す : ");
    display(copy);
    newline();

    gc_mark_object(copy);

    scm->gc_used = gc_sweep(scm, scm->gc_used);

    printf("clean : %d\n", scm->object_counter);
}

int main(void)
{
    scheme scm = scheme_init();

    object o = cons(number(2), cons(number(1), null()));

    display(o);
    newline();

    gc_test(scm, o);

    scheme_end(scm);

    return EXIT_SUCCESS;
}

やっぱScheme作るのは楽しいっす。

しかし、課題山積

ここからが大変そうだ。

  • 結構重そうなので、軽量化を図る。
  • 何を残して、何を消すのか。参照をどのように見つけるか。
  • GCのタイミングはいつか?
  • 循環参照してると、無限ループしちゃう。(見たオブジェクトを除外すればよさげ)

まだまだ課題山積っす。しばらくGCカウンタとの戦いが続きそうデス。

さ、コードリーディングしよう〜。