ガベージコレクション

**ガベージコレクション**（、**GC**）とは、コンピュータプログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。1959年ごろ、LISPにおける問題を解決するためジョン・マッカーシーによって発明された。

メモリの断片化を解消する機能は**コンパクション**（）と呼ばれ、実現方法によってはガベージコレクションと共にコンパクションも行う仕組みになっている。そのためコンパクションを含めてガベージコレクションと呼ぶ場合もあるが、厳密には区別される。

また、ガベージコレクションを行う主体は**ガベージコレクタ**（）と呼ばれる。ガベージコレクタはタスクやスレッドとして実装される場合が多い。

「ガベージコレクション」を直訳すれば「ゴミ集め」「ごみ拾い」となる。JISでは「廃品回収」や「ゴミ集め」などという直訳が割り当てられている規格もあるが、一般的な意味での「ゴミ集め」と紛らわしく、プログラミングの分野ではかえって意味が通じなくなるため、ごく一部の学会誌や論文などを除き、実際に使われることはほとんどなく、外来語として各種カナ表記やGCという略記が使われることが一般的である。

## 動作
従来のメモリ管理では、プログラマがプログラムの実行中においてメモリが必要となる期間を考え、必要となった時点でメモリを確保するコードを記述し、不要となった時点で解放するコードを記述していた。

ガベージコレクションを使用する場合、メモリを確保するコードはプログラマが明示的に記述するが、メモリの解放については明示的に記述する必要がなく、ガベージコレクタが不要と判断した時に、自動的にメモリを解放する。確保したメモリが不要かどうかは、プログラムが今後そのメモリにアクセスするかどうかで決まり、スタックや変数テーブルなどから参照をたどってメモリに到達可能かどうかによって判断される。

ガベージコレクションの機能は、初めからプログラミング言語の言語機能や言語処理系あるいはフレームワークに組み込まれている場合や、外部ライブラリなどによって提供される場合がある。

## 特徴
ガベージコレクションはプログラマが明示的にメモリの解放を行う必要が無いため、以下に示すメモリ管理に関連する陥りやすいバグを回避することができる。

;メモリリークの回避
:ガベージコレクションは、オブジェクト（データを格納したメモリ領域）とそれを指し示すポインタを管理するため、オブジェクトは存在しているがそれを指すポインタが無い状態を回避することができる。
;オブジェクトの二重解放の回避
:いったん解放したオブジェクトをさらに解放することを防ぐ。
;無効なポインタの回避
:例えば、メモリを動的に割り当てるサブルーチン（C言語の`[[malloc]]`関数やPascalの`New`手続きなど）で確保したメモリ領域を指すポインタだったが、メモリを解放するサブルーチン（C言語の`free`関数やPascalの`Dispose`手続きなど）に渡し解放した直後のポインタや、サブルーチン内の自動変数（非静的なローカル変数）のアドレスを指すポインタだったが、戻り値などによって誤ってサブルーチンの呼び出し元に返却されてしまったポインタ、などが該当する。これらのポインタにはあるアドレスが代入されているが、そのアドレスには有効なオブジェクトがすでに存在せず、ポインタは無効なメモリアドレスを指している。このような無効なポインタをダングリング・ポインタ (dangling pointer) といい、ガベージコレクションはこの問題を回避する。

ただしガベージコレクションにおいても、今後使用することのないオブジェクトへのポインタをいつまでも保持しているようなコードでは、いつまでもオブジェクトが解放されず、メモリ不足を起こしてしまう。これは論理的な設計の問題であり、ガベージコレクションを持つ処理系においてもこの種のメモリリークは発生する。

メモリ管理に関するバグを回避する以外に、プログラミングスタイルの選択肢を広げる効果も持つ。型変換などのために一時的なオブジェクトを生成する、マルチスレッドを利用したプログラムでスレッド間でオブジェクトを共有して使用する、といった処理はメモリ確保・解放の処理の記述が煩雑となることが多い。しかし、ガベージコレクションを持つ言語処理系においては煩雑な記述を省略することができ、これらの処理をより自然に記述することができる。

多くの実装では、入れ違いにより誤って到達可能なメモリが不可能と判断されないように、ガベージコレクトが開始されると他の処理を止め、本処理が中断される（Stop-the-world ガベージコレクタ）。CPUを長時間（数百ミリ秒から数十秒）占有することもある。ガベージコレクションの動作タイミングの予測やCPUの占有時間の事前予測などが困難なことから、デッドラインが決められているリアルタイムシステムに使用することは難しい。リアルタイム性を改善したGCとして、インクリメンタルGCやコンカレントGCがある。

ガベージコレクタはプログラムであるため、これを実現するコードが必要になる。これをプロセス単位で組み込まなくてはならない。ガベージコレクタは対象のプロセスが終了するまで余分にメモリを占有し続けるため、メモリ容量が小さな機器には不向きであるか、全く使えない。

## 実装
ガベージコレクションは、Javaのように言語仕様および言語処理系（ランタイム）に標準的に組み込まれたものを透過的に利用する形態がほとんどである。しかし、C言語やC++のように言語仕様および言語処理系には存在していなくとも、あるいは各種スマートポインタのようなライブラリとして実装されたものを利用することもできる。

ガベージコレクションは、プログラム本来の動作とは別に時間のかかる処理である。そこで、ガベージコレクションには本来のプログラムの動作に対して影響が少ないことが求められる。

一般に、デスクトップアプリケーションでは、応答時間を短くするため、ガベージコレクションによるプログラムの停止時間を最小にすることが要求される。また、サーバアプリケーションでは、応答時間よりもスループットを求められることが多く、ガベージコレクションにもスループット性能が高いものが求められる。さらに、機器組み込みアプリケーションでは、機器に搭載されるCPUの能力の低さやメモリ容量の小ささから、リソース消費が小さいものが求められる。また、リアルタイムシステムでは、プログラム動作時間のばらつきを最小にしたいという要求もある。

これらの要求をすべて満たすようなアルゴリズムは存在しないため、さまざまな手法が提案されている。代表的なガベージコレクションアルゴリズムには、以下のものがある。

;参照カウント
:オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。
;マーク・アンド・スイープ
:オブジェクトから別のオブジェクトへの参照をたどり、到達できないオブジェクトを破棄する方法。
;コピーGC
:通常使用するメモリ領域と同じ容量のメモリ領域をもうひとつ用意し、ガベージコレクションの際に有効なオブジェクトのみをもう一方のメモリ領域にコピーする方法。メモリ領域をデータ保持に必要な容量の2倍消費すること、コピーの際にオブジェクトのアドレスが変更されることなどの欠点があるが、ガベージコレクションとコンパクションが同時に行える利点がある。

これらのアルゴリズムは複合して使用することもあり、世代別ガベージコレクションではコピーGCとマーク・アンド・スイープの両方のアルゴリズムを使用している。

また、アプリケーション動作への影響の観点から、アプリケーション動作をすべて止める**ストップ・ザ・ワールド方式**と、アプリケーション動作と並行して動作する**コンカレント方式**に分類することができる。

## 言語による利用可能性
一般論として、高レベルな言語ほどガベージコレクションを言語の標準機能として備えていることが多い。言語に組み込まれていない場合でも、C言語/C++向けのやスマートポインタのように、非標準または標準のライブラリとして実装されていることもある。ただしライブラリベースのアプローチは、オブジェクトの生成と破棄のメカニズムを変更する必要があるなど、欠点もある。

MLやHaskell、APLなどの関数型言語の多くはガベージコレクションが組み込まれている。特に、関数型言語の先駆けとなったLISPは最初にガベージコレクションを取り入れた言語でもある。

LuaやRubyなどといった動的言語も、ガベージコレクションを備えていることが多い（ただしPerl 5やPHP 5.2以前には参照カウント方式のものしかない）。Smalltalk、Java、ECMAScript（JavaScript）のようなオブジェクト指向言語には、たいていガベージコレクションが組み込まれている。C#やVisual Basic .NETなどの.NET言語は.NET Framework/.NET Compact Framework/Mono/.NETといった実行環境下において、実装形態に差はあれどいずれもガベージコレクションを利用可能である。特筆すべき例外はC++とDelphiで、それらはデストラクタがその代わりとなっている。

RustはGCを持たないが、所有権に基づいてメモリを管理する。RustではC++のようにデストラクタを定義することもでき、また参照カウントベースのスマートポインタを標準的に利用することもできる。

古典的なBASICインタープリタ（、など）においてもガベージコレクションが備えられており、文字列の連結操作の結果使われなくなった領域を再度BASICが使えるようにする処理が行われた。その処理の間、BASICがフリーズしたかのようになることから、ガベージコレクションが発生しないようにする方法として、文字列の連結を極力行わず、最大文字数が格納できる領域を持った文字列変数に対して `MID$`、`LEFT$`、`RIGHT$` 関数を使用することで代用することが推奨されていた。

Objective-Cには参照カウントベースのオブジェクト寿命管理機能が組み込まれており、元々ガベージコレクションはなかったが、AppleのObjective-C 2.0では、Mac OS X 10.5以降に限り保守的な世代別GCベースのランタイムコレクタが使用可能である。ただしiOSではこのGCを利用できない。なお、macOSに関しても、`NSGarbageCollector`はOS X 10.8から廃止予定扱いとなり、SDK 10.10を最後に廃止されており、またOS X 10.11を最後にこのGCは搭載されなくなり、macOS 10.12で廃止された。2015年5月以降、Mac App Storeで新規登録／更新されるアプリはGCを使えなくなっている。代替として、自動参照カウント (Automatic Reference Counting; ARC) によるメモリ管理が推奨されている。SwiftもARCを採用している。一方で、GNUstepはBoehm GCを使用している。

Pythonは主に参照カウント方式のガベージコレクションを用いているが、補助的に（伝統的なマーク＆スイープとは逆順の探索アルゴリズムによる）世代別GCを併用している。

C++/CLIでは、`gcnew`で生成したCLIオブジェクトは.NET Frameworkのガベージコレクションにより管理される。

では、`ref new`で生成したWindowsランタイムオブジェクトはCOMベースの参照カウントにより管理される。

## ライブラリ
* Boehm-Demers-Weiser conservative garbage collector (Boehm GC) - C/C++向け。マーク・アンド・スイープ。

### スマートポインタ
なお、C言語で参照カウント方式のガベージコレクションを利用する場合、通常煩雑なコーディングを必要とするが、C++では以下のようなRAIIを活用したを利用することで緩和できる。
* Boost C++ライブラリの`boost::shared_ptr`および`boost::shared_array`。
** 参照カウントの増減処理をカスタマイズできる`boost::intrusive_ptr`もある。
* C++11以降の`std::shared_ptr`
* Active Template Libraryの`ATL::CComPtr` - COMオブジェクトのスマートポインタ。
* Windows Runtime Libraryの`Microsoft::WRL::ComPtr` - Windowsランタイムオブジェクトのスマートポインタ。COMオブジェクトにも使用可能。

## 分散ガベージコレクション
分散コンピューティング環境では、あるホスト内のオブジェクトだけではなく、リモートホスト上に存在するオブジェクトとメッセージのやり取りが行われることがある。このような環境においてローカルなガベージコレクションと同様、不要なオブジェクトを破棄する手法が分散ガベージコレクションである。リモートホストからの参照状態の検出、通信が切れた場合の処理などローカルホストのガベージコレクションとは異なる課題を解決する必要がある。

## 世代別ガベージコレクション

従来のGCは、対象となるメモリ領域がいっぱいになった時に一気にGCを行なうものであり、この方法では、メモリ領域のサイズが大きくなるに従い、GC時間が長くなっていく欠点がある。この問題に対処するために世代別ガベージコレクションが考案された。
世代別GCでは新領域と古い領域にメモリ領域が分けられ、新規に作成されたオブジェクトは、新領域に配置され、新領域がいっぱいになった時点で、新領域内部だけのGCが走る。このGCはメモリ全体に対するGCに比べると当然のことながら低負荷・高速になる。新領域に対するGCを一定回数生き残ったオブジェクトは、古領域に移動し、古領域がいっぱいになった時に、初めて全てのメモリ領域を対象とするFULL GCが行われる。

## SSDにおけるガベージコレクション

## 脚注

### 注釈

### 出典

## 参考文献
* 
* 

## 関連項目
* 動的メモリ確保
* 弱い参照