Boehm GCを使おう

伊藤 彰則
1999.1.15

はじめに

CやC++である程度大きなプログラムを書く場合,最大の問題点は メモリ管理である.複雑なプログラムの場合,必要なメモリの量を あらかじめ見積っておくのが難しいから,メモリが必要になった 時点でメモリを確保し,不要になったらそれを解放するという プログラミングスタイルが一般的だ.Cで言えばこんな感じだ.

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

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

  1. free(x) を忘れると,プロセスがどんどん大きくなってしまう.
  2. free() してはいけないものを間違ってfree()する(たとえば,同じ メモリを2回 free() してしまうとか)と,その free() の中でなく, 全然違う場所でエラーが発生することがあるので,デバッグが非常に 困難.
C++を使うと,コンストラクタ/デストラクタが使えるので,多少 メモリ管理が楽になる.しかし,この場合も new したものを delete するのはプログラマの責任であって,基本的にはCの場合と大差 ない.

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

GCとは

まずGCの説明から始めよう.GCとはGarbage Collecter(ごみ集め) の略で,確保した後使わなくなったメモリを自動的に回収する 方法の総称だ.元はLispなどのプログラム言語に備わった機能 だったのだが,今ではCとその仲間やFortranなどを除くほとんどの言語に 備わっている.世の中には膨大な数のプログラム言語がある (Linuxで使えるものだけでも,少なくとも こんなにあるのだ) が,その中で GC を備えていない言語は少数派である. なぜかというと,GCがあった方がプログラミングが圧倒的に楽 だからだ.

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

Boehm GC とは

Boehm GC はC/C++から利用可能なGCライブラリであり, Hans J. Boehm と Alan J. Demers が書いた.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ライブラリ

Str ライブラリは,Boehm GCを使った 文字列操作ライブラリだ(作者は私).任意の長さの文字列を 扱うことができる.

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

  #define STRSIZE 256
  char str[STRSIZE];
のように,あらかじめ文字列の最大長を決めて領域を確保する. しかし,この方法には問題が多い.十分余裕を持って文字列の 長さを決めるとメモリが無駄になるし,かと言って文字列の 長さをケチると,文字列長が文字配列の長さを越えてしまい, 思わぬバグの原因になる.このような固定長の文字列操作を する場合には,文字列が文字配列の長さを越えないかどうか 慎重にチェックしながら操作しなければならないのだが, C言語標準の文字列操作ライブラリでは,このようなチェック をしていない.

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);
   }
argvを全部つなげた長さがどれ位になるかは,プログラマは 全く気にしなくてよい.Strnew()は,最初に適当な大きさの 文字列領域を確保するが,それが足りなくなると自動的に 大きい領域を確保しなおすからだ.C++のStringライブラリも ほぼ同じことをするが,Strライブラリの良い点は,何といっても 文字列の使い捨てができる点だ.必要な時に文字列を使い, 使った後は何もしなくてよいのだ.

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

Boehm GCの原理

Boehm GC は,conservative GC (保守的GC)と呼ばれるアルゴリズム に基いている.これは,基本的な stop-mark-sweep GC のアルゴリズム を改良し,C言語のような言語から使えるようにしたものだ.

まず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もある 巨大なデータだった場合,プロセスが巨大になってしまう 可能性があるからだ.

おわりに

Boehm GCを使うと,Cプログラミングのメモリ管理からほぼ完全に 解放される.そのありがたさは想像以上だ.多少でも大きなプログラム をCで書こうとしている人は,ぜひBoehm GCを使ってみてもらいたい.