2005-12-30

C言語にコピーGCを実装できるような気が突然したので、
家に帰って早速作ってみた。
C言語から使えるGCとしてはBohemGCが有名であるが、
あれはmark-and-sweepだったはずなので、
あんまりパフォーマンスはよくないと思われる。
(mark-and-sweepはストレージに比例する時間、
コピーGCは生きているデータに比例する時間がかかるゆえ)
なお、今回の実装は原理的にはジェネレーショナルにするのもたやすいので、
潜在的パフォーマンスはもっと高いと言える。

今回の実装を説明する。

int with_gc(int (*f)(),int heap_size=1024*1024);
void *gc_malloc(int size);
void force_collect();

with_gc() は後述。
gc_malloc() はメモリを確保する関数。
確保したメモリは参照が外れると勝手に回収される。
force_collect() は明示的にGCを起こさせる。使う必要はない。

int main(){ return with_gc(gc_main); }

with_gcはこのように使う。
gc_mainをユーザプログラムのエントリポイントとする。

＜中略＞

実装が完成。
テストプログラムを走らせて見る。

#include <cstdio>
using namespace std;

#include "gc.h"

int gc_main()
{
  for (;;) gc_malloc(16);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
(以下略)

見事落ちることなく走り続ける。
ポインタをどこにも保持しないので、
当然のことながら生き残るメモリは0バイトである。
この時点でBoehmGCとの性能比較を行ったところ、
大体数十倍の性能を記録した。

次にオブジェクトを生存させてみる。

#include <cstdio>
using namespace std;

#include "gc.h"

int gc_main()
{
  int *p=(int*)gc_malloc(16);
  p[0]=0x12345678;
  printf("bef_ptr: %p\n",p);
  for (int i=0;i<1024*1024/32;i++){
    gc_malloc(16);
  }
  printf("aft_ptr: %p\n",p);
  printf("*** %X\n",p[0]);
  return 0;
}

int main(){ return with_gc(gc_main); }

丁度一回GCが起こるようにmallocの回数を調節する。
実行結果。

bef_ptr: 0x4b01b0
start gc ...
2 roots marked
1 alive objects, 32 bytes used ...
aft_ptr: 0x5b01b8
*** 12345678

今度はルートがマークされ、
メモリが残っているのが分かる。
バイト数がおかしいのは、gc_mallocでは
メモリブロックにヘッダを付与しているためである。
さらに、コピーGCなので、pの値が勝手に変わっていることに注目。
メモリの内容はちゃんと最初と等しい。

次に構造体経由での参照を扱ってみる。

#include <cstdio>
using namespace std;

#include "gc.h"

struct bar{
  int *p;
};

struct foo{
  bar *b;
};

int gc_main()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->p=(int*)gc_malloc(sizeof(int)*2);
  f->b->p[0]=0x12345678;
  f->b->p[1]=0x87654321;
  force_collect();
  printf("%x %x\n",f->b->p[0],f->b->p[1]);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
4 roots marked
3 alive objects, 64 bytes used ...
12345678 87654321

4 roots markd となっているのは些細なことなので、気に留めないように。
ちゃんと3オブジェクト生き残っている。

次に循環参照を持つ場合を試す。

#include <cstdio>
using namespace std;

#include "gc.h"

struct foo;
struct bar{
  foo *f;
};

struct foo{
  int n;
  bar *b;
};

int gc_main()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->f=f;
  f->n=0x12345678;
  force_collect();
  printf("%x\n",f->b->f->n);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
3 roots marked
2 alive objects, 44 bytes used ...
12345678

当然ながらこれは回収されてはいけない。

#include <cstdio>
using namespace std;

#include "gc.h"

struct foo;
struct bar{
  foo *f;
};

struct foo{
  int n;
  bar *b;
};

void hoge()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->f=f;
  f->n=0x12345678;
}

int gc_main()
{
  hoge(); // 注1
  gc_malloc(4); // 注2
  force_collect();
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...

注1にて別関数にくくりだしているのや
注2でgc_mallocを読んでいるのは一時的に残ってしまうかもしれない
ポインタへを破壊するためなので、意味のある事ではない。
実行結果はこれまた当然のことながらちゃんと全部回収されている。

http://fxp.hp.infoseek.co.jp/soft/cgc/gc.zip

今回作成したプログラムをアップロードしておく。
とても小さいプログラムなので、解読はさほど難しくないだろうから
それについての説明は省略する。

今回、性能的にもコード的にもまずまずのものができたが、
致命的な欠点がある。これをどうにかしないととても常用はできない。
もちろん、ヒープを最初に全部確保しているとか、
ファイナライザに未対応とか、
グローバル変数やstatic変数がたどれないなど些細な(？)問題点もあるが、
運用に支障をきたすレベルの問題が他にあるのだ。
おそらくこれがあるためにBohemGCはmark-and-sweepをとっている
ような気がしないでもないが、やはりどう解消したものかと思う。

と、意味深な前振りをしつつ、次回に続く。
問題点が分かり、かつ、解決策を思いついた方はすごいです。
是非とも私にご連絡を。

純粋関数型雑記帳

C with GC

結論

妙に気になること