D言語のGCの仕組み

ゲームにおいては、コマ落ちを防がなくてはなりません。マシンが遅いために、制作側で想定しているfsp(frames per second : 秒間フレーム数)が出ないのは仕方ないとしても、GC(ガーベジコレクタ)が動作したために数フレーム完全に動きが止まる、というようなことがあってはいけません。

この章では、ゲームプログラミングにおけるGC対策を紹介します。

まずは、GCの仕組みについて詳しく見ていきます。この部分を理解すれば、コマ落ちの発生しないプログラムをD言語で書くことが出来ると思います。

※　GCとは、使われていないメモリを自動的に解放する仕組みです。

使われていないとは、おおざっぱには、どこからも参照されていない、の意味だと考えて良いでしょう。前提知識として、D言語[Digital Mars Dの翻訳]のガーベジコレクションのところを読んでください。

GCのroot集合とスキャン

GCが使用しているメモリをスキャンする開始集合のことをroot集合と呼びます。

「staticデータセグメントと、各スレッドのスタック、そしてレジスタの内容」がroot集合です。スタックは、スタックbottomから、現在使用している部分(スタックtop＝espレジスタの値)までがスキャンの対象となります。

また、GCは、ポインタでない型の変数はスキャンしません。ただし、GCはbyte[]のような配列に対してもスキャンを行ないます。これについては後述します。

byte[]の場合、配列サイズがわかっているので、その配列の終端まですべてがスキャンの対象となります。byte*の場合も、確保してきたメモリサイズをGCに問い合わせ、そのメモリの終端まですべてがスキャンの対象となります。

この意味において、GCとしては、(いわゆる)conservative(=保守的)なGCであると言えます。

すなわち、


	byte [] ab = new byte[4];
	desttest d = new desttest;
	*cast(desttest*)(&ab[0]) = d;

このように、byte配列にアドレスを入れた場合、このbyte配列abが解放されるまではdesttestのデストラクタは呼び出されません。GCはメモリを解放するときに、デストラクタを呼び出します。

よって、私の書いたマイクロスレッドのプログラムは、

ａ．マイクロスレッドのスタックは、マイクロスレッドクラスのメンバ(byte配列)が保持している仮想スタックである。
ｂ．マイクロスレッドの関数内で
Test t = new Test;
などとしたとき、tは仮想スタック上に確保されるが、上記の理由によりマイクロスレッドクラスで用意した仮想スタックが解放されるまではスレッドをswitchingしても解放されない。

ａ．ｂ．より、マイクロスレッド動作中には解放されず、動作終了後マイクロスレッド内で用いていたクラスのデストラクタが正しく呼び出されることがわかります。

GCが動作するタイミング

１．GCはnewしたとき(などに)動作する
２．GCは、(トータルで)1M以上のメモリをallocateしてからでないと動作しない。
３．std.gc.fullCollect()も、２．の条件を満たしていないと動作しない。

以上を踏まえて、以下のようなテストクラスを作りました。


class desttest {
	this() {}
	this(int n) { n_ = n; }
	~this() { printf("dest ok! : %d\n",n_); }
private:
	int n_;
}

int main() {
	{
		byte[] ab = new byte[4];
		desttest d = new desttest;
		*cast(desttest*)(&ab[0]) = d;
	}
	{	//	1MB allocしないとGCが動作しない
		for(int i=0;i<10;++i){
		printf("i=%d\n",i);
		a[i] = new byte[100*1024]; // 100kずつ
	}
	//	さらにGCを明示的に呼び出す
	std.gc.fullCollect();
	while (1) { } // 永久ループにして待機する
	return 0;
}

何と、デストラクタは呼び出されませんでした。

・gc.fullCollectを呼び出しているのに
・1MB確保しているところを10Mに変更しても同様

ここで、この理由を説明します。上のプログラムで確保したbyte配列abは、スタック上に存在するのですが、GCは、スタックの現在使用している部分をGCの探索rootとします。

だから、その関数から抜けない限りは、解放されないのです。ただし、スタックの同じ位置を(コンパイラが他の変数のために使用するコードを吐いて)、そこが上書きして潰されれば、結果として解放されることはあります。

また、auto修飾子についても同様です。auto修飾子をつけていれば、その変数がスコープアウトするときにデストラクタが呼び出されると思っている人が多いですが、このGCの原理を理解すればそうでないことは明らかでしょう。

auto修飾子をつけておいて保証されるのは、その関数から抜けるときにデストラクタが呼び出されること(だけ)です。

あえて、（関数から抜ける前の段階で）解放したいのならば


	{
		byte[] ab = new byte[4];
		desttest d = new desttest;
		*cast(desttest*)(&ab[0]) = d;
		*cast(desttest*)(&ab[0]) = null;	//	1.参照を潰した
		ab = null;							//　2.こっちでもok
	}

このようにスコープアウトする前にnullをセットするべきです。もちろんnullをセットしたからと言って解放されるかどうかはGCの都合次第ですが、nullをセットしない限りは関数から抜けるまでは決して解放されないコードが生成されている可能性がある、ということは知っておいたほうが良いでしょう。まあ、普通はそれでも困りはしないので、スタック上にある参照にいちいちnullを放り込む必要はないと思いますが。

GCのスキャン対象から外す

coservativeなGCなので、byte配列すらスキャン対象になるのは前回の実験より明らかです。

となれば、グラフィックや音声データ等を扱うならば1Mとか2Mぐらいのデータをallocすることはしょっちゅうで、こういう風に確保した領域がGCのスキャン対象になると、もの凄くGCに負荷がかかることは容易に想像つきます。

そこで、大容量のバッファを確保するときは(コマ落ちの許されないようなゲームなどでは)必ず、外部のallocatorでallocする必要があるという結論になります。

何故、外部のallocatorでallocしたメモリはGCのcollect対象にはならないかを考えてみましょう。

GCのスキャンですが、byte配列なんかを際限なく辿れば、そこに入っているのはゴミやデータかも知れず、それをアドレスだと思って、その先をアクセスしてしまえば、アクセス違反になります。よって、GCは、自分の割り当てた(自分の管理している)領域以外へは辿りません。

だもんで、mallocのような外部アロケータで割り当てたメモリをvoid*やbyte*に代入しておいたとしても、GCがその先をスキャンすることはありません。

・std.c.mallocで確保したメモリは、GCがスキャンしていないことを確認しました。よって巨大なメモリを扱うときはmalloc～freeを用いれば良いでしょう。

・new byte[8]のようなbyte[]もスキャン対象になっていることは前回のテストで明らかになりましたが、これをvoid*に入れておいたとしてもスキャン対象となっています。おそらく、byte*,void*のようなポイント型はスキャン対象、int型にcastしたところ、スキャンが行なわれなかったようなのでint型はスキャン対象ではないです。

・また、スキャン方法は、4バイト単位での比較。すなわち、
byte[] by = new byte[8];
に対して、
*cast(desttest*)(&ab[4]) = d;
// dはabが解放されるまで解放されない

*cast(desttest*)(&ab[1]) = d;
// dはabが解放されなくても解放されうる
です。

・staticな配列も、同様に、GCのスキャン対象となります。

すなわち、staticな数10MBの配列を確保したならば、それがすべてGCのfullCollectのたびに全スキャンされます。当然、そんなプログラムは非現実的です。

・大きなデータ用の配列は外部のallocatorを用いるか、何らかの方法でGCのスキャン対象とならないようにしておく。

スキャンの対象とならないように、std.gc.removeRootやremoveRangeを使えないかという意見をもらいましたが、使えません。root集合に含まれるのは、「staticデータセグメントと、各スレッドのスタック、そしてレジスタの内容」であって、ここに含まれていない以上、removeは出来ません。（無いものは取り除けない）

これで、GCのスキャンアルゴリズムについては、ほぼ網羅できたはずです。

GCのスキャン対象に含める

D言語[Digital Mars Dの翻訳]のメモリ管理のMark/Releaseのサンプルについて見ておきます。このサンプル、実はいくつかの問題があるので、ここであえて取り上げます。


	import std.c.stdlib;
	import std.outofmemory;

	class Foo
	{
		static void[] buffer;
		static int bufindex;
		static const int bufsize = 100;

		static this()
		{	void *p;

		p = malloc(bufsize);
		if (!p)
			throw new OutOfMemory;
		gc.addRange(p, p + bufsize);
		buffer = p[0 .. bufsize];
		}

		static ~this()
		{
		if (buffer.length)
		{
			gc.removeRange(buffer);
			free(buffer);
			buffer = null;
		}
		}

		new(uint sz)
		{	void *p;

		p = &buffer[bufindex];
		bufindex += sz;
		if (bufindex > buffer.length)
			throw new OutOfMemory;
		return p;
		}

		delete(void* p)
		{
		assert(0);
		}

		static int mark()
		{
		return bufindex;
		}

		static void release(int i)
		{
		bufindex = i;
		}
	}

	void test()
	{
		int m = Foo.mark();
		Foo f1 = new Foo;		// 割り当て
		Foo f2 = new Foo;		// 割り当て
		...
		Foo.release(m);		// f1 と f2 を解放
	}

このソースの一つ目の欠点(bug)は、Foo::releaseで、gcに対してbufferを変更したことを通知していないことです。


	std.gc.removeRange(buffer);
	std.gc.addRange((void*)buffer,(void*)((byte*)buffer + bufindex));

こういうコードが必要です。しかし、これをやったとしても、Fooのデストラクタは呼び出されません。カスタムnewで確保したメモリはdeallocatorも~thisも呼び出されません。それが仕様なのかどうかはわかりませんが、カスタムでnewしている以上、カスタムでdeleteしなさいということなのでしょう。カスタムnewは非常に使いづらいということがわかっていただけるかと思います。

また、先ほど説明したように、GCは1MB以上newしないと動作を開始しないという問題もあります。

それから、std.gc.addRangeでスキャン対象にしたとしても、原則的に外部のallocatorで割り当てたメモリをGCは解放出来るわけではないということもしっかり覚えておいたほうが良いでしょう。メモリやリソースを割り当てる手段は、malloc , VirtualAlloc , HeapAlloc etc..無数にあり、あるポインタを与えられても、それがどの手段で確保されたメモリなのかGCが判別することは出来ないからです。

よって、
・GCが解放するのは、GCが自分で確保したメモリのみ
・GCがスキャンするのは、原則、GCが自分で確保したメモリ + std.gc.addRange で指定された範囲のメモリのみ
です。

conservativeなGCという意味

GCは、スタックフレームのレイアウトを知る手段はありません。これはすなわち、GCは、どれがポインタなのか、どれがデータなのかわからずにスキャンして行かなくてはならないことを意味します。

きちんと型情報を持つようにすれば、GCのスキャンの量は減るのですが、スタックに参照を置くのにいちいち型情報をつけていたのでは、処理速度に響くので、このへんは現在の現実的な実装だと思いますし、現在のDMDコンパイラのGCも、conservativeなものになっています。（ただし、D言語の仕様上は、GCの実装までは定めていません。）

いま、GCがconservativeだとして話を進めます。

この場合、スタック上に置かれたbyte[]もbyte*もGCからは区別がつかないということです。ポインタのみをGCはスキャンすると言いましたが、区別が付かない以上、ポインタのみをスキャンするということは出来ません。何でもスキャンします。

また、メンバの変数についても同様で、どれとどれがGCが辿らなくてはならないポインタであるかをどこにも保持していない以上、GCはすべてをスキャンします。これは、vtableの指すクラス情報のところに、これとこれはスキャンしない、ということを書くことは可能なので、将来的にどうなるかはわかりませんが、現状、何でもスキャンしているようです。

あと、staticなデータは、事前に型が決定するので、ポインタ型以外はGCのスキャンのroot集合のなかに含まれません。


static byte[8] ab;	//	これはGCのscan対象ではない

int main() {
	{
		desttest d = new desttest(2);
		*cast(desttest*)(&ab[4]) = d;
	}
	// ...何か処理。この場合、dは解放されうる
	return 0;
}

GC対策あれこれ

コマ落ちが許されない状況ではnewしなければGCが動作しないので、事前にnewしてpoolしておくのは常道なのですが、それにしても一切のnewを使ってはいけないとなると、これは本当にオブジェクト指向なんかいな？というプログラムになってきます。

ついでに言えば、スレッドを別にまわしてあるとすると、そのスレッドがnewを行なえば、GCが動作するわけで、他スレッド全部に迷惑がかかります。雑用的なスレッド内でも一切のnewは禁止．．となると、かなり辛いことになりそうです。

そこまでストイックにならなくても良いのでしょうか？

一応、最低限の指針としては、こうでしょう。

・ゲーム中には、なるべくnewしない、オブジェクトは事前にpoolしておく
・大きなメモリ割り当てには外部のallocatorを用いる。(例:std.c.malloc)

あと、まあ、std.gc.disable()でGCを禁止して良いのかは議論の分かれるところです。

gcを停止させると、その間、全スレッドでメモリリークし放題の状態になるわけで、1秒間に100kBほどリークし続ければ10分で60MBほどリークすることになります。これが許せるか、ということになりそうです。

deleteを用いてプログラミングする

また、GCを禁止しておいて、明示的にdeleteを呼び出してデストラクタを呼び出せばどうか、と言う質問を受けました。そういうスタイルのプログラムになることもあると思います。ただ、

１．deleteを呼び出すのでは、GCつきの言語のプログラミングとしてどうかというのはあります。普通はdeleteは書かないでしょうし、他の人のプログラムを流用するときも、そうなっているでしょう。

２．deleteが保証するのは、デストラクタの呼び出しだけであって、そのメモリの解放は行ないません。すなわち、メモリ解放の目的でdeleteを呼び出しても何の意味もないということです。

つまり、GC動作を禁止して、deleteをいくらC++っぽく書いて行ってもメモリリークしまくりです。GCのヒープから確保したメモリ(普通、newをoverrodeしていなければ、newで確保されるメモリはこれに相当する)は、GCが動作しないと解放されることはありません。また、クラスのデストラクタのコードには、ディフォルトでは他のメンバを解放するようなコードは一切含まれていません。GC付きの言語なので、無駄なことはせず、そのへんはGCに頼るコードを生成してあるのが普通です。よって、deleteをしたところで、そのクラスのメンバのデストラクタの呼び出しも保証されません。

よって、deleteをするようなコードは、現実的ではないのです。


Hoge h1 = new Hoge;
Hoge h2 = h1;
delete h1;

このあと、h2はh1の指していたオブジェクトを指します。h1はdeleteした瞬間にnullを指すようになります。h2の値はh1をdeleteしたところで変化しません。(通知しないということです)　このへんboost::weak_ptrと同じように思っていると痛い目を見ます。

そんなわけで、上記のプログラムの場合、delete後にh2.someMember();というようにメンバにアクセスするとアクセス違反になります。これは、通知するメカニズムがない以上、どうしようもありません。(アクセス違反になるのは、おかしい気もしますが、解析したところ、どうもdeleteしたときにvtableへのポインタを潰しているようです。これは、vtableを指すままにしておくとGCによる無駄なスキャンが発生するのでそれを回避するためじゃないかと思います。)

何にせよ、よほどクリティカルな部分以外、deleteを使うのはお勧めしません。

とは言え、例外が発生した場合など、スタックの巻き戻しに際して、そこに至るまでのオブジェクトのデストラクタを呼び出して欲しいと思うことは多々あるのですが．．。

GCの細かい制御

一切newを行なってはいけないとしたら、事前にある程度のメモリを確保して、それをプールして使うことも考えられます。

例)
static byte[1024*1024*50] work; // 50MB

このあと、この領域は、std.gc.removeRootでスキャン対象から外しておけば、ここからメモリを使用する限りはGCは動作しないというわけです。ところが、カスタムnewが非常に使いづらいことは先ほど説明した通りです。

また、32M以上のstaticセグメントは作れません。（linkerが落ちます）　これが、仕様なのかどうかは知りませんが、まあそんな非常識なことはしないので別に構わないでしょう。

あまり知られてはいませんが、GCのヒープに指定したバイト数だけ事前にpoolさせることが出来ます。そのpoolが、あるうちは、GCは動作しません。

その方法は、至って簡単です。


{
	byte [] a = new [1024*1024*10];
	delete a;
}

こう書いておけば10M+1MをnewするまではfullCollectは呼び出されないはずです。なぜなら、GCは一度確保したメモリ分は自分のヒープにpoolするからです。これを割るまではfullCollectしない限り、GCは動きません。(逆に、std.gc.minimize()を呼び出せば、このため込んでいる10Mを吐き出します。)

ゲームにおけるGC対策の現実解

この章のことを総合すれば、以下のようになります。

１．GCは禁止しない。（禁止してしまうと本当にメモリが足りなくなったときにどうしようもなくなる）
２．deleteはどうしようもない場合以外は使用しない。
３．カスタムnewは、なるべく用いない。（クラスとしての汎用性が下がるため）
４．コマ落ちして困る部分に突入する前に、そこで使用するメモリ最大量をnewしてdeleteしておく。（GCのヒープにpoolするため）
５．コマ落ちして困る部分では、なるべくnewせずに、事前にnewしておいたものをpoolから取り出して使うようにする。(newさえしなけばGCは動作しないので)
６．ひと休みのタイミング(ステージクリアとか)でstd.gc.fullCollectを呼び出す。場合によっては、std.gc.minimizeを呼び出す。（GCに仕事をさせてあげないとメモリは逼迫する一方なので）
７．大きなメモリが必要な時は必ず外部のallocatorを用いて確保する。(GCがスキャンする時間も馬鹿にならないため)

D言語研究室