garbage.dd

Ddoc

$(SPEC_S ガベージコレクション,

	$(P D は完全にガベージコレクトされた言語です。
	つまり、メモリを解放する必要は
	全く必要ありません。必要なだけ確保して、あとはガベージコレクタが定期的に
	使われていないメモリをプールへ戻します。
	)

	$(P C/C++ プログラマは明示的なメモリ確保と解放に慣れていて、
	ガベージコレクタの効率や利点については懐疑的なようです。
	私は、
	一からガベージコレクションを念頭に置いて書いたプロジェクトと、
	既存のプロジェクトを
	GC を使うように方向転換した経験のどちらも持っていますが：
	)

	$(UL

	$(LI ガベージコレクトされたプログラムの方が高速です。
		これは直感に反するかもしれませんが、その理由は：

	$(UL
	    $(LI 明示的なメモリ管理の際によく使われる手法は、参照カウントです。
		代入があるたびにカウントを増やしたり減らしたリソースを挿入するのは、
		速度低下の原因になっています。スマートポインタクラスでラップしても、
		速度的な解決にはなりません。（またいずれにせよ、
		循環参照を削除できない参照カウント方式は、
		一般的な解決策ではありません。）
	    )

	    $(LI オブジェクトによって獲得されたリソースの解放には、
		デストラクタが使用されます。多くのクラスでは、このリソースとは
		割り当てられたメモリのことです。GCを使えば、
		ほとんどのデストラクタが空になり、完全に削除してしまえます。
	    )

	    $(LI メモリ管理のためのデストラクタは、
		オブジェクトがスタックに置かれたときに影響が顕著になります。
		例外が発生したときに、全てのスタックフレームでデストラクタが呼び出され、
		メモリを解放するような仕組みが必要となるのです。
		もしデストラクタが関係しなければ、例外を処理する特別なスタックフレームを
		設定する必要がなくなり、コードは高速に実行されます。
	    )

	    $(LI メモリ管理に必要なコードは全てを合わせるとちょっとした量になります。
		大きなプログラムになるほど、キャッシュに入らない部分が増え、
		ページングが多く発生し、
		プログラムが遅くなります。
	    )

	    $(LI GCは、メモリが残り少なくなってきたときのみ実行されます。
		メモリに余裕があれば、プログラムは全速力で実行され、
		メモリ解放に一切時間を取られません。
	    )

	    $(LI モダンなGCは、過去の遅いものより遙かに発展しています。
		世代型のコピーGCには、
		昔のマーク＆スイープアルゴリズムの非効率さはありません。
	    )

	    $(LI モダンなGCはヒープの詰め直しを行います。
		これによってプログラムが活発に参照するページの数を減らし、
		キャッシュヒット率を高め、
		スワップ回数が減ります。
	    )

	    $(LI GCを使うプログラムは、メモリリークの積み重ねで次第にパフォーマンスが悪化、
		という事態に縁がありません。
	    )
	)
	)

	$(LI GCは未使用のメモリを再利用しますから、長時間実行するプログラムが
	システムを落とすまでじわじわとメモリを食いつぶす、
	いわゆる"メモリリーク"に陥ることがありません。
	GC付プログラムは長時間の安定性があります。
	)

	$(LI GCを使うプログラムには、ポインタ周りの見つけにくいバグがほとんど存在しません。
	既に解放されてしまったメモリを指す参照が存在しないからです。
	メモリを明示管理するコードが必要ないので、そのようなコードかが生むバグもありません。
	)

	$(LI GC付きプログラムは、開発もデバッグも高速です。
	何故なら、メモリ管理のコードを開発する必要もデバッグする必要もテストする必要も、
	管理する必要もありませんから。
	)

	$(LI GC付きプログラムは、有意に小さくなります。
	メモリ解放を管理するコードや、
	メモリを解放するための例外ハンドラが不要になるためです。
	)
	)

	$(P ガベージコレクションは万能薬ではありません。欠点もあります：
	)

	$(UL

	$(LI いつメモリ回収が動くかが予測できません。
	その結果、任意の時点でプログラムの動作が停止しえます。
	)

	$(LI メモリ回収にかかる時間に上限がありません。
	実際には非常に高速に動作しますが、保証はされません。
	)

	$(LI メモリ回収時は、
	他のスレッドが全て停止しなくてはなりません。
	)

	$(LI GCは、
	明示的な解放ルーチンなら解放するメモリを保持し続けることがあります。
	実際には、これは大きな問題ではありません。
	というのは、明示的な解放ルーチンには大抵メモリリークがあって
	余分なメモリが解放されずに残りますし、明示的ルーチンの方もいずれにせよ、
	普通は解放されたメモリをOSに返すことはしません。
	代わりに内部のプールに保持するのが一般的です。
	)

	$(LI GCは、
	OSのカーネルサービスとして実装されるべきなのです。
	しかし現実にはそうではないので、GC付プログラムは、
	GCの実装をプログラムに付属させる必要があります。これは共有 DLL
	にすることは可能ですが、それにしてもまだそのDLLが必要になります。
	)
	)

	$(P これらの制約に対するテクニックについては、
	$(DPLLINK memory.html, メモリ管理) の項で概要を述べています。
	)

<h2>ガベージコレクションの動作について</h2>

	$(P GCは次のステップで動作しています:)

	$(OL
	$(LI GCで確保された領域を指す $(SINGLEQUOTE roots) ポインタを全て列挙します。)

	$(LI rootから指されている領域内から、
	再帰的にGCメモリ領域内を指しているポインタを探索します。)

	$(LI GCで割り当てられた領域のうち、
	生きたポインタで指されていないことが分かった領域を全て解放します。)

	$(LI 残ったメモリ領域のデータをコピーして使用領域をまとめる処理
	 (コピーGCと呼ばれます) が実行される可能性があります。)
	)

<h2>GCの管理下にあるオブジェクトと外部コードとの接続</h2>

	$(P GCは、以下の領域を探索の出発点(root)とします:)
	$(OL
	$(LI staticデータセグメント)
	$(LI 各スレッドのスタック)
	$(LI std.gc.addRoot() か std.gc.addRange() で追加された領域)
	)

	$(P もしこの他に出発点とすべきオブジェクトが存在していたとしても、
	コレクタはそのオブジェクトを発見できず、
	メモリを解放してしまいます。
	)

	$(P これが起きるのを避けるには、)

	$(UL
	$(LI 出発点から探索できる領域に、
	オブジェクトへの参照を置いておく。)

	$(LI オブジェクトを std.gc.addRoot() か std.gc.addRange() でrootに追加しておく。)

	$(LI オブジェクト用のメモリを、
	外部のアロケータかCのライブラリ関数
	malloc/free を使って明示的に再確保しておく。
	)
	)

<h2>ポインタとGC</h2>

	$(P Dでのポインタは、大きく分けて二種類に分類できます：一つは、
	ガベージコレクタで管理されたメモリを指すもの、もう一つは、そうでないものです。
	後者の例としては、C の malloc() を呼んで作られたポインタや、
	C のライブラリが返すポインタ、
	あるいは静的データやスタックへのポインタなどがあります。
	これらのポインタに対しては、Cで合法な操作は全て実行できます。
	)

	$(P しかしながら、
	ガベージコレクタに管理されたポインタと参照には、
	幾つかの制限があります。大きな制限ではありませんが、
	ガベージコレクタの設計に最大限の柔軟性を与えるために課されています。
	)

	$(P 未定義な動作：)

	$(UL

	$(LI "xorポインタ-リンクリスト"技のように、
	ポインタに他の値を xor することはできません
	)

	$(LI 二つのポインタを交換するのにxorトリックを使うことはできません
	)

	$(LI キャストやその他の技を使って、
	ポインタを非ポインタ変数へ格納することはできません

------
void* p;
...
int x = cast(int)p;   // エラー： 未定義動作
------

	ガベージコレクタは、ルートにある非ポインタ型は探索の対象としません。
	)

	$(LI アラインメントが行われることを利用して、
	ポインタの下位ビットにビット値を格納することはできません：

------
p = cast(void*)(cast(int)p | 1);  // エラー： 未定義動作
------
	)

	$(LI ガベージコレクタ管理域を指すかもしれない整数値を、
	ポインタ変数に格納することはできません。

------
p = cast(void*)12345678;   // エラー： 未定義動作
------

	コピーGCが値を変更する可能性があります。
	)

	$(LI $(D null) 以外のマジックナンバーをポインタに入れてはなりません。
	)

	$(LI ポインタ値をディスクに書き出したり、
	読み戻したりすることはできません。
	)

	$(LI ポインタの値をハッシュ値の計算に使用することはできません。
	コピーGCアルゴリズムを使ったガベージコレクタは、
	オブジェクトをメモリ上の任意の位置に再配置することがあり、
	この時計算されたハッシュ値は無効になります。
	)

	$(LI ポインタの順序付けに依存することはできません：

------
if (p1 < p2)  // エラー： 未定義動作
  ...
------
	繰り返しになりますが、ガベージコレクタは、
	オブジェクトをメモリ上で移動するかもしれません。
	)

	$(LI D元々確保された範囲の外に出るような、
	ポインタに対する
	オフセットの加減算を行うことはできません。

------
char* p = new char[10];
char* q = p + 6; // ok
q = p + 11;      // エラー： 未定義動作
q = p - 1;       // エラー： 未定義動作
------
	)

	$(LI GCヒープを指す可能性があるポインタ変数を、
	境界整列されていない位置に置くことはできません：

------
align (1) struct Foo {
  byte b;
  char* p;  // 境界整列されていないポインタ
}
------

	境界整列されていないポインタは、実行環境のハードウェアがそれをサポートしている場合
	$(B かつ) そのポインタがGCヒープを決して指さない場合にのみ
	使うことが出来ます。
	)

	$(LI ポインタ値をbyte毎byte毎のメモリコピーで複製することはできません。
	この方法は、有効なポインタでない中間状態を作り出すことになるので、
	そのような状態でGCがスレッドを停止すると、
	メモリが破壊されることがあります。
	ほとんどの $(D memcpy()) の実装にはこの問題はありません。
	内部のコピーの実装では、ポインタサイズと同等かそれ以上のサイズの整列した
	まとまり単位でコピーを行っているためです。しかし、その種の実装が
	Cの標準規格で保証されているわけではありませんから、
	$(D memcpy()) は十分に注意して使う必要があります。
	)

	$(LI 構造体のメンバとして、自分自身を指すポインタを持ってはいけません。
	これの問題点は、インスタンスがメモリ上で移動されたときに、
	ポインタが移動前のインスタンスを指してしまい、
	悲惨な結果になり得ることです。
	)

	)

	$(P 保証されている、実行してもよいこと：)

	$(UL

	$(LI 共用体を使ってポインタのメモリ領域を他の変数と共有すること：

------
union U { void* ptr; int value }
------
	)

	$(LI オブジェクト内部へのポインタが存在するならば、
		オブジェクト先頭へのポインタを保持しておく必要はありません。

------
char[] p = new char[10];
char[] q = p[3..6];
// q さえあれば、オブジェクト全体が生存しているとみなされます。
// p を同時に保持する必要はありません。
------
	)
	)

	$(P 実際のところ、
	ほとんどの場合はポインタを使わずに済みます。
	Dは大抵のポインタの使い道に置き換わる機能を用意しています。
	例えばオブジェクトへの参照、動的配列、
	そしてガベージコレクションです。
	ポインタは、CのAPIとのインターフェイスとして使うためと、
	あとは低レベル処理のために用意されているものです。
	)

<h2>GCとうまくやって行くには</h2>

	$(P ガベージコレクションは、
	メモリ解放に関する全ての問題を解決するわけではありません。
	例えば、巨大なデータ構造へのアクセスルートが生きていれば、
	例え実際には二度と参照されないとしても、GCはその領域を再利用できません。
	この問題を回避するには、必要ないオブジェクトへの参照やポインタにはnullを
	セットしておく、というのが良い習慣です。
	)

	$(P このアドバイスは、staticな参照かオブジェクトに埋め込まれた参照にのみ当てはまります。
	スタック上の参照にnullを代入するのにはあまり意味はありません。
	いずれ新しいスタックフレームで書き潰される領域なので、
	GCはスタックトップより先は見に行きませんから。
	)

<h2>オブジェクトのピン留めとMove GC</h2>

	$(P 現在の D の実装は move GC を採用していませんが、
	上に上げた規則を守っていれば move GC の実装も可能です。
	オブジェクトをピン留めするのに特別な処理は必要ありません。Move GC は、
	あいまいな参照がなく、その参照を更新可能なオブジェクトだけを移動します。
	そのほかのオブジェクトは自動的にアドレスが固定されます。
	)

<h2>GC を使う D の操作</h2>

	$(P コードの一部で、GCの起動を避けたいことがあるかもしれません。
	以下が、GCによりメモリ割り当てを行う言語要素の一覧です:
	)

	$(UL
	$(LI $(GLINK2 expression, NewExpression))
	$(LI 配列の要素追加)
	$(LI 配列の結合)
	$(LI 配列リテラル (静的初期化子として使われた場合は除く))
	$(LI 連想配列リテラル)
	$(LI 連想配列への挿入、削除、検索の全て)
	$(LI 連想配列からのキーや値の取り出し)
	$(V2
	$(LI 外のスコープの変数にアクセスするネスト関数のアドレスを取る (つまり delegate) 
	 操作)
	$(LI 外のスコープの変数にアクセスする関数リテラル)
	)
	$(LI 失敗する $(GLINK2 expression, AssertExpression))
	)

<h2>参考文献</h2>

	$(UL
	$(LI $(LINK2 http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29, Wikipedia))
	$(LI $(LINK2 http://www.iecc.com/gclist/GC-faq.html, GC FAQ))
	$(LI $(LINK2 ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps, Uniprocessor Garbage Collector Techniques))
	$(LI $(AMAZONLINK 0471941484, Garbage Collection : Algorithms for Automatic Dynamic Memory Management))
	)

)

Macros:
	TITLE=ガベージコレクション
	WIKI=Garbage
	CATEGORY_SPEC=$0