ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。

しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。

そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは驚きでした。

最後にクリーンアップ: つまりGCなし

最も単純なガベージのクリーンアップ方法は、タスクが終了するのを待って全てのものを一度に捨てることです。これは驚くほど便利なテクニックで、タスクを細分化する手段がある場合は特に便利です。例えば、Apache Webサーバはリクエストごとに小さいメモリプールを作成し、リクエストが完了すると、プール全体を捨てます。

右の小さいアニメーションは、ある実行中のプログラムを表しています。全体のイメージはプログラムのメモリを表します。メモリは最初真っ黒です。これはメモリが使用されていないことを示しています。明るい緑や黄色の点滅する領域は読み書きされているメモリです。色は徐々に薄れていくので、メモリがどのように使用されたかだけでなく、現在の活動も確認できます。注意深く眺めていると、メモリの一部をプログラムが無視するというパターンの出現に気付くと思います。これらの領域はガベージを示します。つまり使用されておらず、プログラムからは到達不能です。ガベージでないものは全て「ライブ」です。

プログラムの実行中は、ガベージのクリーンアップについて心配する必要もなく、プログラムは容易にメモリを使用できます。残りの例もこの単純なプログラムを使って説明していきます。

参照カウントコレクタ

もう1つのシンプルなソリューションは、リソース（この場合、メモリ内のオブジェクト）を使用する数を数えて、カウントがゼロになったら捨てるという方法です。これは既存のシステムにガベージコレクションを追加する場合に用いられる最も一般的なテクニックで、他のリソースマネージャと既存のコードベースに簡単に統合できる唯一のガベージコレクタです。Apple社はObjective-C向けにマークスイープコレクタをリリースした後、このことを思い知ることになりました。あまりにも多くの問題が発生したために、この機能を撤回し、既存のコードよりずっとうまく機能する自動参照カウントコレクタに置き換えざるを得なかったのです。

このアニメーションは先ほどと同じプログラムを表していますが、今回は、メモリ内のオブジェクトごとに参照数を数えることで、ガベージを廃棄しようとしています。赤い点滅は参照を数えていることを示します。参照カウントで非常に便利なのは、ガベージを速やかに検出できることです。時々、赤く点滅した直後に黒に転じる領域があることに気付かれると思います。

残念ながら参照カウントには多くの問題があります。一番の問題は、循環的構造を扱うことができない点です。これはごく一般的なことで、親値への参照やその逆を行うと、メモリリークを起こす循環が生成されます。また、参照カウントには過剰なオーバーヘッドがかかります。アニメーションを見ると、メモリ使用量が増えていない時でも常に赤く点滅しているのが分かりますね。最新のCPUは計算能力は早いもののメモリが遅く、カウンタはロードされてしばしばメモリに保存されます。また、こうしたカウンタの更新によって、リードオンリーのデータやスレッドセーフなデータを持つのが難しくなります。

参照カウントは償却アルゴリズムですが（オーバーヘッドはプログラムのランタイム全体にかかる）、応答時間の保証ができない偶発的に償却されるアルゴリズムです。例えば、あるプログラムが非常に大きなツリー構造で動作していて、ツリーを使用するプログラムの最後の断片がツリー全体の処理を始動させるとします。マーフィーの法則によれば、ユーザが最も遅延が起きてほしくない時にそれは必ず起こるでしょう。ですが、他のどのアルゴリズムも償却されていないので、データに依存する機能が偶然償却される可能性があります（これら全てのアルゴリズムには部分的であれ同時変動がありますが、私のちっぽけなプログラムの性能を超えており、お見せできません）。

マークスイープコレクタ

マークスイープは、参照カウントの問題の一部を排除できます。すなわち、カウントを維持する必要がないので循環的構造を容易に扱い、オーバーヘッドもあまりかかりません。

マークスイープはガベージを即座には検出できません。アニメーションを見て分かるように、赤い点滅のない時間がありますが、突然いくつもの赤い点滅が現れます。これはライブオブジェクトをマークしていることを示します。マークし終わると、メモリ全体を一掃し、ガベージ処理します。参照カウントのアプローチのように時間をかけて黒い部分が広がるのではなく、複数の領域が一気に黒くなることもアニメーションで確認できますね。

マークスイープは参照カウントよりも実装の一貫性が必要とされるため、既存システムの中に組み込むのが困難です。マークフェーズでは全てのライブデータをトラバースできる必要があり、オブジェクトにカプセル化されたデータも例外ではありません。トラバースできないオブジェクトがある場合、マークスイープをコードに組み込もうとするのは恐らく危険でしょう。マークスイープのもう1つの弱点は、ガベージを見つけるのにメモリ全体を一掃しなくてはならない点です。ガベージをあまり生成しないシステムであれば問題ではありませんが、最新の機能的なプログラミングスタイルでは大量のガベージが生成されます。

マークコンパクトコレクタ

先ほどご覧頂いたアニメーションを見てお気付きかもしれませんが、オブジェクトは決して動きません。オブジェクトがメモリに割り当てられると、メモリが黒に囲まれて分断された島々のようになっても同じ場所に存在し続けます。これから紹介する2つのアルゴリズムは全く異なるアプローチでそれを変えます。

マークコンパクトは、ただマークして解放するのではなく、オブジェクトを下の空きスペースに移すことによってメモリ処理します。オブジェクトは常に同じメモリ順のままですが（つまり、あるオブジェクトの前に割り当てられたオブジェクトは常にメモリ内の下の方にある）、破棄されたオブジェクトによってできたすき間はオブジェクトの移動によって埋められます。

オブジェクトを移動するという素晴らしいアイデアによって、新しいオブジェクトは常に使用メモリの最後に生成されることになります。これは「バンプ」アロケータと呼ばれていて、スタック割り当てと同じくらい安価ですが、スタックサイズの制限がありません。バンプアロケータを使っているシステムの中には、データを保存するのにコールスタックを使わず、ヒープ領域内でコールフレームを割り当て、その他のオブジェクトと同様に扱うものさえあります。

その他の利点としては、実践というより理論に近いかもしれませんが、このようにオブジェクトをコンパクト化する場合、プログラムのメモリアクセスパターンが改善し、最新のハードウェアのメモリキャッシュでも問題ないことです。あなたがこれを利点と考えるかは全く確信が持てませんけどね。参照カウントとマークスイープで使用されるメモリアロケータは複雑ですが、非常に優れたデバッグ機能を備えており、 非常に効率的です。

マークコンパクトは、割り当てられたオブジェクト全てに関して複数のパスを必要とする複雑なアルゴリズムです。アニメーションを見ると、ライブオブジェクトのマーク付けにより赤く点滅し、 移動先を計算する間に大量の読み書きが実行されることが分かります。その後、オブジェクトが移動され、最後にオブジェクトが移動した場所を示すために参照が固定されます。この複雑さの主な利点は、メモリオーバーヘッドが非常に低い状態で処理していることです。Oracle社のHotspot JVMは、複数の異なるガベージコレクションアルゴリズムを使用します。寿命の長いオブジェクト空間は、マークコンパクトを使用します。

コピーコレクタ

私がアニメーションを作成した最後のアルゴリズムは、最もパフォーマンスの高いガベージコレクションシステムの基礎です。マークコンパクトのようにオブジェクトを移動させるコレクタですが、驚くほどシンプルです。2つのメモリ空間を使い、コピーしたライブオブジェクトを行き来させるだけです。実際には空間は2つ以上あり、オブジェクトの異なる世代ごとに空間が使用されます。新しいオブジェクトが1つの空間に生成され、オブジェクトが存続する場合は別の空間にコピーされ、最後に寿命の長いオブジェクトが寿命の長い空間にコピーされます。ガベージコレクタが長命あるいは短命と称した場合は大抵、複数空間のコピーコレクタです。

簡潔さと順応性以外に、ライブオブジェクトだけに時間を費やすのも、このアルゴリズムの主な利点です。後から一掃またはコンパクト化しなければならないマークフェーズはありません。ライブオブジェクトのトラバーサルの間に、速やかにオブジェクトがコピーされ、壊れた参照（オブジェクトが元々あった場所）をたどることによって、オブジェクト参照が修復されます。

アニメーションを見ると、複数のガベージコレクションで、ほとんど全てのデータが、ある空間から別の空間にコピーされていることが分かります。これは、このアルゴリズムにとって最悪の状況であり、人々がガベージコレクタのチューニングを話題にする理由の1つでもあります。メモリのサイズを指定して、ガベージコレクションが開始した時点でほとんどのオブジェクトがデッドオブジェクトになっているようにアロケーションを調整できれば、安全な関数型プログラミングスタイルと高いパフォーマンスという優れた組み合わせが得られるのです。