『お気楽Ｃ言語プログラミング超入門』の番外編です。本ページでは、超入門で取り上げることができなかったデータ構造やアルゴリズムなど、いろいろなプログラムをＣ言語で作ってみようと思っております。少々難しい話になるかもしれませんが、よろしければお付き合いくださいませ。
今回は「ガベージコレクション (garbage collection: GC)」の基本的な仕組みを簡単に説明します。そして、Ｃ/Ｃ++用のガベージコレクタ Boehm GC を紹介します。
簡単な例として、「連結リスト (セル)」のガベージコレクションを考えてみます。説明の都合上、セルは複数個まとめて malloc で確保することにします。これを「セル領域」と呼ぶことにします。そして、下図のように未使用のセルをつないで管理します。
cell_free --> [ | ] --> [ | ] --> ... --> [ | ] --> NULL
図 : 未使用セルのリンケージ
cell_free は未使用のセルを保持する変数です。未使用のセルはリストで管理します。これを「フリーリスト」と呼ぶことにします。
ガベージコレクションの基本的な動作は、使用しているセルと不要になったセルを区別して、不要になったセルを回収することです。セルはプログラムのいろいろな場所から参照されます。スタック上に確保された局所変数や静的に確保された外部変数、レジスタや他のセルからも参照されます。
このように、セルを参照している領域はいろいろありますが、セル以外の領域をまとめて「ルート (root)」と呼ぶことにします。すると、ルートから参照されているセルはプログラムで使用中のセルと考えることができます。そして、使用中のセルからたどることができるセルも、また使用中のセルと考えることができます。ルートからたどることができないセルを「到達不能」であるといいます。到達不能なセルは「不要になったセル」と判断することができます。
到達不能なセルが生じたことを検出する簡単な方法は、各セルに「参照回数」を持たせることです。変数やセルのメンバ変数などで、あるセルのアドレスをセットしたとき、そのセルの参照回数を +1 します。アドレスを書き換えたときは、元のセルの参照回数を -1 します。そして、参照回数が 0 になったならば、そのセルは到達不能になったので回収します。これを「リファレンスカウント法 (Reference counting)」といいます。
リファレンスカウント法には大きな欠点があります。循環リストがある場合、参照回数だけでは到達不能なセルを検出することができないのです。次の図を見てください。
┌───────────────┐
A↓ B C │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数──→│１│・┼─→│２│・┼─→│３│・│
└─┴─┘ └─┴─┘ └─┴─┘
RC:2 RC:1 RC:1
┌───────────────┐
A↓ B C │
┌─┬─┐ ┌─┬─┐ ┌─┬┼┐
変数─Ｘ→│１│・┼─→│２│・┼─→│３│・│
└─┴─┘ └─┴─┘ └─┴─┘
RC:1 RC:1 RC:1
図 : 循環リスト
ある変数がセル A を参照している状態で、各セルの参照回数を RC で表しています。セル A は変数とセル C から参照されているので RC は 2 になります。セル B と C の RC は 1 です。この状態で変数の値を書き換えて、セル A の RC が -1 されたとします。
すると、A の RC は 1 になりますが 0 にはならないので、A を回収することはできません。セル B はセル A だけから参照されていますが、セル A が生き残っているので、RC は 1 のままです。セル C も同様です。つまり、循環リストがあると、ルートから到達できない状態になっても参照回数が 0 にならないのです。
このため、リファレンスカウント法を使う場合は、到達不能な循環リストを検出するため、他のアルゴリズムと組み合わせることがあります。たとえば、スクリプト言語 Python の GC はリファレンスカウント法が基本ですが、循環したデータ構造を検出して回収するため、アルゴリズムが異なる GC も使っています。
もう一つ基本的な方法に「マークスイープ法 (mark sweep)」があります。マークスイープ法は、未使用なセルがなくなった時点で GC を起動して、到達不能になったセルをいっきに回収する方法です。まず、ルートからたどることができるセルすべてに印をつける作業 (Mark) を行います。それから、セル領域全体を探索して、マークの付いていないセルを回収する作業 (Sweep) を行います。このように、2 段階の手順をふんで GC を実行することからマークスイープ法と呼ばれています。
ただし、Ｃ言語やＣ++でマークスイープ法を実行する場合、スタック領域やレジスタに格納されている値が、たんなる数値なのかセルへのポインタなのか区別することができません。このため、曖昧な値はセルとして判定することにします。これを「保守的な GC (conservative GC)」といいます。
マークするとき、値がセル領域の範囲外あれば数値と判定することができます。また、セルが偶数番地から配置されているとすると、セル領域の範囲内であっても値が奇数であれば、それも数値として判定することができます。とりあえず、それ以外の値はセルとして判定するのが保守的な GC なのです。
当然ですが、保守的な GC は数値としてスタックに詰まれたデータを間違ってセルと判定することがあります。その数値に対応するセルが到達不能な場合、そのセルを回収することはできません。ですが、その頻度がそれほど多くなければ、プログラムの実行に大きな影響を及ぼすことは少ないと考えられます。今回紹介する Bohem GC は保守的な GC を採用しています。
Boehm GC (http://www.hboehm.info/gc/) はＣ/Ｃ++ 用の「ガベージコレクタ (garbage collector)」です。malloc を GC_MALLOC に変えるだけで、不要になったメモリを自動的に回収してくれます。最近のプログラミング言語、特に関数型言語やスクリプト言語では、当然のように GC が実装されていますが、Boehm GC を使っている処理系もあります。たとえば、M.Hiroi も愛用している Gauche (Scheme) がそうです。
Debian 系の Linux であれば、次のコマンドで Boehm GC をインストールすることができます。
$ sudo apt install libgc-dev
基本的な使い方は簡単です。ヘッダファイル gc.h をインクルードします。そして、malloc, calloc のかわりに GC_MALLOC (内部にポインタを含まない場合は GC_MALLOC_ATOMIC) を、realloc のかわりに GC_REALLOC を使い、プログラムから free を削除します。あとは、コンパイルするときに -l オプションで gc を指定する (-lgc とする) だけです。
Boehm GC については LinuxC | GC (http://linuxc.info/memory/gc/) を参考にさせていただきました。有益な情報を公開されている khondalit さんに感謝いたします。
それでは簡単な例題として、連結リストを使って順列を生成するプログラムを作ってみましょう。最初にセルを定義します。
リスト : Boehm GC の使用例
#include <stdio.h>
#include <gc.h>
// セルの定義
typedef struct cell {
int item;
struct cell *next;
} Cell;
// セルの生成
Cell *make_cell(int x, Cell *next)
{
Cell *cp = GC_MALLOC(sizeof(Cell));
cp->item = x;
cp->next = next;
return cp;
}
構造体 Cell はポインタを含んでいるので、メモリの取得には GC_MALLOC を使います。GC_MALLOC_ATOMIC を使ってはいけません。
次に、順列を生成するプログラムを作ります。
リスト : 順列の生成
// セルの表示
void print_cell(Cell *cp)
{
for (; cp != NULL; cp = cp->next)
printf("%d ", cp->item);
printf("\n");
}
// x と等しいセルを削除
Cell *remove_cell(int x, Cell *cp)
{
if (cp == NULL)
return NULL;
else if (cp->item == x)
return remove_cell(x, cp->next);
else
return make_cell(cp->item, remove_cell(x, cp->next));
}
// 順列の生成
void perm(Cell *nums, Cell *a)
{
if (nums == NULL)
print_cell(a);
else
for (Cell *cp = nums; cp != NULL; cp = cp->next) {
perm(remove_cell(cp->item, nums), make_cell(cp->item, a));
}
}
関数 print_cell は連結リストを表示します。関数 remove は引数 x と等しい要素を削除します。remove は引数のリストを破壊的に修正せず、新しいリストを生成していることに注意してください。
関数 perm は数字のリスト nums から数字を順番に選択します。そして、nums から選んだ数字を削除し、それを累積変数 a のリストに追加して perm を再帰呼び出しします。これで nums に格納された数字の順列を生成することができます。
関数型言語でリストを操作するときは、このように引数のリストを破壊せずに新しいリストを生成することがよく行われます。当然ですが、セルを消費するだけではメモリ不足になってしまいます。GC があると、不要になったメモリを自動的に回収してくれるので、このようなプログラムでも正常に動作します。
それでは実際に試してみましょう。次のテストを行ってみました。
リスト : 簡単なテスト
// 数列の生成
Cell *iota(int n, int m)
{
Cell *a = NULL;
while (n <= m) {
a = make_cell(m, a);
m--;
}
return a;
}
int main(void)
{
perm(iota(1, 9), NULL);
printf("%lu\n", GC_gc_no);
return 0;
}
関数 iota は n から m までの数値を格納したリストを生成します。perm(iota(1, 9), NULL) で、1 から 9 までの順列を生成することができます。このプログラムを実行して、タスクマネージャなどでメモリの使用量をチェックすると、大量のメモリを消費せずにプログラムが動作していることがわかります。それから、GC_gc_no [*1] には GC を行った回数が記録されています。M.Hiroi の環境では 494 回 GC が起動されました。
それにしても、Boehm GC はとても便利ですね。興味のある方はいろいろ試してみてください。
リスト : Boehm GC の簡単なテスト
#include <stdio.h>
#include <gc.h>
// セルの定義
typedef struct cell {
int item;
struct cell *next;
} Cell;
// セルの生成
Cell *make_cell(int x, Cell *next)
{
Cell *cp = GC_MALLOC(sizeof(Cell));
cp->item = x;
cp->next = next;
return cp;
}
// セルの表示
void print_cell(Cell *cp)
{
for (; cp != NULL; cp = cp->next)
printf("%d ", cp->item);
printf("\n");
}
// x と等しいセルを削除
Cell *remove_cell(int x, Cell *cp)
{
if (cp == NULL)
return NULL;
else if (cp->item == x)
return remove_cell(x, cp->next);
else
return make_cell(cp->item, remove_cell(x, cp->next));
}
// 順列の生成
void perm(Cell *nums, Cell *a)
{
if (nums == NULL)
print_cell(a);
else
for (Cell *cp = nums; cp != NULL; cp = cp->next) {
perm(remove_cell(cp->item, nums), make_cell(cp->item, a));
}
}
// 数列の生成
Cell *iota(int n, int m)
{
Cell *a = NULL;
while (n <= m) {
a = make_cell(m, a);
m--;
}
return a;
}
int main(void)
{
perm(iota(1, 9), NULL);
printf("%lu\n", GC_gc_no);
return 0;
}