Loading article…
コンピュータサイエンス において、マークコンパクトアルゴリズムは、到達不能なメモリ領域を解放するために使用されるガベージコレクションアルゴリズムの一種です。マークコンパクトアルゴリズムは、マークスイープアルゴリズムとチェイニーのコピーアルゴリズムを組み合わせたものと考えることができます。まず、到達可能なオブジェクトにマークを付け、次に圧縮ステップによって到達可能な（マークされた）オブジェクトをヒープ領域の先頭に移動させます。圧縮ガベージコレクションは、最新のJVM、MicrosoftのCommon Language Runtime、およびGlasgow Haskell Compilerで使用されています。
マークスイープアルゴリズムと同様の方法でヒープ内の生存オブジェクトをマークした後、ヒープは断片化されることがよくあります。マークコンパクトアルゴリズムの目的は、メモリ内の生存オブジェクトをまとめて移動し、断片化を解消することです。課題は、移動されたオブジェクトへのすべてのポインタを正しく更新することです。これらのポインタのほとんどは、圧縮後に新しいメモリ アドレスを持つことになります。ポインタの更新処理は、さまざまな方法で行われます。
テーブルベースのアルゴリズムは、1967年にハドンとウェイトによって初めて記述されました。[ 1 ]このアルゴリズムは、ヒープ内の生存オブジェクトの相対的な位置を保持し、一定のオーバーヘッドしか必要としません。
圧縮処理はヒープの下部（低アドレス）から上部（高アドレス）へと進行します。生存オブジェクト（つまり、マークされたオブジェクト）が見つかると、それらは最初に利用可能な低アドレスに移動され、再配置情報を含むブレークテーブルにレコードが追加されます。各生存オブジェクトについて、ブレークテーブルのレコードは、圧縮前のオブジェクトの元のアドレスと、圧縮後の元のアドレスと新しいアドレスの差で構成されます。ブレークテーブルは、圧縮対象のヒープ内に格納されますが、未使用としてマークされた領域に格納されます。圧縮処理が必ず成功するように、ヒープ内の最小オブジェクトサイズは、ブレークテーブルのレコードサイズ以上である必要があります。
圧縮が進むにつれて、再配置されたオブジェクトはヒープの下部に向かってコピーされます。最終的に、オブジェクトはブレークテーブルが占める領域にコピーされる必要があり、ブレークテーブルは別の場所に再配置されなければなりません。このブレークテーブルの移動（著者らはこれを「テーブルのローリング」と呼んでいます）により、再配置レコードが乱雑になるため、圧縮完了後にブレークテーブルをソートする必要があります。ブレークテーブルのソートのコストはO ( n log n ) であり、nはアルゴリズムのマーク段階で見つかった生存オブジェクトの数です。
最後に、再配置テーブルの再配置レコードを使用して、再配置されたオブジェクト内のポインタフィールドを調整します。生存オブジェクトを調べてポインタを検出し、ブレークテーブルがソートされている場合は、サイズnのソート済みブレークテーブルでO(log n ) 時間でポインタを検索できるため、全体の実行時間はO ( n log n ) となります。その後、ポインタは再配置テーブルで指定された量だけ調整されます。
O ( n log n )の計算量を回避するため、 LISP 2アルゴリズムはヒープに対して3つの異なるパスを使用します。さらに、ヒープオブジェクトは、ガベージコレクション以外では使用されない、別の転送ポインタスロットを持つ必要があります。
標準マーキングの後、アルゴリズムは次の3つのパスで進行します。
このアルゴリズムはヒープのサイズに対してO ( n )の計算量であり、テーブルベースのアプローチよりも計算量は優れていますが、テーブルベースのアプローチではnは使用される領域のサイズのみであり、LISP2アルゴリズムのようにヒープ全体の領域ではありません。ただし、LISP2アルゴリズムの方が実装は簡単です。
Compressor 圧縮アルゴリズム[ 2 ] は、現在知られている圧縮アルゴリズムの中で最も複雑度が低い。これは IBM の Java 用ガベージ コレクションを拡張したものである。[ 3 ] Compressor のシリアル版は、各オブジェクトの古いアドレスを新しいアドレスにマッピングする再配置マップを保持する (つまり、圧縮前のアドレスを圧縮後のアドレスにマッピングする)。最初のパスでは、ヒープ内のすべてのオブジェクトに対してマッピングが計算される。2 番目のパスでは、各オブジェクトが新しい場所に移動され (ヒープの先頭に圧縮される)、その中のすべてのポインタが再配置マップに従って変更される。
最初のパスにおける再配置マップの計算は、ヒープ全体を走査する必要のない小さなテーブルを使用することで非常に効率的に行うことができます。これにより、コンプレッサの計算複雑度は低く抑えられ、小さなテーブルを1回、ヒープ全体を1回走査するだけで済みます。これは、コンパクションアルゴリズムの中で既知の中で最も低い計算複雑度を表しています。
Compressorには並列バージョンもあり、複数の圧縮スレッドが連携してすべてのオブジェクトを並列に圧縮できます。また、Compressorには並行バージョンもあり、圧縮スレッドがプログラムと並行して動作し、オブジェクトがヒープの先頭に向かって移動される際に、プログラムがオブジェクトにアクセスできるように配慮されています。Compressorの並列バージョンと並行バージョンは、仮想メモリプリミティブを利用します。