Cheney’s algorithm とは

チェイニーのアルゴリズムは、1970年代のC.J.チェンイーのACM論文で最初に記述されたもので、コンピュータソフトウェアシステムにおけるガベージコレクションの追跡と停止の方法です。このスキームでは、ヒープは2つの等しい半分に分割され、そのうち1つのみがいつでも使用されます。ガーベジコレクションは、ライブオブジェクトをある半空間(from-space)から他方の空間(to-space)にコピーすることによって実行され、新しいオブジェクトが新しいヒープになります。古いヒープ全体が1つの部分で破棄されます。以前の停止とコピーのテクニックの改善です。
チェイニーのアルゴリズムは、次のようにアイテムを再利用します。
 スタック上のオブジェクト参照。スタック上のオブジェクト参照がチェックされます。 from-space内のオブジェクトを指し示すオブジェクト参照ごとに、以下の2つのアクションのうちの1つが実行されます。オブジェクトがto-spaceにまだ移動されていない場合は、to-spaceに同じコピーを作成し、次にfrom-spaceバージョンをto-spaceコピーへの転送ポインタで置き換えます。次に、to-spaceの新しいバージョンを参照するようにオブジェクト参照を更新します。オブジェクトが既にto-spaceに移動されている場合は、from-space内の転送ポインタから参照を単に更新するだけです。 to-spaceのオブジェクト。ガベージコレクタは、to-spaceに移行されたオブジェクトのすべてのオブジェクト参照を調べ、参照されたオブジェクトに対して上記の2つのアクションのいずれかを実行します。
すべての空間参照が検査され、更新されると、ガベージコレクションは完了する。
アルゴリズムはスタックを必要とせず、from-spaceとto-space以外の2つのポインタだけを必要とします:to-spaceの空き領域の先頭へのポインタと、to-spaceの次の単語へのポインタ。このため、「ツーフィンガー」コレクターと呼ばれることもあります。ツースペースを指す「2本の指」だけで、その状態を把握することができます。 2本の指の間のデータは、それが行うために残っている作業を表します。
フォワーディングポインタ(時には「ハッピーハート」と呼ばれる)は、ガベージコレクションプロセス中にのみ使用されます。すでにto-spaceにあるオブジェクトへの参照(つまり、from-space内の転送ポインタを持つ)が見つかった場合、転送ポインタと一致するようにポインタを更新するだけで、参照を素早く簡単に更新できます。
この方法は、すべてのライブ参照を参照してから参照オブジェクト内のすべての参照を使い果すことであるため、ガベージコレクションスキームをコピーする幅優先リストと呼ばれます。