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

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

• ダングリングポインタとは、メモリ領域が解放された後もその領域へのポインタが存在し、かつそれらのポインタの1つが逆参照された場合に発生するものです。その時点でメモリは別の用途に再割り当てされている可能性があり、予期せぬ結果を招くことがあります。 ^{[ 9 ]}
• ダブルフリーバグとは、プログラムが既に解放されたメモリ領域を解放しようとした際に発生するバグであり、場合によっては既に再度割り当てられているメモリ領域を解放しようとした際に発生する。
• メモリリークにはいくつかの種類があり、プログラムがアクセスできなくなったオブジェクトによって占有されているメモリを解放できないため、メモリ枯渇につながる可能性があります。^{[ 10 ]}

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

実際にガベージコレクションが行われるタイミングは予測不可能であり、セッション全体にわたってストール（メモリの解放や移動のための一時停止）が発生することがあります。このような予測不可能なストールは、リアルタイム環境、トランザクション処理、または対話型プログラムでは許容できない場合があります。インクリメンタル、コンカレント、リアルタイムのガベージコレクタは、それぞれ異なるトレードオフを持ちながら、これらの問題に対処します。

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

参照カウント方式のガベージコレクションでは、各オブジェクトは自身への参照数をカウントします。ガベージは参照カウントがゼロであるオブジェクトとして識別されます。オブジェクトの参照カウントは、そのオブジェクトへの参照が作成されると増加し、参照が破棄されると減少します。カウントがゼロになると、オブジェクトのメモリが解放されます。^{[ 15 ]}

As with manual memory management, and unlike tracing garbage collection, reference counting guarantees that objects are destroyed as soon as their last reference is destroyed, and usually only accesses memory which is either in CPU caches, in objects to be freed, or directly pointed to by those, and thus tends to not have significant negative side effects on CPU cache and virtual memory operation.

There are a number of disadvantages to reference counting; this can generally be solved or mitigated by more sophisticated algorithms:

Cycles

If two or more objects refer to each other, they can create a cycle whereby neither will be collected as their mutual references never let their reference counts become zero. Some garbage collection systems using reference counting (like the one in CPython) use specific cycle-detecting algorithms to deal with this issue.^[16] Another strategy is to use weak references for the "backpointers" which create cycles. Under reference counting, a weak reference is similar to a weak reference under a tracing garbage collector. It is a special reference object whose existence does not increment the reference count of the referent object. Furthermore, a weak reference is safe in that when the referent object becomes garbage, any weak reference to it lapses, rather than being permitted to remain dangling, meaning that it turns into a predictable value, such as a null reference.

Space overhead (reference count)

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

速度オーバーヘッド（インクリメント／デクリメント）

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

原子性が必要

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

リアルタイムではない

参照カウントの単純な実装では、一般的にリアルタイム動作は実現できません。なぜなら、ポインタの割り当てによって、割り当てられたメモリの合計サイズによってのみ制限される数のオブジェクトが再帰的に解放される可能性があり、その間スレッドは他の処理を実行できなくなるからです。この問題を回避するには、参照されていないオブジェクトの解放を他のスレッドに委任する方法がありますが、その分オーバーヘッドが増加します。

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

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

C言語はこれまでガベージコレクションを公式にサポートしたことはありません。C ++はC++11で標準ライブラリにガベージコレクションのサポートを追加しましたが、この機能をサポートするコンパイラがなかったため、C++23で削除されました。 ^{[ 30 ]}この一部に含まれていた機能はポインタの安全性に関連していました。^{[ 31 ]}

標準ライブラリのガベージコレクションのサポートは削除されましたが、Boehmガベージコレクタ（CおよびC++用）などの一部のガベージコレクタは引き続き使用できます。Boehm GCはトレースガベージコレクションを使用します。メモリ管理は手動のままですが、メモリリークやダブルフリーエラーを検出して報告できるリーク検出モードでも使用できます。その使用はヘッダーから呼び出すことができます<gc.h>。

C++ では、「リソース取得は初期化である」（RAII）イディオムとスマートポインタを使用することで、手動によるオブジェクト破棄を抽象化できます。std::unique_ptrはライフタイムを所有権に結び付け、 はstd::shared_ptr参照カウントを使用してライフタイムを決定します。 を使用するstd::weak_ptrと、参照カウントを増やさずにポインタを取得できます。ガベージコレクションとは異なり、RAII は決定論的です。

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

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

Java OpenJDKs仮想マシン（JVM）で利用可能なガベージコレクタには、以下のものがあります。

• シリアル
• 平行
• CMS（同時マークスイープ）
• G1 (Garbage-First)
• ZGC (Z Garbage Collector)
• Epsilon
• Shenandoah
• GenZGC (Generational ZGC)
• GenShen (Generational Shenandoah)
• IBM Metronome (only in IBM OpenJDK)
• SAP (only in SAP OpenJDK)
• Azul C4 (Continuously Concurrent Compacting Collector)^[41] (only in Azul Systems OpenJDK)

Compile-time garbage collection is a form of static analysis allowing memory to be reused and reclaimed based on invariants known during compilation.

This form of garbage collection has been studied in the Mercury programming language,^[42] and it saw greater usage with the introduction of LLVM's automatic reference counter (ARC) into Apple's ecosystem (iOS and OS X) in 2011.^[37][38][34]

Incremental, concurrent, and real-time garbage collectors have been developed, for example by Henry Baker and by Henry Lieberman.^[43][44][45]

In Baker's algorithm, the allocation is done in either half of a single region of memory. When it becomes half full, a garbage collection is performed which moves the live objects into the other half and the remaining objects are implicitly deallocated. The running program (the 'mutator') has to check that any object it references is in the correct half, and if not move it across, while a background task is finding all of the objects.^[46]

Generational garbage collection schemes are based on the empirical observation that most objects die young. In generational garbage collection, two or more allocation regions (generations) are kept, which are kept separate based on the object's age. New objects are created in the "young" generation that is regularly collected, and when a generation is full, the objects that are still referenced from older regions are copied into the next oldest generation. Occasionally a full scan is performed.

Some high-level language computer architectures include hardware support for real-time garbage collection.

Most implementations of real-time garbage collectors use tracing. Such real-time garbage collectors meet hard real-time constraints when used with a real-time operating system.^[47]