「ガベージコレクション」の版間の差分

削除された内容追加された内容

インライン

2021年5月20日 (木) 22:56時点における版

ガベージコレクション^{[注釈 1]}（英: garbage collection; GC）とは、コンピュータプログラムが動的に確保したメモリ領域のうち、不要になった領域を自動的に解放する機能である。廃品回収^[1]やゴミ集め^[2]^[3]などの訳もある。1959年ごろ、LISPにおける問題を解決するためジョン・マッカーシーによって発明された^[4]^[5]。

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

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

動作

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

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

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

特徴

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

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

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

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

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

実装

ガベージコレクションは、Javaのように言語処理系に組み込まれたものと、C言語のように言語処理系には存在しないがライブラリを使用することで実現できるものがある。

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

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

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

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

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

また、アプリケーション動作への影響の観点から、アプリケーション動作をすべて止めるStop the world方式と、アプリケーション動作と並行して動作するコンカレント方式に分類することができる^[6]。

言語による利用可能性

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

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

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

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

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

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

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

C++/CX（英語版）では、ref newで生成したWindowsランタイムオブジェクトはCOMベースの参照カウントにより管理される。

ライブラリ

Boehm-Demers-Weiser conservative garbage collector - 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におけるガベージコレクション

→詳細は「ライトアンプリフィケーション § SSDにおけるガベージコレクション(GC)」を参照

脚注

[脚注の使い方]

注釈

^ カナ表記には「ガベージ・コレクション」のほかに、「ガーベッジ・コレクション」や「ガーベジ・コレクション」などもある。

出典

^ JISX3002 2011.
^ JISX3015 2008.
^ 田浦 2000.
^ Recursive functions of symbolic expressions and their computation by machine, Part I
^ RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998)
^ “古典的Javaガベージコレクションを理解する”. 2020年9月15日閲覧。
^ “メモリ管理を理解する（後編） (2/2)：Cocoaの素、Objective-Cを知ろう（8） - ＠IT”. 2019年2月14日閲覧。
^ “NSGarbageCollector - Foundation | Apple Developer Documentation” (英語). 2019年2月14日閲覧。
^ “Xcode Release Notes | Xcode 8.3” (英語). 2019年2月14日閲覧。
^ “Apple Warns Developers Garbage Collection is Dead, Move to ARC – The Mac Observer” (英語). 2019年2月14日閲覧。
^ “29.11. gc — ガベージコレクタインターフェース — Python 3.6.5 ドキュメント”. 2019年2月10日閲覧。
^ “Garbage Collection for Python” (英語). 2019年2月10日閲覧。

参考文献

JIS X 3002:2011「電子計算機プログラム言語COBOL」（日本産業標準調査会、経済産業省）
JIS X 3015:2008「プログラム言語C#」（日本産業標準調査会、経済産業省）
田浦健次朗、米澤明憲「分散記憶並列計算機における局所ごみ集めのスケジュール方式について」『情報処理学会論文誌』第41巻第5号、情報処理学会、2000年5月15日、1490 - 1499頁、ISSN 1882-7764、2021年5月9日閲覧。

@@ 57行目: / 57行目: @@
 古典的な[[BASIC]]インタープリタ(N88-BASIC, F-BASICなど)においてもガベージコレクションが備えられており、文字列の連結操作の結果使われなくなった領域を再度BASICが使えるようにする処理が行われた。その処理の間、BASICがフリーズしたかのようになることから、ガベージコレクションが発生しないようにする方法として、文字列の連結を極力行わず、最大文字数が格納できる領域を持った文字列変数に対してMID$(),LEFT$(),RIGHT$()関数を使用することで代用することが推奨されていた。
-[[Objective-C]]には参照カウントベースのオブジェクト寿命管理機能が組み込まれており、元々ガベージコレクションはなかったが、[[Apple]]のObjective-C 2.0では、[[Mac OS X 10.5]]以降に限り<ref>{{Cite web|url=https://www.atmarkit.co.jp/ait/articles/0908/05/news096_2.html |title=メモリ管理を理解する（後編） (2/2)：Cocoaの素、Objective-Cを知ろう（8） - ＠IT |accessdate=2019-02-14}}</ref>保守的な世代別GCベースのランタイムコレクタが使用可能である。ただし[[iOS (アップル)|iOS]]ではこのGCを利用できない。なお、[[macOS]]に関しても、<code>NSGarbageCollector</code>は[[OS X Mountain Lion|OS X 10.8]]から廃止予定扱いとなり、SDK 10.10を最後に廃止されており<ref>{{Cite web|url=https://developer.apple.com/documentation/foundation/nsgarbagecollector?language=occ |title=NSGarbageCollector - Foundation {{!}} Apple Developer Documentation |language=en |accessdate=2019-02-14}}</ref>、また[[OS X El Capitan|OS X 10.11]]を最後に<ref>{{Cite web|url=https://developer.apple.com/library/archive/releasenotes/DeveloperTools/RN-Xcode/Chapters/Introduction.html#//apple_ref/doc/uid/TP40001051-CH1-SW160 |title=Xcode Release Notes {{!}} Xcode 8.3 |language=en |accessdate=2019-02-14}}</ref>このGCは搭載されなくなり、[[macOS Sierra|macOS 10.12]]で廃止された。2015年5月以降、[[Mac App Store]]で新規登録／更新されるアプリはGCを使えなくなっている<ref>{{Cite web|url=https://www.macobserver.com/tmo/article/apple-warns-developers-garbage-collection-is-dead-move-to-arc |title=Apple Warns Developers Garbage Collection is Dead, Move to ARC – The Mac Observer |language=en |accessdate=2019-02-14}}</ref>。代替として、自動参照カウント (Automatic Reference Counting; ARC) によるメモリ管理が推奨されている。一方で、[[GNUstep]]はBoehm GCを使用している。
+[[Objective-C]]には参照カウントベースのオブジェクト寿命管理機能が組み込まれており、元々ガベージコレクションはなかったが、[[Apple]]のObjective-C 2.0では、[[Mac OS X 10.5]]以降に限り<ref>{{Cite web|url=https://www.atmarkit.co.jp/ait/articles/0908/05/news096_2.html |title=メモリ管理を理解する（後編） (2/2)：Cocoaの素、Objective-Cを知ろう（8） - ＠IT |accessdate=2019-02-14}}</ref>保守的な世代別GCベースのランタイムコレクタが使用可能である。ただし[[IOS (Apple)|iOS]]ではこのGCを利用できない。なお、[[macOS]]に関しても、<code>NSGarbageCollector</code>は[[OS X Mountain Lion|OS X 10.8]]から廃止予定扱いとなり、SDK 10.10を最後に廃止されており<ref>{{Cite web|url=https://developer.apple.com/documentation/foundation/nsgarbagecollector?language=occ |title=NSGarbageCollector - Foundation {{!}} Apple Developer Documentation |language=en |accessdate=2019-02-14}}</ref>、また[[OS X El Capitan|OS X 10.11]]を最後に<ref>{{Cite web|url=https://developer.apple.com/library/archive/releasenotes/DeveloperTools/RN-Xcode/Chapters/Introduction.html#//apple_ref/doc/uid/TP40001051-CH1-SW160 |title=Xcode Release Notes {{!}} Xcode 8.3 |language=en |accessdate=2019-02-14}}</ref>このGCは搭載されなくなり、[[macOS Sierra|macOS 10.12]]で廃止された。2015年5月以降、[[Mac App Store]]で新規登録／更新されるアプリはGCを使えなくなっている<ref>{{Cite web|url=https://www.macobserver.com/tmo/article/apple-warns-developers-garbage-collection-is-dead-move-to-arc |title=Apple Warns Developers Garbage Collection is Dead, Move to ARC – The Mac Observer |language=en |accessdate=2019-02-14}}</ref>。代替として、自動参照カウント (Automatic Reference Counting; ARC) によるメモリ管理が推奨されている。一方で、[[GNUstep]]はBoehm GCを使用している。
 [[Python]]は主に参照カウント方式のガベージコレクションを用いているが、補助的に（伝統的なマーク＆スイープとは逆順の探索アルゴリズムによる）世代別GCを併用している<ref>{{Cite web|url=https://docs.python.jp/3/library/gc.html#module-gc |title=29.11. gc — ガベージコレクタインターフェース — Python 3.6.5 ドキュメント |accessdate=2019-02-10}}</ref><ref>{{Cite web|url=http://arctrix.com/nas/python/gc/ |title=Garbage Collection for Python |language=en |accessdate=2019-02-10}}</ref>。