OLD
2.4. 世代別ごみ集めとその関連研究 27
NEW NEW
for ODD cycle for EVEN cycle
OLD space
evacuation path
(a) Original Bucket Brigade technique
NEW
OLD space
(b) Wilson’s simplified version
water mark NEW
water mark
for ODD cycle for EVEN cycle
図 2.11: ShawとWilsonの世代別ごみ集めのヒープレイアウト
する時に，最終的なコピー先でない場所にポインタ値を補正しながらコピーし，後で最終的な目的地 にブロック移動している点にある．
このごみ集めは，MLという言語一般の特性から以下のような仮定と対策を講じている．
• MLでは書き換えはめったに起きない．
→書き換えが起きる度に，ポインタの始点と終点をリストに記録する．
• MLではコンパイルされたコードでも，オブジェクトの確保が30命令に1回起きるほど頻繁で ある．
→freeの使い切りはポインタの検査でなくページフォールトで検出する．
この方式では，最近生成されたオブジェクトもすぐにOLDへ終身雇用されてしまう，つまり十分 時間が経っていないオブジェクトを終身雇用してしまうので，(c)〜(e)の全体的なごみ集めが比較的 短い周期で必要になることが予想される．
ShawとWilsonの実時間ごみ集め
この論文では，未成熟オブジェクトの終身雇用を避ける問題を，Ungerの方式のようなオブジェク ト毎の世代カウンタを設けることなしに解決することに主眼を置いている．図2.11の(a)に示すShaw のBucketBrigade[64]は，Libermanらの方式を古い領域の前につけたような構成になっており，小 さい半領域のサイズと段数を調整することで，終身雇用までの確保時間を調節できる. Wilsonはこれ の改良として，調査結果から得た「せいぜい1回のごみ集めを生き延びれば終身雇用しても良い．」と いう経験則から，指標（water mark）を導入してShawの方式を簡略化した(b)のような構成を提案 した．指標はNEWから救助されたオブジェクトと，一回ごみ集めを生き延びたオブジェクトを区別 するために設定され，図で指標より下のオブジェクトで生き延びたものが，古い領域に救助される．
OLD
A-map
evacuate
ds
dt d0
d1
semi-space0
semi-space1
図2.12: 小出らの世代別ごみ集めのヒープレイアウト
世代間ポインタの追跡には，ページングハードウエアを使った割り出しでカード（32ワード）毎に 古い領域への書き込みを記録し，ごみ集め時に書き込まれたカードの走査を行って，古い領域以外を 指している世代間ポインタの補正を行っている．
小出らの世代別ごみ集め
生成順序を保存する複写式ごみ集め[41]を元にした，世代別ごみ集めが提案されている．図2.12に 示すようなヒープレイアウトになる．何世代かのごみ集めを生き抜いたオブジェクトが半領域0に救 助されたときに，終身雇用される．A-mapと呼ぶ領域に，印付けと並行して古い領域も含めた使用中 オブジェクト全体のアドレスを収集し，古い領域内の世代間ポインタの補正や，世代間ポインタの指 し先の最大値を求める．remember setや間接ポインタのようなデータ構造を使わない代わりに，世 代間ポインタと参照先の対が古い領域で閉じるように，半領域0への救助の際に新しい領域と古い領 域の境界線d0を設定する．
この方式では，ポインタの書き換えの際のオーバヘッドが無い代わりに，古い領域のオブジェクト へも印付けが必要である．
2.5 従来の世代別ごみ集めの問題点と第 3 章と第 4 章で解決する問題
概観した世代別ごみ集めでは，小出らの方式を除いて，次のような問題がある．
• 世代間ポインタを管理するためのデータ構造が各図に示した領域とは別に必要である．
2.6. この章のまとめ 29
• 終身雇用問題の解決のための世代管理で，複雑なデータ構造を用いたり，カウンタの管理など のオーバヘッドが大きい．
• また，論文では触れられていないものがあるが，AppelとLibermanら以外の方式では，全体 的なごみ集めは印掃法で行うものと思われる．
第3章では，印掃式ごみ集めで必須であると思われていた，ヒープ全体の走査を省くことができる 印掃法滑り圧縮ごみ集めの，アルゴリズムと実装について述べ，評価を行う．
第4章では，第3章の方式を拡張して，滑り圧縮の生成順序保存という特性を利用した，オーバ ヘッドが低い世代別ごみ集めを構成する方法と，その実装について述べ，評価を行う．
2.6 この章のまとめ
この章では，ごみ集めの問題を定式化し，印掃法と複写法というごみ集めの2つの基本手法を説明 し，それぞれについての従来の研究成果を紹介した．そして，世代別ごみ集めの問題を定式化し，従 来の手法を紹介した．