ガベージコレクション（コンピュータサイエンス）

コンピュータサイエンスにおいて、ガベージコレクション（GC ）は自動メモリ管理の一形態です。^[2]ガベージコレクターは、プログラムによって割り当てられたが参照されなくなったメモリを回収しようとします。このようなメモリはガベージと呼ばれます。ガベージコレクションは、1959年頃にアメリカのコンピュータ科学者ジョン・マッカーシーによって、 Lispでの手動メモリ管理を簡素化するために発明されました。^[3]

ガベージコレクションは、プログラマーがどのオブジェクトを解放してメモリシステムに戻すか、またいつそうするかを指定する手動のメモリ管理からプログラマーを解放します。 ^[4]その他の同様の技術には、スタック割り当て、領域推論、メモリ所有権、およびそれらの組み合わせがあります。ガベージコレクションはプログラムの総処理時間のかなりの部分を占め、結果として パフォーマンスに影響を与える可能性があります。

ネットワーク ソケット、データベースハンドル、ウィンドウ、ファイル記述子、デバイス記述子などのメモリ以外のリソースは、通常、ガベージ コレクションではなく、他の方法(デストラクタなど) によって処理されます。このような方法の中には、メモリの割り当てを解除するものもあります。

多くのプログラミング言語では、言語仕様の一部として（例：RPL、Java、C#、D、^[5] Go、およびほとんどのスクリプト言語）、または実質的に実用的な実装として（例：ラムダ計算などの形式言語）ガベージコレクションが必要です。^{[6]これらは、}ガベージコレクション言語と言われています。 CやC++などの他の言語は、手動メモリ管理で使用するように設計されていますが、ガベージコレクションの実装が利用可能です。Ada、Modula-3、C++/CLIなどの一部の言語では、収集されたオブジェクトと手動で管理されるオブジェクトに別のヒープを使用することで、ガベージコレクションと手動メモリ管理の両方を同じアプリケーションで共存させることができます。 Dなどの他の言語は、ガベージコレクションされますが、ユーザーがオブジェクトを手動で削除したり、速度が必要な場合はガベージコレクションを完全に無効にしたりすることもできます。^[7]

多くの言語ではGCをコンパイラやランタイムシステムに統合していますが、自動参照カウント（ARC）などの事後GCシステムも存在します。これらの事後GCシステムの中には再コンパイルを必要としないものもあります。^[8]

GCはプログラマーが手動でメモリを解放する手間を省きます。これにより、いくつかの種類のエラーを回避できます。^[9]

• ダングリングポインタは、メモリの一部が解放されたときにそのメモリへのポインタがまだ存在し、そのポインタの1つが参照解除されたときに発生します。その時点でメモリは別の用途に再割り当てされている可能性があり、予期しない結果が生じる可能性があります。 ^[10]
• 二重解放バグは、プログラムがすでに解放され、おそらくすでに再割り当てされているメモリ領域を解放しようとしたときに発生します。
• ある種のメモリリークでは、プログラムがアクセス不能になったオブジェクトによって占有されているメモリを解放できず、メモリ枯渇につながる可能性があります。^[11]

GC は、どのメモリを解放するかを決定するためにコンピューティング リソースを使用します。したがって、ソース コードでオブジェクトの有効期間を手動で注釈付けしないという利便性の代償としてオーバーヘッドが発生し、プログラムのパフォーマンスが低下する可能性があります。^[12] 2005 年の査読済み論文では、このオーバーヘッドを補い、理想的な明示的なメモリ管理を使用する同じプログラムと同じ速度で実行するには、GC に 5 倍のメモリが必要であると結論付けられています。ただし、比較は、プロファイラーで実行されるプログラムからトレースを収集することによって実装された、オラクルを使用して割り当て解除呼び出しを挿入することによって生成されたプログラムに対して行われ、プログラムは特定の 1 回の実行に対してのみ正しいものです。^[13]メモリ階層効果との相互作用により、日常的なテストで予測または検出するのが難しい状況では、このオーバーヘッドが許容できないものになる可能性があります。最も望まれている機能であるにもかかわらず、 Apple はiOSでガベージ コレクションを採用しない理由としてパフォーマンスへの影響を挙げました。 ^[14]

ガベージが実際に収集される瞬間は予測不可能な場合があり、その結果、セッション全体にストール (メモリの移動/解放のための一時停止) が散発的に発生します。予測不可能なストールは、リアルタイム環境、トランザクション処理、または対話型プログラムでは許容されません。増分、同時、およびリアルタイムのガベージ コレクターは、さまざまなトレードオフを伴いながら、これらの問題に対処します。

トレース ガベージ コレクションは最も一般的なタイプのガベージ コレクションであり、「ガベージ コレクション」は参照カウントなどの他の方法ではなく、トレース ガベージ コレクションを指すことがよくあります。全体的な戦略は、特定のルート オブジェクトからの参照のチェーンによって到達可能なオブジェクトをトレースすることによって、ガベージ コレクションするオブジェクトを決定し、残りをガベージと見なして収集することです。ただし、実装には多数のアルゴリズムが使用され、複雑さとパフォーマンス特性は大きく異なります。

参照カウントガベージコレクションでは、各オブジェクトに参照回数のカウントが付けられます。ガベージは参照カウントがゼロであることによって識別されます。オブジェクトの参照カウントは、参照が作成されると増加し、参照が破棄されると減少します。カウントがゼロになると、オブジェクトのメモリが再利用されます。^[15]

手動のメモリ管理と同様に、またガベージ コレクションのトレースとは異なり、参照カウントは、最後の参照が破棄されるとすぐにオブジェクトが破棄されることを保証し、通常はCPU キャッシュ内、解放されるオブジェクト内、またはそれらによって直接ポイントされるメモリのみにアクセスするため、CPU キャッシュおよび仮想メモリ操作に重大な悪影響を与えない傾向があります。

参照カウントにはいくつかの欠点がありますが、一般的にはより洗練されたアルゴリズムによって解決または軽減できます。

サイクル

2 つ以上のオブジェクトが互いを参照している場合、相互参照によって参照カウントが 0 にならないため、どちらも収集されない循環が発生する可能性があります。参照カウントを使用する一部のガベージ コレクション システム ( CPythonのものなど) では、特定の循環検出アルゴリズムを使用してこの問題に対処しています。^{[16]別の戦略は、循環を作成する「バックポインタ」に}弱参照を使用することです。参照カウントでは、弱参照はトレース ガベージ コレクターでの弱参照に似ています。これは、存在しても参照先オブジェクトの参照カウントが増加しない特別な参照オブジェクトです。さらに、弱参照は、参照先オブジェクトがガベージになると、そのオブジェクトへの弱参照が無効になり、ぶら下がったままになる (つまり、null 参照などの予測可能な値に変わる) ことがないという点で安全です。

スペースオーバーヘッド（参照カウント）

参照カウントでは、各オブジェクトに参照カウントを格納するための領域を割り当てる必要があります。カウントは、オブジェクトのメモリに隣接して格納することも、別の場所のサイド テーブルに格納することもできますが、いずれの場合も、参照カウントが適用されるすべてのオブジェクトには、参照カウント用の追加ストレージが必要です。このタスクには、通常、符号なしポインタのサイズのメモリ領域が使用されます。つまり、各オブジェクトに 32 ビットまたは 64 ビットの参照カウント ストレージを割り当てる必要があります。一部のシステムでは、タグ付きポインタを使用してオブジェクトのメモリの未使用領域に参照カウントを格納することで、このオーバーヘッドを軽減できる場合があります。多くの場合、アーキテクチャでは、ネイティブ ポインタ サイズに格納できるメモリ アドレスの全範囲にプログラムがアクセスすることを実際には許可していません。アドレスの上位ビットの一定数は無視されるか、ゼロである必要があります。オブジェクトが特定の場所に確実にポインタを持っている場合、参照カウントはポインタの未使用ビットに格納できます。たとえば、Objective-Cの各オブジェクトには、メモリの先頭にそのクラスへのポインタがあります。 iOS 7を使用するARM64アーキテクチャでは、このクラスポインタの未使用の19ビットがオブジェクトの参照カウントを格納するために使用されます。^{[17] [18]}

速度オーバーヘッド（増加/減少）

単純な実装では、参照の割り当てやスコープ外の参照ごとに、1 つ以上の参照カウンタの変更が必要になることがよくあります。ただし、参照が外側のスコープ変数から内側のスコープ変数にコピーされ、内側の変数の有効期間が外側の変数の有効期間によって制限される一般的なケースでは、参照の増分は排除できます。外側の変数は参照を「所有」します。プログラミング言語 C++ では、この手法はconst参照を使用して簡単に実装および実証できます。C++ での参照カウントは通常、「スマート ポインタ」^[19]を使用して実装され、そのコンストラクタ、デストラクタ、および割り当て演算子が参照を管理します。スマート ポインタは関数への参照によって渡すことができるため、新しいスマート ポインタをコピーして構築する必要がなくなります (これにより、関数に入るときに参照カウントが増加し、終了するときに減少します)。代わりに、関数は、コストをかけずに生成されたスマート ポインタへの参照を受け取ります。参照カウントの Deutsch-Bobrow 法は、ほとんどの参照カウント更新が実際にはローカル変数に格納された参照によって生成されるという事実を利用しています。この方法ではこれらの参照は無視され、ヒープ内の参照のみがカウントされますが、参照カウントが 0 のオブジェクトを削除する前に、システムはスタックとレジスタをスキャンして、そのオブジェクトへの他の参照が存在しないことを確認する必要があります。カウンタ更新のオーバーヘッドをさらに大幅に削減するには、Levanoni とPetrankによって導入された更新の結合を使用します。^{[20] [21]}実行の特定の間隔で複数回更新されるポインタを考えてみましょう。ポインタは最初にオブジェクト を指しO1、次にオブジェクト を指しO2、間隔の終わりには何らかのオブジェクト を指します。参照カウント アルゴリズムは通常、、、、、、...をOn実行します。しかし、これらの更新のほとんどは冗長です。間隔の終わりに参照カウントを適切に評価するには、および を実行すれば十分です。 Levanoni と Petrank は、一般的な Java ベンチマークでカウンター更新の 99% 以上が排除されたことを測定しました。rc(O1)--rc(O2)++rc(O2)--rc(O3)++rc(O3)--rc(On)++rc(O1)--rc(On)++

原子性が必要

マルチスレッド環境で使用する場合、これらの変更 (増分と減分) は、少なくとも複数のスレッド間で共有されているか、共有される可能性があるオブジェクトについては、比較とスワップなどのアトミック操作である必要がある場合があります。アトミック操作はマルチプロセッサではコストが高く、ソフトウェア アルゴリズムでエミュレートする必要がある場合は、さらにコストがかかります。この問題は、スレッドごとまたは CPU ごとに参照カウントを追加し、ローカル参照カウントがゼロになるかゼロでなくなった場合にのみグローバル参照カウントにアクセスすることで回避できます (または、代わりに、参照カウントのバイナリ ツリーを使用するか、グローバル参照カウントをまったく持たないことと引き換えに決定論的な破棄をあきらめることもできます)。ただし、これによりメモリのオーバーヘッドが大幅に増加するため、特殊な場合にのみ役立つ傾向があります (たとえば、Linux カーネル モジュールの参照カウントで使用されます)。Levanoni と Petrank による更新合体^{[20] [21]}を使用すると、書き込みバリアからすべてのアトミック操作を排除できます。カウンターは、プログラム実行中にプログラム スレッドによって更新されることはありません。カウンターは、同期なしで単一の追加スレッドとして実行されるコレクターによってのみ変更されます。この方法は、並列プログラムのストップ ザ ワールド メカニズムとして、また同時参照カウント コレクターとともに使用できます。

リアルタイムではない

参照カウントの単純な実装では、通常、リアルタイムの動作は提供されません。これは、ポインター割り当てによって、割り当てられたメモリ サイズの合計によって制限される数のオブジェクトが、スレッドが他の作業を実行できない間に再帰的に解放される可能性があるためです。参照されていないオブジェクトの解放を他のスレッドに委任することで、余分なオーバーヘッドを犠牲にして、この問題を回避することができます。

エスケープ解析は、ヒープ割り当てをスタック割り当てに変換できるコンパイル時の手法であり、これによりガベージコレクションの回数を減らすことができます。この解析では、関数内で割り当てられたオブジェクトが関数外からアクセス可能かどうかを判定します。関数ローカル割り当てが別の関数またはスレッドからアクセス可能であることが判明した場合、割り当ては「エスケープ」され、スタック上で実行することはできません。それ以外の場合は、オブジェクトをスタック上に直接割り当て、関数が返されたときに解放することで、ヒープと関連するメモリ管理コストを回避できます。^[22]

一般的に、高水準プログラミング言語では、ガベージ コレクションが標準機能として備わっている可能性が高くなります。ガベージ コレクションが組み込まれていない言語では、 C および C++ のBoehm ガベージ コレクターのように、ライブラリを通じてガベージ コレクションを追加できます。

ML、Haskell、APLなどのほとんどの関数型プログラミング言語にはガベージコレクションが組み込まれています。Lispは最初の関数型プログラミング言語であると同時に、ガベージコレクションを導入した最初の言語としても特に注目に値します。^[23]

RubyやJulia（ただし、参照カウントを使用するPerl 5やバージョン5.3より前のPHPは除く[24]）、JavaScript、ECMAScriptなどの他の動的言語もGCを使用する傾向があります。Smalltalk、ooRexx 、  RPL 、Java^などのオブジェクト指向プログラミング言語は通常、統合ガベージコレクションを提供します。注目すべき例外は、デストラクタを持つC++とDelphiです。

BASICとLogoでは、プログラマにメモリ管理の詳細を負担させないために、文字列やリストなどの可変長データ型にガベージ コレクションを使用することが多い。Altair 8800では、文字列変数が多く、文字列スペースが少ないプログラムでは、ガベージ コレクションによって長時間の停止が発生することがあった。^[25]同様に、Applesoft BASICインタプリタのガベージ コレクション アルゴリズムは、最高アドレスの文字列を文字列記述子で繰り返しスキャンして高メモリ方向に圧縮するため、パフォーマンスが低下し^[26]、停止時間は数秒から数分になる。^[27] Randy Wiggintonによる Applesoft BASIC の代替ガベージ コレクターは、ヒープ上のすべてのパスで文字列のグループを識別し、コレクション時間を大幅に短縮する。^{[28 ] 1983 年に}ProDOSとともにリリースされた BASIC.SYSTEM は、BASIC 用のウィンドウ ガベージ コレクターを提供し、これは何倍も高速である。^[29]${\displaystyle O(n^{2})}$

Objective-Cには伝統的にガベージコレクションがなかったが、 2007年のOS X 10.5のリリースでApple は 自社開発のランタイムコレクターを使用してObjective-C 2.0にガベージコレクションを導入した。 ^{[30]しかし、2012 年の}OS X 10.8 のリリースでガベージコレクションは非推奨となり、代わりにOS X 10.7で導入されたLLVMの自動参照カウンター(ARC) が採用された。^{[31]さらに、2015 年 5 月以降、Apple は}App Storeでの新しい OS X アプリケーションでのガベージコレクションの使用を禁止した。^{[32] [33]} iOSでは、アプリケーションの応答性とパフォーマンスの問題からガベージコレクションは導入されていない。^{[14] [34]}代わりに iOS は ARC を使用している。^{[35] [36]}

ガベージコレクションは、限られたリソースの使用を厳密に制御する必要があるため、組み込みシステムやリアルタイムシステムではほとんど使用されません。ただし、多くの限られた環境と互換性のあるガベージコレクターが開発されています。 ^[37] Microsoft .NET Micro Framework、.NET nanoFramework ^[38]、およびJava Platform, Micro Editionは、より大規模な類似製品と同様にガベージコレクションを含む組み込みソフトウェアプラットフォームです。

Java JDK で利用可能なガベージ コレクターには次のものがあります。

• G1
• 平行
• 同時マークスイープコレクター(CMS)
• シリアル
• C4（連続並行コンパクションコレクター）^[39]
• シェナンドー
• ゼグ

コンパイル時のガベージ コレクションは、コンパイル時に判明した不変条件に基づいてメモリを再利用および回収できる 静的分析の一種です。

この形式のガベージコレクションはMercuryプログラミング言語で研究されており、^[40] 2011年にLLVMの自動参照カウンタ（ARC）がAppleのエコシステム（iOSとOS X）に導入されたことで、より広く使用されるようになりました。 ^{[35] [36] [32]}

インクリメンタル、コンカレント、リアルタイムのガベージコレクターは、例えばヘンリー・ベイカーやヘンリー・リーバーマンによって開発されてきた。^{[41] [42] [43]}

ベイカーのアルゴリズムでは、メモリの単一領域のどちらか半分で割り当てが行われます。メモリが半分いっぱいになると、ガベージコレクションが実行され、ライブオブジェクトがもう半分に移動され、残りのオブジェクトは暗黙的に割り当て解除されます。実行中のプログラム (「ミューテーター」) は、参照するオブジェクトが正しい半分にあるかどうかを確認し、そうでない場合は、バックグラウンドタスクがすべてのオブジェクトを検索している間に、オブジェクトを移動する必要があります。^[44]

世代別ガベージ コレクションスキームは、ほとんどのオブジェクトが早く消滅するという経験的観察に基づいています。世代別ガベージ コレクションでは、2 つ以上の割り当て領域 (世代) が保持され、オブジェクトの古さに基づいて分離されます。新しいオブジェクトは、定期的に収集される「若い」世代に作成され、世代がいっぱいになると、古い領域からまだ参照されているオブジェクトが次に古い世代にコピーされます。時々、完全スキャンが実行されます。

一部の高級言語コンピュータ アーキテクチャには、リアルタイム ガベージ コレクションのハードウェア サポートが含まれています。

リアルタイムガベージコレクターの実装のほとんどはトレースを使用します。^[要出典]このようなリアルタイムガベージコレクターは、リアルタイムオペレーティングシステムで使用すると厳しいリアルタイム制約を満たします。 ^[45]

• デストラクタ (コンピュータ プログラミング)
• 動的なデッドコード除去
• スマートポインター
• 仮想メモリ圧縮

• ジョーンズ、リチャード、ホスキング、アントニー、モス、J. エリオット B. (2011-08-16)。ガベージコレクション ハンドブック: 自動メモリ管理の技法。CRC 応用アルゴリズムおよびデータ構造シリーズ。チャップマン アンド ホール/ CRC プレス/テイラー & フランシス社。ISBN 978-1-4200-8279-1。（511ページ）
• ジョーンズ、リチャード; リンス、ラファエル (1996-07-12)。ガベージコレクション: 自動動的メモリ管理アルゴリズム(第 1 版) 。Wiley。ISBN 978-0-47194148-4。（404ページ）
• Schorr, Herbert ; Waite, William M. (1967 年 8 月)。「さまざまなリスト構造でのガベージ コレクションのための効率的なマシン非依存手順」(PDF)。Communications of the ACM。10 ( 8): 501–506。doi :10.1145/363534.363554。S2CID 5684388。2021年 1月22 日にオリジナルから アーカイブ(PDF) 。
• Wilson , Paul R. ( 1992)。「ユニプロセッサ ガベージ コレクション テクニック」。メモリ管理。コンピュータ サイエンスの講義ノート。第 637 巻。Springer-Verlag。pp . 1–42。CiteSeerX 10.1.1.47.2438。doi :10.1007  / bfb0017182。ISBN 3-540-55940-X。 {{cite book}}:|journal=無視されました (ヘルプ)
• Wilson, Paul R.; Johnstone, Mark S.; Neely, Michael; Boles, David (1995)。「動的ストレージ割り当て: 調査と批評」。メモリ管理。コンピュータサイエンスの講義ノート。第 986 巻 (第 1 版) 。pp . 1–116。CiteSeerX 10.1.1.47.275。doi :  10.1007 / 3-540-60368-9_19。ISBN 978-3-540-60368-9。 {{cite book}}:|journal=無視されました (ヘルプ)

Wikibookのメモリ管理には、ガベージコレクションに関するページがあります。

• メモリ管理リファレンス
• ガベージコレクションの基本
• Java SE 6 HotSpot 仮想マシン ガベージ コレクションのチューニング
• TinyGC - BoehmGC API の独立した実装
• C言語の保守的なガベージコレクションの実装
• MeixnerGC - スマート ポインタを使用した C++ 用の増分マーク アンド スイープ ガベージ コレクター