LoginSignup
14
10

More than 3 years have passed since last update.

@pseudo_foxkeh

参照カウントをベースにしたメモリ管理アルゴリズムの紹介

Last updated at Posted at 2019-06-19

前置き

ヒープ上に確保したメモリを自動的に解放する仕組みとしては、

  • ガベージコレクション（GC）
  • 参照カウント方式

の、2種類があります1。
参照カウント方式はパッと思いつく利点として、

  • 実装が簡単（のように見える）。
  • 低レイテンシ、つまり、メモリ解放時にプログラムが停止する時間が短い。
  • 不要となったオブジェクトを速やかに解放してくれる（期待されたタイミングでデストラクタが呼び出される）。

欠点として、真っ先に上がるのは循環参照を回収できないことでしょう。
C++ の shared_ptr や Rust の Rc および Arc では弱参照を使ってある程度この問題を解決しようとしていますが、根本的な解決にはなりません。例えば、循環参照を含む片方向連結リストの場合、弱参照は何の役にも立ちません。

Partial Mark and Sweep という手法を使えば、循環参照問題を解決できます。Qiita にはまとまった情報が無かったようなので、ここに書き残しておきます。なお、この方法は Python で利用されているようです。

参照カウント方式とは

まあ、なんというかここまで話してきて、そこからかよって感じですが念のため話しておきましょう。

class Cell {
    constructor(name) {
        this.name = name;  // デバッグ用
        this.next = null;
        this.refCount = 0; // 参照カウンタ
    }
}

片方向連結リストを javascript で実装したものです。通常の連結リストなら次ノードへのポインタだけ持っていればよいですが、参照カウンタも持たせています。参照カウンタは他のノードから参照されると増えていきます。

function appendLink(from, to) {
    from.next = to;
    incRefCount(to);
}

function incRefCount(cell) {
    cell.refCount++;
}

こんな感じです。逆にリンクが解消されたときは参照カウントが減ります。

function removeLink(cell) {
    if(cell.next) {
        decRefCount(cell.next);
    }
    cell.next = null;
}

function decRefCount(cell) {
    cell.refCount--;
    if(cell.refCount === 0) {
        removeLink(cell);
        reclaim(cell);
    }
}

function reclaim(cell) {
    // なんやかんややってメモリを回収（解放）する関数のつもり
    //（もちろん javascript でそんな芸当はできない）
    console.log(cell.name + ' を解放しました。');
}

オブジェクトが回収（解放）されるときは当然リンクも解消されますので、decRefCount 関数内で参照カウントが 0 になったとき（＝解放が決定したとき）は removeLink 関数を呼び出します。これにより連鎖的に解放を行うことができます。

const root = new Cell('root');
const a = new Cell('a');
const b = new Cell('b');
appendLink(root, a);
appendLink(a, b);
removeLink(root);

// 出力
// b を解放しました。
// a を解放しました。

これが非常に単純に実装した参照カウント方式です。さて循環参照の場合はどうなるか一応見てみましょう。

const root = new Cell('root');
const a = new Cell('a');
const b = new Cell('b');
appendLink(root, a);
appendLink(a, b);
appendLink(b, a); // この行だけ追加。（a → b → a と循環参照になっている）
removeLink(root);

// 出力

予定通り解放されません。

Partial Mark and Sweep

Rafael Dueire Lins さんが考案した手法です。

  1. 循環参照を回収するんだったら、Mark and Sweep をすればいいじゃない！
  2. でも Mark and Sweep は停止時間が…。
  3. なら、基本は参照カウント方式を使って、循環参照が疑われるときだけ Mark and Sweep をしたら両方のいいとこどりができるね！

発想は大体こんな感じみたいです。
以下、また javascript で疑似的なコードを書いていきたいと思います。が、さすがに文章とコードだけだとイメージが湧きづらいと思ったので、Slides.com でスライドを作ってみました（→資料スライド）。多分スライドを見ながらの方が分かりやすいと思いますので見てやってください。

循環参照が疑われるオブジェクトとは

A、B、C、D はそれぞれオブジェクトを表しています。矢印が参照を表します。オブジェクトの側にある数字は参照カウントを表します。


参照カウントを減らしたときに、参照カウントが 1 以上の場合は、循環参照になっている可能性があると言えます。逆に言えば、参照カウントが 0 ならば、その場で回収してしまえるわけで、回収できない＝循環参照を疑う、となります。

const suspectedList = []; // 循環参照の疑いがあるオブジェクトのリスト

const COLOR = {
    BLACK: Symbol('black'), // アクティブなオブジェクト
    WHITE: Symbol('white'), // 回収候補のオブジェクト
    GRAY: Symbol('gray'), // 循環参照をチェック中のオブジェクト
    PURPLE: Symbol('purple'), // 循環参照の疑いのあるオブジェクト
};

class Cell {
    constructor(name) {
        this.name = name;
        this.next = null;
        this.refCount = 0; // 参照カウンタ
        this.color = COLOR.BLACK; // color プロパティの追加
    }
}

function decRefCount(cell) {
    cell.refCount--;
    if(cell.refCount === 0) {
        removeLink(cell);
        reclaim(cell);
    } else {
        cell.color = COLOR.PURPLE;
        console.log(cell.name + ' は循環参照が疑われるため、紫色にマークします。');
        suspectedList.push(cell);
    }
}

循環参照の疑いがあるオブジェクトに対して、試験削除を行う

先ほどの図では、A と B と C が循環参照になっていました。この時もし A が削除されると、B、C も参照カウントが 0 になり、削除されることは分かると思います。現時点ではただの「疑い」ですので、実際に削除するわけにはいきませんが、削除をシミュレートして本当に循環参照しているか確かめてみよう、というのが試験削除です。

function checkSuspected() {
    while(suspectedList.length > 0) {
        const cell = suspectedList.pop();
        if(cell.color === COLOR.PURPLE) {   // 疑わしいオブジェクトそれぞれに対し、以下のステップを実施
            paintGray(cell);
            scanGray(cell);
            collectWhite(cell);
        }
    }
}

試験削除は
1. PaintGray
2. ScanGray (PaintBlack)
3. CollectWhite
というステップに分かれます。

PaintGray

function paintGray(cell) {
    if(cell.color !== COLOR.GRAY) {
        console.log(cell.name + ' を灰色にマークします。');
        cell.color = COLOR.GRAY;
        // cell.refCount--; と、しないことに注意
        if(cell.next) {
            cell.next.refCount--;
            paintGray(cell.next);
        }
    }
}

循環参照を調べているオブジェクトを灰色にマークしていきます。また next が存在するときは参照カウントを減らしていきます（削除のシミュレート）。PaintGray は再帰関数となっており、全てのノードをたどると終了し、次のステップ、ScanGray に移ります。

ScanGray

function scanGray(cell) {
    if(cell.color === COLOR.GRAY) {
        if(cell.refCount > 0) {
            paintBlack(cell);
        } else {
            console.log(cell.name + ' を白色にマークします。');
            cell.color = COLOR.WHITE;
            scanGray(cell.next);
        }
    }
}

灰色のオブジェクトかつ、参照カウントが 0 のものを白くマークしていきます。白いオブジェクトは回収候補となります。また、参照カウントが 1 以上のものは外部から参照があるため、削除できません。このオブジェクトおよびこのオブジェクトの子孫要素を削除対象から外し、減らしてしまった参照カウントを戻します。そのための関数が PaintBlack です。

function paintBlack(cell) {
    if(cell.color !== COLOR.BLACK) {
        console.log(cell.name + ' を黒色にマークします。');
        cell.color = COLOR.BLACK;
        if(cell.next) {
            cell.next.refCount++;
            paintBlack(cell.next);
        }
    }
}

PaintBlack は PaintGray の反対のことを行う関数です。
ScanGray および PaintBlack が終了したら、最後のステップ、CollectWhite に移ります。

CollectWhite

function collectWhite(cell) {
    if(cell.color === COLOR.WHITE) {
        cell.color = COLOR.BLACK; // 循環参照の場合、色を変えておかないと collectWhite が無限ループする
                                  // ここで色を変えてもこの関数内にある reclaim で回収されるため問題ない
        if(cell.next) {
            collectWhite(cell.next); // オブジェクトが回収されてしまうと子要素にアクセスできなくなるため、
                                     // 先に子要素から回収していく。
        }
        reclaim(cell);
    }
}

ここは白くマークされたオブジェクトを回収するだけです。

まとめ

いかがでしたでしょうか？意外と単純だったと思います。メモリのオーバーヘッド（参照カウンタ分と色分け分）がありますが、そこに目をつぶればレイテンシもそんなに高くなさそうだし十分に使えそうという印象になるのではと思います。
しかし、並行/並列処理を考慮するとまた話が違ってきます。参照カウントの増減はアトミックに行う必要がありますし、Partial Mark and Sweep ではフルの Mark and Sweep よりも短い期間になるでしょうが、やはりプロセスを止める必要があります。参照カウントが減るたびに試験削除を実施していたら、レイテンシもスループットもひどいものとなるでしょう。かと言ってまとめて試験削除を行うと、「不要となったオブジェクトを速やかに解放してくれる」という参照カウント方式の利点を損なうことにもなりかねません。この辺りの難しさが、この方式が主流にならない理由なのかなと思っています（個人的な推測です、一般的にどう言われているか、思われているかは分かりません）。

全ソースコード（スライドと同じ状態を作ります）

const suspectedList = []; // 循環参照の疑いがあるオブジェクトのリスト

const COLOR = {
    BLACK: Symbol('black'), // アクティブなオブジェクト
    WHITE: Symbol('white'), // 回収候補のオブジェクト
    GRAY: Symbol('gray'), // 循環参照をチェック中のオブジェクト
    PURPLE: Symbol('purple'), // 循環参照の疑いのあるオブジェクト
};

class Cell {
    constructor(name) {
        this.name = name;
        this.next = null;
        this.refCount = 0; // 参照カウンタ
        this.color = COLOR.BLACK;
    }
}

class Root {
    constructor() {
        this.name = 'Root';
        this.child = [];
    }
    addLink(cell) {
        this.child.push(cell);
        incRefCount(cell);
    }
    removeLink(cell) {
        this.child = this.child.filter(e => e !== cell);
        decRefCount(cell);
    }
}

function appendLink(from, to) {
    from.next = to;
    incRefCount(to);
}

function incRefCount(cell) {
    cell.refCount++;
}

function removeLink(cell) {
    if(cell.next) {
        decRefCount(cell.next);
    }
    cell.next = null;
}

function decRefCount(cell) {
    cell.refCount--;
    if(cell.refCount === 0) {
        removeLink(cell);
        reclaim(cell);
    } else {
        cell.color = COLOR.PURPLE;
        console.log(cell.name + ' は循環参照が疑われるため、紫色にマークします。');
        suspectedList.push(cell);
    }
}

function reclaim(cell) {
    // なんやかんややってメモリを回収（解放）する関数のつもり
    //（もちろん javascript でそんな芸当はできない）
    console.log(cell.name + ' を解放しました。');
}

function checkSuspected() {
    while(suspectedList.length > 0) {
        const cell = suspectedList.shift(); // ここはもちろん pop で構いません
        if(cell.color === COLOR.PURPLE) {   // 疑わしいオブジェクトそれぞれに対し、以下のステップを実施
            paintGray(cell);
            scanGray(cell);
            collectWhite(cell);
        }
    }
}

function paintGray(cell) {
    if(cell.color !== COLOR.GRAY) {
        console.log(cell.name + ' を灰色にマークします。');
        cell.color = COLOR.GRAY;
        // cell.refCount--; と、しないことに注意
        if(cell.next) {
            cell.next.refCount--;
            paintGray(cell.next);
        }
    }
}

function scanGray(cell) {
    if(cell.color === COLOR.GRAY) {
        if(cell.refCount > 0) {
            paintBlack(cell);
        } else {
            console.log(cell.name + ' を白色にマークします。');
            cell.color = COLOR.WHITE;
            scanGray(cell.next);
        }
    }
}

function paintBlack(cell) {
    if(cell.color !== COLOR.BLACK) {
        console.log(cell.name + ' を黒色にマークします。');
        cell.color = COLOR.BLACK;
        if(cell.next) {
            cell.next.refCount++;
            paintBlack(cell.next);
        }
    }
}

function collectWhite(cell) {
    if(cell.color === COLOR.WHITE) {
        cell.color = COLOR.BLACK; // 循環参照の場合、色を変えておかないと collectWhite が無限ループする
                                  // ここで色を変えてもこの関数内にある reclaim で回収されるため問題ない
        if(cell.next) {
            collectWhite(cell.next); // オブジェクトが回収されてしまうと子要素にアクセスできなくなるため、
                                     // 先に子要素から回収していく。
        }
        reclaim(cell);
    }
}

/**
 * 初期化
 * 
 */
const root = new Root();
const a = new Cell('A');
const b = new Cell('B');
const c = new Cell('C');
const d = new Cell('D');
const e = new Cell('E');
const f = new Cell('F');
const g = new Cell('G');
const h = new Cell('H');

root.addLink(a);
root.addLink(d);
root.addLink(f);
root.addLink(g);

appendLink(a, b);
appendLink(b, c);
appendLink(c, a);

appendLink(d, e);
appendLink(e, c);

appendLink(f, g);
appendLink(g, h);

/**
 * リンクの除去
 */
root.removeLink(a);
root.removeLink(d);
root.removeLink(g);

console.log('以下は、循環参照の疑いがあるオブジェクト');
for(const cell of suspectedList) {
    console.log('  ' + cell.name);
}
/**
 * 試験削除の実施
 */
console.log('試験削除の実施');
checkSuspected();

  1. 参照カウント方式は GC に関する資料では、ほとんどの場合（全てかも？） GC の一種とされています。しかしながら、こちらや「「リファレンスカウント式のGC」は、IT界ではGCと認識されていないのだろうか?」などを見ると、参照カウント方式を GC に含めない方も多くいるようなので、とりあえず「いわゆる GC 」と「参照カウント方式」の2種類としておきます。 ↩

14
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
10