Boehm GCを使おう

はじめに

  char *x;
   ...
  x = (char*)malloc(n*sizeof(char));
   ... x を使って仕事をする ...
  free(x);

このプログラミングスタイルの問題点は，おおまかに言って こんなところだろう．

1. free(x) を忘れると，プロセスがどんどん大きくなってしまう．
2. free() してはいけないものを間違ってfree()する(たとえば，同じ メモリを2回 free() してしまうとか)と，その free() の中でなく， 全然違う場所でエラーが発生することがあるので，デバッグが非常に 困難．

ところが，このメモリ管理をプログラマが全然面倒見なくてすむ 画期的な方法がある．それがBoehm GCだ．

GCとは

GCにはさまざまなアルゴリズムがあり，現在も盛んに研究されて いる．Boehm GC のアルゴリズムについては後述するが，詳しくは GC FAQ を見るとよいだろう．また，情報処理学会誌94年11月号 にGCの特集があり，詳しい解説が読める．

Boehm GC とは

Boehm GCが提供するのは，基本的に GC_malloc(),GC_malloc_atomic(),GC_realloc() という3つの関数である．これらは，C のライブラリの malloc() と realloc() に対応していて，使い方も同じだ．GC_free() という 関数も提供されるが，なまじ GC_free() を使うとバグの元なので， 使わない方が良い．

GC_malloc()とGC_malloc_atomic()は基本的には同じだが，GC_malloc_atomic() は内部にポインタを含まないデータの確保に使う．例えば文字列データを 確保する場合などに GC_malloc_atomic()を使う． この場合にGC_malloc() を使ってもちゃんと動くのだが，GC_malloc_atomic() を使った方がGCの効率が上がる．

これらの関数を使うと，プログラミングスタイルはこんな風に変わる．

  char *x;
   ...
  x = (char*)GC_malloc_atomic(n*sizeof(char));
   ... x を使って仕事をする ...

つまり，GC_malloc() で確保したメモリは，自分で解放する必要がないのだ． 必要なときにメモリを確保すれば，それでOK．メモリの使い捨てが可能に なる．これがどんなに楽かは，一度プログラムを書いてみればよく分かる だろう．

実例：Strライブラリ

普通のCの文字列操作では，

  #define STRSIZE 256
  char str[STRSIZE];

Strライブラリを使うと，文字列の最大長を全く気にしなくて 良くなる．例えば，argvの内容を全部つなげて表示するプログラム は，こんな感じになる．

  #include <Str.h>

  main(int argc, char *argv[])
  {
    Str str = Strnew();
    int i;

    for (i = 1; i < argc; i++)
      Strcat_charp(str,argv[i]);

    Strfputs(str,stdout);
   }

Strライブラリと同じ方法を使えば，可変長の配列も作ること ができる．ただし，データ型ごとに配列を定義しなければならない ので，実際にはちょっと面倒かもしれない．

Boehm GCの原理

まずstop-mark-sweepの説明から始めよう．GCには多くのアルゴリズム があるが，stop-mark-sweepは最も基本的なGCのアルゴリズムの1つ だ．このアルゴリズムは，まず「このデータは確実に使用中だ」 というデータを特定するところから始まる．このようなデータは， スタック領域や定数領域にあるポインタからなる．次に，その領域 にあるポインタが参照しているデータ(これも使用中のはずだ)に 「印」を付ける．さらに，「印」のついたデータから参照されて いるデータにも「印」をつけ，さらに... という感じで，使用中の データに次々に印をつける．使用中のデータすべてに印を付け終わ ったら，「印」のついていないデータを回収する．ここで言う「回収」 とは，これらのデータを後で再利用できるように，使用済データの 一覧表のようなものを作ることを意味している．これで，使用済の データを自動的に再利用することができる．

C言語で，このstop-mark-sweep方式のGCをやろうとすると，問題がある． stop-mark-sweep GCはポインタから参照されているデータに次々に 印をつけるのだが，C言語の場合，メモリの内容を見ただけでは， どれがポインタでどれが数値かわからないのだ．これがLispなどの 場合には，データ自体に「これは数値」「これはポインタ」という 区別がある(区別の方法はいろいろある)のだが，Cの場合には それがない．そこで，保守的GCでは，「ポインタかもしれないもの」 を全てポインタとみなしてGCを行なう．そうすると，当然 「本当は回収してもいいのに，間違って回収しそこねてしまう」 データが発生する．例えば，0x00b0ef00 番地のデータが「ごみ」 だったとしても，どこかの変数に11595520という数値が(そのデータとは 無関係に)入っていたとしたら，この変数が 0x00b0ef00 番地を 指すポインタとみなされるため，0x00b0ef00 番地のデータは 回収されそこねてしまう．しかし，Boehmらの実験によると， そのようなデータは量的にあまり多くないので，ほとんど無視 しても問題はない．

…というのが保守的GCの原理だ．このように，「ポインタかもしれない ものをすべてポインタとみなす」方式のため，上で書いたような GC_malloc_atomic()という関数が存在する．この関数で確保された 領域にはポインタがないことがわかっているから，「ごみ」を 回収しそこねるリスクを減らすことができるのだ．

Boehm GCを使う場合の注意点として，「あまり大きい領域を 一度にGC_malloc()で確保しない」ということが挙げられるだろう． 上記のように，Boehm GCで確保したメモリは，ある確率で 回収されそこねる危険がある．それがたまたま数MByteもある 巨大なデータだった場合，プロセスが巨大になってしまう 可能性があるからだ．

おわりに