Garbage Collection

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも貢献。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれない。

前回のテーマは JIT。今回のテーマは Garbage Collection。

参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
  - 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
  - Pull Request 等お待ちしております。

GC は特別なことはしていない、というよりむしろ複雑なことはせずに、シンプルにしました。一番の目的はリソース管理というのも勿論あるものの、フリー・オブジェクトのキャッシングにある。malloc/free の回数を減らす。これが結構パフォーマンスに影響する。

実現手法

マーク・アンド・スイープ

ストップ・ザ・ワールドのマーク・アンド・スイープで、一旦全ての処理を止めて GC する。（あえて Kinx の）疑似コードであらわすと次のような感じ。

function mark(p) {
    // Stop the recursive check
    return if (p.mark);
    p.mark = true;

    // Check the mark recursively
    p.innerObjects.each(mark);
}

function markAndSweep(stack, context) {
    // Initialization
    context.aliveList.each(&(p) => { p.mark = false; });

    // Mark
    stack.each(mark);

    // Sweep
    context.aliveList = context.aliveList.filter(&(p) => {
        if (!p.mark) {
            context.deadList.push(p);
        }
        return p.mark;
    });
}

マーク

まず、マークと呼ばれるフェーズで生きているオブジェクト全てにマークを付けていく。ここでマークを漏らすと生きているのに回収されてしまっておかしくなるので漏らさないように。例のレキシカル・スコープや、関数オブジェクトに括り付いたフレーム等も全て対象。

マークの際のルートとなるのはスタック。スタック上のオブジェクトをルートに参照を全て辿って到達するオブジェクトに対し、片っ端からマークしていく。オブジェクトは循環参照しているケースがあるので、一度マークを付けたら次にまた到達したときには何もしないようにガードしておく。

また、Kinx ではスタック以外のルートとして以下がある。

独立して保持している例外オブジェクト。
正規表現リテラルの管理リスト。

晴れて全てのオブジェクトにマークが付いたら、スイープのフェーズに入る。

スイープ

オブジェクトは全て alive リストと dead リストで管理されている。ただし、alive の方は線形リスト、dead の方はベクターである。

なぜなら、alive リストは死んだオブジェクトを途中から引っこ抜いていく形で使われるのに対し、dead リストは死んだオブジェクトの再利用に使われるだけなので途中から引っこ抜くことがないため。こんな感じ。

aliveList -> obj1 -> obj2 -> obj3 -> obj4 -> obj5 -> ... -> objN -> ...
                             ~~~~ dead!
                           ↓
                                ,---> To deadList
                               /
aliveList -> obj1 -> obj2    obj3    obj4 -> obj5 -> ... -> objN -> ...
                      |               ↑
                      `---------------'

Kinx ではオブジェクト・サイズごとに全て異なるアロケーターを持ち、別々の alive/dead リストで管理することにしてある。そうすることで、オブジェクト再利用時の処理を dead リストからの pop 一発でいけるようにしている。

スイープ・フェーズでは alive リスト全てチェックし、マークの付いていないオブジェクトをリストから外して dead リストに push。

gctick

回収オブジェクトが多くないと GC するのは無駄。なので、まずは一定間隔で GC するようになっている。そのカウンタとして gctick が用意してある。一定回数インストラクションを実行したら GC がキックされる。

今後 GC 中のオブジェクト状況をプロファイルして gctick の値をコントロールしようとは思っている。

雑感

本来管理すべきリソースはメモリだけではない。ファイル・ディスクリプタやソケット等 open/close が伴うものは適切にリソース管理しなくてはならない。

C++ では RAII という機構でほぼほぼ気にせず華麗にリソース管理できるようにしていたのが、メモリ以外は try-finally で自分で管理する必要性が出てきているのはもしかして退化なのでは？、といささか感じなくもない。

C++

std::unique_ptr<FILE, decltype(&fclose)> fp(fopen(filename, "r"), fclose);

に対して、

Kinx

function open(filename, mode, func) {
    var f;
    try {
        f = new File(filename, mode);
        return func(f);
    } finally {
        f.close();
    }
}

。。。C++ のほうが簡単に書けるな。

まあ、GC するときに close するようにはしてはいるもののタイミングは予測不能。その性質上、予測不能でも問題ないものにしか適用できない。また、迂闊にオブジェクトが残ったりするとシステム側でリソース数に上限があったりするから、ちゃんと解放してあげないといけない。これを GC 的アルゴリズムの（予測不可能な世界の）中で実現するのは難しい。参照カウンタくらいか。

実は Kinx でも XML ドキュメント等は GC の時に解放されるが、解放するかどうかの判断は参照カウンタで実現している。XML ドキュメントは自身が管理する XML ノードから参照されているため、全ての管理対象 XML ノードがフリー状態になっていないと解放できない。したがって参照カウンタ。以下がソース。

src/extlib/kxxml.c

今後

今後、GC を改善するとしたら以下のような感じ。ただし、GC のような裏方は本来の仕事を邪魔しない程度に関わるのが筋。GC が明らかにボトルネックになっているといったケース、その機能が言語本来の機能要求を満たすのに必要、という以外、優先度を上げるべきではないだろう。

gctick コントロール
Force GC ... これは必要。
native 中の GC
インクリメンタル GC

おわりに

Garbage Collection は学術的にも奥が深く、ハマったらここだけでも相当なパワーが必要な領域。現実的な範囲で実用上の要求事項が満たせるレベルで動作させることを一番に考えてこういう実装に。

余裕ができたら高度な GC を取り入れても良いとは思うが、何事もプロファイルが重要。手を付けるならちゃんとボトルネックになってることを確認してからですね。

尚、GC 関連の処理は以下のソースにあります。

src/allocator.c

では、次は Fiber の予定。

Kinx 実現技術 - Garbage Collection