津田の開発な日記

いったい何を開発しているのか? (RunRunDietOnline プロトタイプ build 0026)

循環参照検出（cycle detect） (2008/06/21 10:00)

リファレンスカウント方式の循環参照対応には、大別すると以下の2種類の方法がある。（参照 3章）
[1] 定期的にマーク＆スイープなどのGCを実行
[2] 循環参照を検出し、メモリ開放

（定期的に処理が重くなる）マーク＆スイープなどのGCはなんとなくやりたくないので、まずは循環参照検出処理をやってみる
循環参照検出は、参照回数をデクリメントし０に達しなかったタイミングで行うことができる。
以下に深さ優先探索による単純なプログラムを示す。

bool psDelete(CRCObjectBody *ptr, std::vector<CRCObjectBody*> &vObjBody)
{
    for(すべての子オブジェクトについて) {
        CRCObject *obj = ptr->m_childPtr[ix];
        if( obj != NULL ) {
            CRCObjectBody *child = obj->m_bodyPtr;
            vObjBody.push_back(child);    //  後で参照数を元に戻すためにオブジェクトを覚えておく
            if( -- child->m_nRef == 0 ) {
                if( (child->m_flags & CRCObjectBody::ROOT) != 0 )       //  ルートに到達
                    return true;
                if( psDelete(child, vObjBody) )
                    return true;
            }
        }
    }
    return false;
}

上記関数はルートからたどってルートまで循環するかどうかを判定するのだが、途中に循環参照があった場合にうまくいかない。
さらに、循環参照を検出したとしても、そのまま delete を呼んでしまうと、delete 処理が循環してクラッシュしてしまう。
これらの問題も対処可能だと考えられるが、参照カウント処理がますます重くなってしまう。
そもそも循環参照になる確率は低いはずなのにオブジェクト削除時に毎回チェックするのは無駄である。
そこで、循環参照候補をストックしておき、閑になったときやストックがいっぱいになったときに、GCを行う方が賢い
このようなアルゴリズムは cycle collection と呼ばれる