ガベージコレクションのトレース

コンピュータ プログラミングにおいて、トレース ガベージ コレクションは、自動メモリ管理の一種で、特定の「ルート」オブジェクトからの参照チェーンによって到達可能なオブジェクトをトレースし、残りを「ガベージ」と見なして収集することで、割り当てを解除 (「ガベージ コレクション」) するオブジェクトを決定し、収集するものです。トレースは最も一般的なタイプのガベージ コレクションです。そのため、「ガベージ コレクション」は参照カウントなどの他の方法ではなく、トレース方法を指すことが多く、実装には多数のアルゴリズムが使用されています。

非公式には、オブジェクトは、プログラム内の少なくとも 1 つの変数によって直接参照されるか、または他の到達可能なオブジェクトからの参照を介して参照される場合に到達可能です。より正確には、オブジェクトに到達できるのは 2 つの方法のみです。

1. ルートの区別されたセット: 到達可能であると想定されるオブジェクト。通常、これらには、コール スタック内の任意の場所から参照されるすべてのオブジェクト(つまり、現在呼び出されている関数内のすべてのローカル変数とパラメーター) と、すべてのグローバル変数が含まれます。
2. 到達可能なオブジェクトから参照されるものはすべて、それ自体が到達可能です。より正式には、到達可能性は推移的な閉包です。

プログラムがオブジェクトを最後に使用するのは、そのオブジェクトが環境スコープから外れる前になる可能性があるため、「ゴミ」の到達可能性の定義は最適ではありません。構文上のゴミ (プログラムが到達できないオブジェクト) と意味上のゴミ(プログラムが実際には二度と使用しないオブジェクト) を区別することがあります。例:

Object x = new Foo (); Object y = new Bar (); x = new Quux (); /* この時点で、元々 x に割り当てられた Foo オブジェクトにはアクセスされないことが分かっています。これは構文上のゴミです。*/    
    
   





/* 次のブロックでは、 y は意味的にゴミである可能性があります。 * ただし、 x.check_something()
が何らかの値を返すまで、それが返されるかどうかはわかりません。 
*/ if ( x . check_something ()) { x . do_something ( y ); } System . exit ( 0 );

  
    

意味的ゴミを正確に識別する問題は、部分的に決定可能であることが簡単に示されます。つまり、オブジェクトを割り当て、任意の入力プログラムを実行し、終了した場合に限り使用するプログラムでは、停止問題を解決するために意味的ゴミコレクターが必要になります。意味的ゴミ検出のための保守的なヒューリスティック手法は、活発な研究分野のままですが、基本的にすべての実用的なゴミコレクターは、構文的ゴミに焦点を当てています。^{[引用が必要]}${\displaystyle X}$${\displaystyle P}$${\displaystyle X}$${\displaystyle P}$

このアプローチのもう 1 つの複雑な点は、参照型とボックス化されていない値型の両方を持つ言語では、ガベージ コレクターがスタック上のどの変数またはオブジェクト内のフィールドが通常の値で、どれが参照であるかを何らかの方法で区別する必要があることです。メモリ内では、整数と参照は似ている可能性があります。ガベージ コレクターは、要素を参照として扱って追跡するか、またはそれがプリミティブ値であるかどうかを認識する必要があります。一般的な解決策の 1 つは、タグ付きポインターを使用することです。

ガベージ コレクターは、ルート セットから直接または間接的に参照されていないオブジェクトのみを回収できます。ただし、一部のプログラムでは、オブジェクトが存在する限り使用可能であるが、その寿命を延ばすべきではない、弱参照が必要です。弱参照に関する議論では、通常の参照は強参照と呼ばれることがあります。オブジェクトへの強い (つまり通常の) 参照がない場合、そのオブジェクトはガベージ コレクションの対象となりますが、弱参照がいくつか残っている可能性があります。

弱い参照は、ガベージ コレクターが気にしないオブジェクトへの単なるポインターではありません。この用語は通常、安全な値 (通常は ) に変化nullするため、オブジェクトが消えた後でも安全に使用できる、適切に管理された特別な参照オブジェクトのカテゴリに対して予約されています。ガベージ コレクターに認識されない安全でない参照は、オブジェクトが以前存在していたアドレスを参照し続けることによって、単に宙ぶらりんのままになります。これは弱い参照ではありません。

いくつかの実装では、弱参照はサブカテゴリに分けられます。たとえば、Java仮想マシンは、ソフト参照、^[1]、 ファントム参照、^[2]、および通常の弱参照の3つの形式の弱参照を提供します。^[3]ソフト参照されたオブジェクトは、ガベージコレクターがプログラムのメモリが少ないと判断した場合にのみ、再利用の対象となります。ソフト参照や通常の弱参照とは異なり、ファントム参照は参照先のオブジェクトへのアクセスを提供しません。その代わりに、ファントム参照は、参照されたオブジェクトがファントム到達可能になったときにガベージコレクターがプログラムに通知できるようにするメカニズムです。オブジェクトがまだメモリ内に存在し、ファントム参照によって参照されているが、そのファイナライザがすでに実行されている場合、オブジェクトはファントム到達可能です。同様に、Microsoft.NETは、弱参照の2つのサブカテゴリ、^[4]、つまり長い弱参照（復活を追跡）と短い弱参照を提供します。

弱い追跡機能を持つデータ構造も考案できます。たとえば、弱いハッシュ テーブルは便利です。通常のハッシュ テーブルと同様に、弱いハッシュ テーブルは、各ペアがキーと値であると理解されるオブジェクトのペア間の関連付けを維持します。ただし、ハッシュ テーブルは実際にはこれらのオブジェクトに対する強い参照を維持していません。キーまたは値、またはその両方がガベージになると、特別な動作が発生します。ハッシュ テーブル エントリは自動的に削除されます。さらに、弱いキーのみ (値参照は通常の強い参照) または弱い値のみ (キー参照は強い参照) を持つハッシュ テーブルなどの改良版も存在します。

弱いハッシュ テーブルは、オブジェクト間の関連付けを維持するために重要です。関連付けに関与するオブジェクトは、プログラム内でそれらのオブジェクトを参照するものがなくなった場合 (関連付けられているハッシュ テーブル以外)、ガベージになる可能性があります。

このような目的で通常のハッシュ テーブルを使用すると、「論理メモリ リーク」が発生する可能性があります。これは、プログラムが必要とせず、使用しないアクセス可能なデータが蓄積されることを意味します。

トレース コレクターは、メモリのワーキング セットをトレースするため、このように呼ばれています。これらのガベージ コレクターは、コレクションをサイクルで実行します。メモリ マネージャーが割り当て要求を満たすのに十分な空きメモリがない場合、サイクルがトリガーされるのが一般的です。ただし、サイクルはミューテーターによって直接要求されるか、タイム スケジュールに従って実行されることがよくあります。元の方法では、メモリ セット全体が複数回アクセスされる 単純なマーク アンド スイープが使用されます。

単純なマーク アンド スイープ方式では、メモリ内の各オブジェクトには、ガベージ コレクション専用に予約されたフラグ (通常は 1 ビット) があります。このフラグは、コレクション サイクル中を除いて常にクリアされます。

最初のステージはマーク ステージで、これは「ルート セット」全体のツリー トラバーサルを実行し、ルートによってポイントされる各オブジェクトを「使用中」としてマークします。それらのオブジェクトがポイントするすべてのオブジェクトもマークされるため、ルート セット経由で到達可能なすべてのオブジェクトがマークされます。

2 番目のステージであるスイープ ステージでは、すべてのメモリが最初から最後までスキャンされ、すべての空きブロックまたは使用済みブロックが検査されます。「使用中」としてマークされていないブロックはどのルートからもアクセスできず、そのメモリは解放されます。使用中としてマークされたオブジェクトについては、使用中フラグがクリアされ、次のサイクルの準備が整います。

この方法にはいくつかの欠点がありますが、最も顕著な欠点は、コレクション中にシステム全体を一時停止する必要があることです。つまり、ワーキング セットの変更は許可されません。これにより、プログラムが定期的に (通常は予測できない形で) 「フリーズ」し、一部のリアルタイム アプリケーションや時間重視のアプリケーションが実行できなくなります。さらに、ワーキング メモリ全体を (大部分は 2 回) 検査する必要があり、ページ メモリシステムで問題が発生する可能性があります。

これらのパフォーマンスの問題のため、ほとんどの最新のトレース ガベージ コレクターは、 3 色マーキング 抽象化の何らかのバリエーションを実装していますが、単純なコレクター (マーク アンド スイープコレクターなど) では、この抽象化が明示的に行われないことがよくあります。3 色マーキングは、次のように機能します。

白、黒、グレーの3 つのセットが作成されます 。

• ホワイト セット、または廃棄予定セットは、メモリをリサイクルする候補となるオブジェクトのセットです。
• ブラック セットは、ホワイト セット内のオブジェクトへの出力参照がなく、ルートから到達可能であることが示されるオブジェクトのセットです。ブラック セット内のオブジェクトはコレクションの候補ではありません。
• グレー セットには、ルートから到達可能だが、「ホワイト」オブジェクトへの参照がまだスキャンされていないすべてのオブジェクトが含まれます。ルートから到達可能であることがわかっているため、ガベージ コレクションは実行できず、スキャン後にブラック セットに格納されます。

多くのアルゴリズムでは、最初は黒いセットは空で始まり、灰色のセットはルートから直接参照されるオブジェクトのセットで、白いセットには他のすべてのオブジェクトが含まれます。メモリ内のすべてのオブジェクトは常に 3 つのセットのいずれかに含まれます。アルゴリズムは次のように進行します。

1. 灰色のセットからオブジェクトoを選択します
2. 参照する各白いオブジェクトをグレー セットに移動します。これにより、このオブジェクトも、それが参照するどのオブジェクトもガベージ コレクションされないことが保証されます。
3. 黒のセットに移動
4. グレーのセットが空になるまで、最後の 3 つの手順を繰り返します。

灰色のセットが空になると、スキャンは完了します。黒いオブジェクトはルートから到達可能ですが、白いオブジェクトは到達不可能であり、ガベージ コレクションできます。

ルートから直接到達できないすべてのオブジェクトは白のセットに追加され、オブジェクトは白からグレーへ、グレーから黒へしか移動できないため、アルゴリズムは重要な不変条件 (黒のオブジェクトは白のオブジェクトを参照しない) を保持します。これにより、グレーのセットが空になると白のオブジェクトを解放できるようになります。これは、3 色不変条件と呼ばれます。アルゴリズムのいくつかのバリエーションでは、この不変条件を保持せず、すべての重要な特性が保持される修正された形式を使用します。

3 色方式には重要な利点があります。システムを長時間停止させることなく、オンザフライで実行できるのです。これは、オブジェクトが割り当てられるときにマークを付け、変更中にさまざまなセットを維持することで実現されます。セットのサイズを監視することで、システムは必要に応じてではなく定期的にガベージ コレクションを実行できます。また、各サイクルでワーキング セット全体に触れる必要がなくなります。

到達不能セットが決定されると、ガベージ コレクターは、到達不能オブジェクトを解放してその他すべてをそのままにしておくか、到達可能オブジェクトの一部またはすべてを新しいメモリ領域にコピーして、必要に応じてそれらのオブジェクトへのすべての参照を更新します。これらは、それぞれ「非移動」および「移動」(または「非圧縮」および「圧縮」) ガベージ コレクターと呼ばれます。

最初は、移動アルゴリズムは非移動アルゴリズムに比べて非効率的であるように思われるかもしれません。これは、各サイクルでより多くの作業が必要になるように見えるためです。しかし、移動アルゴリズムは、ガベージ コレクション サイクル自体とプログラム実行の両方で、いくつかのパフォーマンス上の利点をもたらします。

• デッド オブジェクトによって解放されたスペースを再利用するために追加の作業は必要ありません。到達可能なオブジェクトが移動されたメモリ領域全体が空きスペースとみなされます。対照的に、移動しない GC は、到達不可能な各オブジェクトを訪問し、そのオブジェクトが占有していたメモリが使用可能であることを記録する必要があります。
• 同様に、新しいオブジェクトも非常に素早く割り当てることができます。通常、大きな連続したメモリ領域は移動 GC によって使用可能になるため、新しいオブジェクトは単に「空きメモリ」ポインタを増分するだけで割り当てることができます。移動しない戦略では、しばらくするとヒープが極度に断片化され、新しいオブジェクトを割り当てるために、使用可能な小さなメモリ ブロックの「空きリスト」を高コストで参照する必要が生じる可能性があります。
• 適切なトラバーサル順序 (リストconsesの cdr-first など) を使用すると、オブジェクトをメモリ内で参照するオブジェクトのすぐ近くに移動できるため、同じキャッシュ ラインまたは仮想メモリページに配置される可能性が高くなります。これにより、これらの参照を介したオブジェクトへのアクセスが大幅に高速化されます。

移動ガベージコレクターの欠点の 1 つは、ガベージコレクション環境によって管理されている参照を介したアクセスのみが許可され、ポインター演算が許可されないことです。これは、ガベージコレクターがオブジェクトを移動すると、オブジェクトへのポインターが無効になるためです (ダングリングポインターになります)。ネイティブコードとの相互運用性を確保するため、ガベージコレクターはオブジェクトの内容をメモリのガベージコレクション領域外の場所にコピーする必要があります。別の方法として、オブジェクトをメモリ内に固定して、ガベージコレクターがオブジェクトを移動できないようにし、メモリをネイティブポインターと直接共有できるようにする (ポインター演算を許可する可能性もある) というものがあります。^[5]

コレクターは、移動するか移動しないかによって異なるだけでなく、収集サイクル中に白、灰色、黒のオブジェクト セットをどのように扱うかによっても分類できます。

最も単純なアプローチは、1969 年に登場したセミスペース コレクターです。この移動コレクターでは、メモリが等サイズの「from スペース」と「to スペース」に分割されます。最初は、to スペースがいっぱいになってコレクション サイクルがトリガーされるまで、オブジェクトが to スペースに割り当てられます。サイクルの開始時に、「to スペース」が「from スペース」になり、その逆も同様です。ルート セットから到達可能なオブジェクトは、「from スペース」から「to スペース」にコピーされます。これらのオブジェクトは順番にスキャンされ、それらが指すすべてのオブジェクトが「to スペース」にコピーされます。これは、到達可能なすべてのオブジェクトが「to スペース」にコピーされるまで続きます。プログラムが実行を続けると、to スペースが再びいっぱいになるまで、新しいオブジェクトが再び割り当てられ、プロセスが繰り返されます。

このアプローチは非常にシンプルですが、オブジェクトの割り当てに 1 つのセミスペースのみを使用するため、メモリ使用量は他のアルゴリズムに比べて 2 倍になります。この手法は、ストップ アンド コピーとも呼ばれます。Cheneyのアルゴリズムは、セミスペース コレクターの改良版です。

マーク アンド スイープ ガベージ コレクターは、各オブジェクトが白か黒かを記録するために 1 ビットまたは 2 ビットを保持します。グレー セットは、別のリストとして、または別のビットを使用して保持されます。コレクション サイクル (「マーク」フェーズ) 中に参照ツリーがトラバースされると、これらのビットはコレクターによって操作されます。メモリ領域の最後の「スイープ」により、白いオブジェクトが解放されます。マーク アンド スイープ戦略の利点は、廃棄セットが決定されたら、移動または非移動のコレクション戦略を実行できることです。この戦略の選択は、使用可能なメモリが許す限り、実行時に行うことができます。この戦略には、オブジェクトが少しだけ「膨張」するという欠点があります。つまり、リスト/追加ビットのために、すべてのオブジェクトに小さな隠れたメモリ コストがかかります。コレクターが割り当ても処理する場合は、割り当てデータ構造内の未使用のビットを使用できる可能性があるため、この欠点はいくらか軽減されます。または、タグ付きポインターを使用して、メモリ コストを CPU 時間で引き換えることで、この「隠れたメモリ」を排除できます。ただし、マーク アンド スイープは、そもそも外部アロケータと容易に連携できる唯一の戦略です。

マークアンド スイープガベージ コレクターは、マーク アンド スイープと同様に、各オブジェクトにビットを保持して、白か黒かを記録します。グレー セットは、別のリストとして、または別のビットを使用して保持されます。ここでは、2 つの重要な違いがあります。まず、黒と白の意味は、マーク アンド スイープ コレクターの場合とは異なります。「マーク アンド スイープ」コレクターでは、到達可能なすべてのオブジェクトは常に黒です。オブジェクトは割り当てられた時点で黒としてマークされ、到達不能になっても黒のままです。白のオブジェクトは未使用のメモリであり、割り当てることができます。次に、黒/白ビットの解釈は変わる可能性があります。最初は、黒/白ビットの意味は (0=白、1=黒) である可能性があります。割り当て操作で使用可能な (白) メモリが見つからない場合は、すべてのオブジェクトが使用済み (黒) としてマークされます。黒/白ビットの意味は反転されます (たとえば、0=黒、1=白)。すべてが白になります。これにより、到達可能なオブジェクトが黒であるという不変性が一時的に破られますが、すぐに完全なマーキング フェーズが続き、再び黒にマークされます。これが完了すると、到達不可能なメモリはすべて白になります。「スイープ」フェーズは必要ありません。

マーク アンド スウィープ戦略では、アロケータとコレクターの連携が必要ですが、割り当てられたポインターごとに 1 ビットしか必要としないため、スペース効率が非常に高くなります (ほとんどの割り当てアルゴリズムでは、いずれにしても 1 ビットが必要です)。ただし、ほとんどの場合、メモリの大部分が誤って黒 (使用済み) としてマークされるため、メモリ使用量が少ないときにリソースをシステムに戻す (他のアロケータ、スレッド、またはプロセスが使用できるようにする) のが難しくなり、この利点はいくらか軽減されます。

したがって、マーク アンド ドント スイープ戦略は、マーク アンド スイープとストップ アンド コピー戦略の長所と短所の間の妥協点として考えることができます。

多くのプログラムでは、最も最近作成されたオブジェクトが、すぐに到達不能になる可能性も最も高いことが経験的に観察されています (これは、初期死亡率または世代仮説として知られています)。世代別 GC (エフェメラル GC とも呼ばれます) は、オブジェクトを世代に分割し、ほとんどのサイクルでは、世代のサブセットのオブジェクトのみを初期のホワイト (廃棄) セットに配置します。さらに、ランタイム システムは、参照の作成と上書きを観察することによって、参照が世代をまたぐタイミングに関する知識を維持します。ガベージ コレクターが実行されると、この知識を使用して、参照ツリー全体をトラバースしなくても、初期のホワイト セットの一部のオブジェクトが到達不能であることを証明できる場合があります。世代仮説が成り立つ場合、これにより、ほとんどの到達不能オブジェクトを再利用しながら、コレクション サイクルが大幅に高速化されます。

この概念を実装するために、多くの世代別ガベージ コレクターは、オブジェクトの異なる年齢ごとに別々のメモリ領域を使用します。領域がいっぱいになると、古い世代からの参照をルートとして使用して、その領域内のオブジェクトがトレースされます。これにより、通常、その世代内のほとんどのオブジェクトが収集され (仮説により)、新しいオブジェクトの割り当てに使用されます。コレクションが多くのオブジェクトを収集しない場合 (たとえば、プログラムが保持したい新しいオブジェクトの大規模なコレクションを計算したために仮説が成立しない場合)、古いメモリ領域から参照されている生き残ったオブジェクトの一部またはすべてが次の最上位の領域に昇格され、領域全体が新しいオブジェクトで上書きされます。この手法により、一度に 1 つの領域のみのガベージ コレクションで済むため、非常に高速な増分ガベージ コレクションが可能になります。

Ungarの古典的な世代スカベンジャーには 2 つの世代があります。これは、「新しいスペース」と呼ばれる最も若い世代を、新しいオブジェクトが作成される大きな「エデン」と、過去のサバイバー スペースと将来のサバイバー スペースの 2 つの小さな「サバイバー スペース」に分割します。新しいスペースのオブジェクトを参照する可能性のある古い世代のオブジェクトは、「記憶セット」に保持されます。各スカベンジで、新しいスペースのオブジェクトは記憶セットのルートからトレースされ、将来のサバイバー スペースにコピーされます。将来のサバイバー スペースがいっぱいになると、適合しないオブジェクトは古いスペースに昇格されます。このプロセスは「テニュアリング」と呼ばれます。スカベンジの終了時に、一部のオブジェクトは将来のサバイバー スペースに存在し、エデンと過去のサバイバー スペースは空になります。その後、将来のサバイバー スペースと過去のサバイバー スペースが交換され、プログラムは続行され、エデンにオブジェクトを割り当てます。Ungar の元のシステムでは、エデンは各サバイバー スペースの 5 倍の大きさです。

世代別ガベージ コレクションはヒューリスティックなアプローチであり、到達不可能なオブジェクトの一部は各サイクルで再利用されない場合があります。したがって、使用可能な領域をすべて再利用するには、完全なマーク アンド スイープまたはコピー ガベージ コレクションを実行する必要がある場合があります。実際、最新のプログラミング言語 ( Javaや.NET Frameworkなど) のランタイム システムでは、これまで説明したさまざまな戦略を組み合わせたものが通常使用されます。たとえば、ほとんどのコレクション サイクルでは数世代のみを参照しますが、マーク アンド スイープが実行される場合もあり、さらにまれに、断片化に対処するために完全なコピーが実行されます。コレクターの攻撃性のこれらの異なるレベルを説明するために、「マイナー サイクル」と「メジャー サイクル」という用語が使用されることがあります。

シンプルなストップザワールドガベージ コレクターは、コレクション サイクルを実行するためにプログラムの実行を完全に停止します。これにより、コレクターの実行中に新しいオブジェクトが割り当てられず、オブジェクトが突然アクセス不能にならないことが保証されます。

この方法の欠点は、コレクションサイクルの実行中はプログラムが有用な作業を実行できないことです (「恥ずかしい一時停止」^[6]と呼ばれることもあります)。そのため、ストップザワールド ガベージ コレクションは主に非対話型プログラムに適しています。その利点は、増分ガベージ コレクションよりも実装が簡単で高速であることです。

インクリメンタルガベージ コレクターとコンカレントガベージ コレクターは、メイン プログラムのアクティビティと作業をインターリーブすることで、この中断を減らすように設計されています。インクリメンタルガベージ コレクターは、ガベージ コレクション サイクルを個別のフェーズで実行し、各フェーズ間 (場合によっては一部のフェーズ中) にプログラムの実行が許可されます。コンカレントガベージ コレクターは、プログラムの実行スタックがスキャンされるときなど、短時間を除き、プログラムの実行をまったく停止しません。 ただし、インクリメンタル フェーズの合計は、1 回のバッチ ガベージ コレクション パスよりも完了までに時間がかかるため、これらのガベージ コレクターでは合計スループットが低くなる可能性があります。

これらの手法では、メイン プログラムがガベージ コレクターに干渉しないように、またその逆の干渉が発生しないように、慎重な設計が必要です。たとえば、プログラムが新しいオブジェクトを割り当てる必要がある場合、ランタイム システムはコレクション サイクルが完了するまでプログラムを一時停止するか、ガベージ コレクターに新しい到達可能なオブジェクトが存在することを何らかの方法で通知する必要があります。

一部のコレクターは、オブジェクト内のすべてのポインター (参照) を正しく識別できます。これらは、正確な(または正確とも呼ばれる) コレクターと呼ばれ、その反対は保守的または部分的に保守的なコレクターです。保守的なコレクターは、メモリ内の任意のビット パターンがポインターとして解釈され、割り当てられたオブジェクトを指す場合、そのビット パターンはポインターである可能性があると想定します。保守的なコレクターは、ポインターの識別が不適切であるために未使用のメモリが解放されないという誤検知を生成する場合があります。これは、プログラムがポインターとして誤検知されやすい大量のデータを処理していない限り、実際には必ずしも問題になるわけではありません。有効なメモリ アドレスの範囲は、64 ビット値の範囲のごく一部になる傾向があるため、 64 ビットシステムでは一般に32 ビットシステムよりも誤検知の問題が少なくなります。したがって、任意の 64 ビット パターンが有効なポインターを模倣する可能性は低くなります。ポインターが「隠されている」(たとえば、XOR リンク リストを使用している) 場合にも、誤検知が発生する可能性があります。正確なコレクターが実用的かどうかは、通常、問題のプログラミング言語の型安全性プロパティによって決まります。保守的なガベージ コレクターが必要となる例としては、型付き (非 void) ポインターを型なし (void) ポインターに型キャストしたり、その逆を行ったりできる C 言語が挙げられます。

関連する問題として、内部ポインタ、つまりオブジェクト内のフィールドへのポインタがあります。言語のセマンティクスで内部ポインタが許可されている場合、同じオブジェクトの一部を参照できるさまざまなアドレスが存在する可能性があり、オブジェクトがガベージであるかどうかを判断するのが複雑になります。この例としては、多重継承によって基本オブジェクトへのポインタが異なるアドレスを持つ可能性があるC++言語があります。厳密に最適化されたプログラムでは、オブジェクト自体への対応するポインタがレジスタ内で上書きされている可能性があるため、このような内部ポインタをスキャンする必要があります。

トレース ガベージ コレクターのパフォーマンス (レイテンシとスループットの両方) は、実装、ワークロード、環境に大きく依存します。単純な実装や、特に組み込みシステムなどのメモリが非常に制限された環境での使用は、他の方法と比較してパフォーマンスが非常に低下する可能性がありますが、洗練された実装や十分なメモリがある環境での使用は、優れたパフォーマンスをもたらす可能性があります。^{[引用が必要]}

スループットの点では、トレースはその性質上、暗黙の実行時オーバーヘッドを必要としますが、場合によっては償却コストが非常に低く、割り当てまたはコレクションごとに1命令未満になる場合もあり、スタック割り当てよりもパフォーマンスが優れています。^[7]手動メモリ管理では、メモリの明示的な解放によるオーバーヘッドが必要であり、参照カウントでは、参照カウントの増分と減分、およびカウントがオーバーフローしたかゼロになったかのチェックによるオーバーヘッドがあります。

レイテンシの点では、単純なストップザワールド ガベージ コレクターは、ガベージ コレクションのためにプログラムの実行を一時停止します。ガベージ コレクションは任意のタイミングで実行され、任意の時間がかかる可能性があるため、リアルタイム コンピューティング、特に組み込みシステムには使用できず、対話型の使用や、低レイテンシが優先されるその他の状況には適していません。ただし、インクリメンタル ガベージ コレクターは、厳密なリアルタイム保証を提供できます。また、パーソナル コンピューターなど、アイドル時間が頻繁に発生し、十分な空きメモリがあるシステムでは、アイドル時間にガベージ コレクションをスケジュールできるため、対話型のパフォーマンスへの影響は最小限に抑えられます。手動のメモリ管理 (C++ など) と参照カウントでも、大規模なデータ構造とそのすべての子の割り当てを解除する場合に、任意の長さの一時停止が発生するという同様の問題がありますが、これはガベージ コレクションに依存せず、固定時間にのみ発生します。

手動ヒープ割り当て

• 十分な大きさの最適/最初に適合するブロックを検索する
• 無料リストメンテナンス

ガベージコレクション

• 到達可能なオブジェクトを見つける
• 移動コレクターの到達可能なオブジェクトをコピーする
• インクリメンタルコレクターの読み取り/書き込みバリア
• 移動しないコレクターのベスト/ファーストフィットブロックとフリーリストのメンテナンスの検索

2 つのケースを直接比較することは困難です。なぜなら、その動作は状況によって異なるからです。たとえば、ガベージ コレクション システムの場合、割り当てはポインタを増分するだけですが、手動ヒープ割り当ての場合、割り当てはポインタに従うだけで済みます。ただし、このサイズの分離は通常、外部の断片化を大幅に引き起こし、キャッシュの動作に悪影響を与える可能性があります。ガベージ コレクション言語でのメモリ割り当ては、（ポインタを単純に増分するのではなく）舞台裏でヒープ割り当てを使用して実装される可能性があるため、上記のパフォーマンス上の利点は必ずしもこのケースには当てはまりません。状況によっては、特に組み込みシステムでは、メモリ プールを事前に割り当て、割り当て/割り当て解除にカスタムの軽量スキームを使用することで、ガベージ コレクションとヒープ管理のオーバーヘッドの両方を回避できます。^[8]

書き込みバリアのオーバーヘッドは、データを一度だけ構築して変更しない関数型スタイルのプログラムよりも、既存のデータ構造に頻繁にポインターを書き込む命令型スタイルのプログラムで顕著になる可能性が高くなります。

ガベージ コレクションの進歩の一部は、パフォーマンスの問題に対する反応として理解できます。初期のコレクターはストップ ザ ワールド コレクターでしたが、このアプローチのパフォーマンスは対話型アプリケーションでは問題でした。増分コレクションはこの混乱を回避しましたが、バリアが必要なため効率が低下するという代償がありました。世代別コレクション手法は、ストップ ザ ワールド コレクターと増分コレクターの両方でパフォーマンスを向上させるために使用されます。そのトレードオフは、一部のガベージが通常よりも長い間ガベージとして検出されないことです。

• ガベージ コレクションのトレースは、オブジェクトの終了のタイミングが決定的ではありません。ガベージ コレクションの対象となるオブジェクトは、通常は最終的にクリーンアップされますが、それがいつ行われるか (または行われるかどうか) は保証されません。オブジェクトがメモリ以外のリソースに関連付けられている場合、その解放がネットワーク接続の終了、デバイスの解放、ファイルのクローズなど、外部から見えるプログラムの動作である場合、これはプログラムの正確性にとって問題となります。この点で決定性を提供するガベージ コレクション手法の 1 つが参照カウントです。
• ガベージ コレクションは、処理中のアルゴリズムとは関係のないプログラムの実行の一時停止を引き起こす可能性があるため、実行時間に非決定的な影響を与える可能性があります。トレース ガベージ コレクションでは、新しいオブジェクトを割り当てる要求がすぐに返されることもあれば、長いガベージ コレクション サイクルをトリガーすることもあります。参照カウントでは、オブジェクトの割り当ては通常高速ですが、参照のデクリメントは非決定的です。参照がゼロに達すると、そのオブジェクトが保持する他のオブジェクトの参照カウントをデクリメントする再帰がトリガーされる可能性があるためです。

ガベージコレクションは一般に非決定論的ですが、ハードリアルタイムシステムで使用することは可能です。リアルタイムガベージコレクターは、最悪の場合でも一定数の計算リソースをミューテータースレッドに割り当てることを保証する必要があります。リアルタイムガベージコレクターに課される制約は、通常、作業ベースまたは時間ベースです。時間ベースの制約は次のようになります。duration の各時間ウィンドウ内で、ミューテータースレッドは少なくとも時間実行できるようにする必要があります。作業ベースの分析では、ガベージコレクションアルゴリズムのリアルタイム制約として、通常 、MMU (最小ミューテーター使用率) ^{[9]が使用されます。}${\displaystyle T}$${\displaystyle T_{m}}$

JVM用のハードリアルタイムガベージコレクションの最初の実装の 1 つはMetronome アルゴリズムに基づいており、^{[10]その商用実装は}IBM WebSphere Real Timeの一部として提供されています。^[11]もう 1 つのハードリアルタイムガベージコレクションアルゴリズムは Staccato で、IBMのJ9 JVMで利用できます。Staccato も大規模なマルチプロセッサアーキテクチャにスケーラビリティを提供し、Metronome や、逆に特殊なハードウェアを必要とする他のアルゴリズムに比べてさまざまな利点をもたらします。^[12]

現代のマルチコアアーキテクチャにおけるリアルタイムガベージコレクションの大きな課題の1つは、同時実行スレッドが互いにブロックして予期しない一時停止を生じさせないように、非ブロッキング同時実行ガベージコレクションを設計することです。非ブロッキングリアルタイム同時実行ガベージコレクションを可能にするアルゴリズムの研究は、Microsoft ResearchのPizloらによる論文に掲載されています。^[13]

• デッドコードの除去
• マークコンパクトアルゴリズム