第 3 章 改良型 Morris アルゴリズム
3.2 提案方式
34 第3章 改良型Morrisアルゴリズム
図3.3: ヒープ中の使用中オブジェクトとごみ
last entry in o-table
o-table already marked (a)
(b)
white: non marked
need not to be pushed need to
be pushed currently being marked object
図 3.4: 印付け時のクラスタリング
「印付け中のクラスタリング」（marking time clustering）
印付け段階でごみ集めは，あるオブジェクトに印付けをするとき，オブジェクトの先頭から始 めて，後尾に向かって，それに含まれるワードの全ての Mフィールドに印を付ける．後端の 番地が，クラスタの最後端のものでないので，登録する必要が無いと判定可能であるのは，図 3.4の(a)を印付けする場合である．それは，この番地は，そのすぐ次に既に印付けされたオブ ジェクトがあるので，クラスタの最後端ではないと判断しても良い．しかし，図の(b)を印付 けする場合は番地を登録しなければならない．それは，すぐ次のオブジェクトは最終的には印 付けされるかも知れないが，(b)を登録するか否かを判定する時点では，そのオブジェクトは印 付けされていないためである．
「ソーティング前のクラスタリング」（pre-sorting clusterling）
あるオブジェクトに印付けした時点ではクラスタの最後端であるように見えて，その後に同じ クラスタのより番地が大きいオブジェクトに印付けされた場合を考える．このような順序で印 付けがされると，印付けが終了した時点で，O-表にはクラスタ最後端以外を指す番地が登録さ れていることになる．そこで，O-表を上下から挟み撃ちにするように1回走査して，そのよう なエントリを削除する．これにかかる手間が高々O(A)であるのは，明らかである．
36 第3章 改良型Morrisアルゴリズム
¶ ³
boolean isMarkrd(word *x); // xで指されたオブジェクトが印付け済み word *backend(word *x); // xで指されたオブジェクトの後端のアドレス
int otfull = FALSE; // O-表がいっぱいであるというフラグ
word *oh = O-表の先頭;
word *ot; // O-表の後尾
// オブジェクトを1つ印つけ void mark1(word *obj) {
word *w;
if (!isMarked(obj)) {
*objを印付け;
for (w = *objのポインタ成分) mark1(w);
if (!M(*(backend(obj)+1)))
*ot++ = obj; // クラスタの下端かもしれない→O-表に加える
} }
void GarbageCollector() {
word *w, *t; // 作業用変数
// 使用中オブジェクトに印付け : O(L) ot = oh;
for (w = 実行環境の根の全て) mark1(w);
// Pre-sorting clustering : O(A) w = oh;
while (w < ot) {
while (isMarked(*(w+1))) w++;
while (!isMarked(*(ot-1))) ot--;
*w = *(ot-- -1); } // 移動 ot = w;
ohからotの間をソート; // quick法なら平均でO(N log N) // Backward scanning : O(L)
t = *oh;
for (w = oh; w < ot; w++) {
*(t+1) = w; // a-link 作成
*wのクラスタに対してMorris法のSTEP1を行う;
}
// Forward scanning & relocation : O(L)
a-linkを辿りながら各クラスタに対してMorris法のSTEP2を行う;
}
µ ´
図 3.5: 改良型Morrisアルゴリズム
: in-use : garbage : a-link
Marking
Pre-sorting clusterling
forward scanning
&
relocation
O(A)
O(A)
scanning direction
a1
a3
a5
a6
a0 O-table
a0
a2
a4
a1 a2 a3 a4 a5
a6
a1 a3 a5
a6
N
a1 a3 a5 a6
Sorting O(N log N)
Backward scanning
O(A)
scanning direction
a1 a3 a5 a6
図3.6: 改良型Morrisアルゴリズムにおけるヒープの様子
3.2.2 アルゴリズムと手間の見積もり
提案方式のアルゴリズムを示しながら，その計算量を見積もる．アルゴリズムの概略を，それぞれ のフェーズの計算量と共に図3.5に，その様子の図3.2との共通部分を省略したものを，図3.6に示す．
クラスタリングを終了したら，O-表を番地の大きい順にソートする．これにかかる手間は平均 O(NlogN)に比例する時間である．一般的には，図3.3のようにクラスタが構成されるので，LÀN となる．また，ソーティングする前のO-表の順序もソーティングアルゴリズムに対して最悪のパター ンにはならないので，ソーティングのための時間は，後の実験結果が示すようにごみ集め全体の実行 時間に比べて十分小さい．
最悪の場合，つまりクラスタが全く構成されず，しかも表の並び順がソーティングアルゴリズムに 不利なパターンである場合を考える．ソーティングに使うアルゴリズムにも依るが，計算量はO(L2) となる．
その後の手間は，O-表を使ってクラスタ間を渡り歩くという点を除けば，図3.2を使って説明した 場合と同じである．
3.2.3 O- 表の溢れに対する対応
印付け段階でO-表が溢れてしまう可能性がある．その場合，ごみ集めの実行時間が急に増えてし まうことを問題としなければ，通常のMorrisのアルゴリズムを実行することで，ごみ集めを完了す ることが可能である．
38 第3章 改良型Morrisアルゴリズム