まず、用語のポイント: 「ガベージ コレクション」は人によって意味が異なり、GC スキームの中には他のものよりも洗練されたものもあります。参照カウントを GC の一種と考える人もいますが、個人的には「真の GC」は参照カウントとは別物だと考えています。
refcounts を使用すると、参照数を追跡する整数があり、refcount がゼロになるとすぐに割り当て解除をトリガーできます。これは、CPython 実装がどのように機能するか、およびほとんどの種類の C++ スマート ポインターがどのように機能するかを示しています。CPython の実装では、バックアップとしてマーク/スイープ GC が追加されるため、説明したハイブリッド設計に非常によく似ています。
しかし、参照が渡されるたびに (比較的) 高価なメモリ書き込み (さらに、スレッドの安全性を確保するためのメモリ バリアやロック) が発生するため、参照カウントは実際には非常にひどいソリューションです。C++ のような命令型言語では、マクロとコーディング規則を使用してメモリの所有権を管理することは可能ですが (難しいだけです)、Lisp のような関数型言語では、通常、クロージャでのローカル変数のキャプチャにより暗黙的にメモリ割り当てが行われるため、ほぼ不可能になります。
したがって、最新の GC への第一歩が Lisp のために発明されたとしても、驚くべきことではありません。これは「twospace アロケーター」または「twospace コレクター」と呼ばれ、その名の通り正確に機能しました。つまり、割り当て可能なメモリ (「ヒープ」) を 2 つのスペースに分割しました。すべての新しいオブジェクトは最初のスペースから割り当てられ、いっぱいになると割り当てが停止し、ランタイムは参照グラフをたどり、ライブ (まだ参照されている) オブジェクトのみを 2 番目のスペースにコピーします。ライブ オブジェクトがコピーされた後、最初のスペースは空としてマークされ、割り当てが再開され、2 番目のスペースから新しいオブジェクトが割り当てられます。満杯になった時点で、ライブ オブジェクトは最初のスペースにコピーされ、プロセスは最初からやり直します。
twospace コレクターの利点は、O(N)
作業を行う代わりに ( Nはガベージ オブジェクトの総数)、O(M)
作業のみを行うことです ( Mはガベージオブジェクトの数) 。実際には、ほとんどのオブジェクトは短時間で割り当てられてから割り当て解除されるため、これによりパフォーマンスが大幅に向上する可能性があります。
さらに、twospace コレクターにより、アロケーター側も単純化できました。ほとんどのmalloc()
実装では、「空きリスト」と呼ばれるものを保持しています。これは、まだ割り当て可能なブロックのリストです。新しいオブジェクトを割り当てるにはmalloc()
、フリー リストをスキャンして、十分な大きさの空き領域を探す必要があります。しかし、twospace アロケータはそれを気にしませんでした。必要なバイト数だけポインタを押し上げるだけで、スタックのように各スペースにオブジェクトを割り当てただけです。
したがって、twospace コレクターは よりもはるかに高速でした。Lispmalloc()
プログラムは C プログラムよりも多くの割り当てを行うため、これは素晴らしいことでした。別の言い方をすれば、Lisp プログラムはスタックのようにメモリを割り当てる方法を必要としていましたが、有効期間は実行スタックに制限されていませんでした。つまり、プログラムがメモリを使い果たすことなく無限に成長できるスタックです。 . 実際、Raymond Chen は、GC について人々はまさにそのように考えるべきだと主張しています。ガベージ コレクションについて誰もが間違った方法で考えているという彼の一連のブログ投稿を強くお勧めします。
しかし、twospace コレクターには重大な欠陥がありました。つまり、使用可能な RAM の半分以上を使用できるプログラムはなく、残りの半分は常に無駄になっていたということです。したがって、GC 手法の歴史は、通常、プログラム動作のヒューリスティックを使用して、twospace コレクターを改善しようとする試みの歴史です。ただし、GC アルゴリズムには必然的にトレードオフが伴います。通常は、オブジェクトを個別にではなくバッチで割り当て解除することを好みます。これにより、オブジェクトがすぐに割り当て解除されない場合に必然的に遅延が発生します。
編集:フォローアップの質問に答えるために、最新の GC は一般に世代別ガベージ コレクションのアイデアを取り入れています。オブジェクトは、有効期間に基づいて異なる「世代」にグループ化され、ある世代のオブジェクトは、存続すると別の世代に「昇格」されます。十分な長さ。場合によっては、オブジェクトの有効期間のわずかな違い (たとえば、リクエスト駆動型のサーバーで、1 つのリクエストより長くオブジェクトを格納する場合) が、オブジェクトの割り当てが解除されるまでにかかる時間に大きな違いが生じることがあります。より「終身」。
malloc()
真の GC はとのレベルの「下」で動作する必要があることを正しく観察しますfree()
。malloc()
(ちなみに、とがどのように実装されているかを学ぶ価値free()
はあります。それらも魔法ではありません!) さらに、効果的な GC を実現するには、(Boehm GC のように) 保守的であり、オブジェクトを決して移動しないでください。ポインターである可能性があるもの、または何らかの種類の「不透明なポインター」タイプが必要です-JavaおよびC#は「参照」と呼びます。不透明なポインターは、オブジェクトへのポインターを更新することでいつでもオブジェクトを移動できることを意味するため、実際には割り当てシステムに最適です。生のメモリ アドレスと直接対話する C のような言語では、オブジェクトを移動することは決して安全ではありません。
また、GC アルゴリズムには複数のオプションがあります。標準の Java ランタイムには 5 つ以上のコレクター (Young、Serial、古い CMS、新しい CMS、および G1。1 つ忘れていると思いますが) が含まれており、それぞれにすべて構成可能な一連のオプションがあります。
ただし、GC は魔法ではありません。ほとんどの GC は、バッチ処理の時間と空間のトレードオフを利用しているだけです。つまり、速度の向上は通常、メモリ使用量の増加によって支払われます (手動のメモリ管理や参照カウントと比較して)。しかし、最近の RAM の低コストと比較して、プログラムのパフォーマンスとプログラマーのパフォーマンスの向上の組み合わせは、通常、トレードオフの価値があります。
うまくいけば、それが物事をより明確にするのに役立ちます!