ストップ&コピーの待機領域をマークに使用してリスト出力

CEK ベースの仮想マシンにライタを追加することにします。この仮想マシンではセルの破壊走査を許しているため、循環参照を作ることができます。そのため、リスト出力で循環参照を辿ってしまって無限ループに入り込まないようにすることにします。

遅延スイープでストップ&コピーの待機領域をマークに使用してリスト出力を改良

循環参照を含む可能性があるグラフ構造を安全に走査するには、既に訪れたことがあるセルかどうかを判断できなければなりません。もしも、マーク・スイープ方式のゴミ集めを採用しているなら、ゴミ集め用のマーク・ビットをリスト出力に流用するのがスマートです。この仮想マシンが採用したストップ&コピーではマーク・ビットを使わないのでビットを割り当ててません。ところが、良くしたもので、2つの同じサイズのヒープ領域があり、一方を利用しているとき、もう一方の待機している領域が全部空いています。利用中の領域でのセルの相対位置と同じ待機位置をマークに使うことができます。さらに、このマシンの約束事で、セルは最低でも2スロットを使い、1スロット目をマークに、2スロット目をセルにつけるラベル番号の記録に使うことができます。

    (svm->heap.room + (x.p - svm->heap.live))[0].u = mark;
    (svm->heap.room + (x.p - svm->heap.live))[1].i = svmi (labeling);

ところで、ストップ&コピーの性質上、待機領域はクリアされていないため、マークに使いたいスロットにどんな値が入っているかは未定です。そのため、事前に生存領域のセルの開始位置に対応する待機領域の場所をクリアしなければなりません。

void
svmwrunmark (svm_t* svm)
{
    svmvalue_t* scan = svm->heap.live;
    svmvalue_t* room = svm->heap.room;
    while (scan < svm->heap.free) {
        room[0].u = 0;
        size_t skip = svmskip (scan[0].u, svmsize (scan[0].u));
        scan += skip;
        room += skip;
    }
}

ペアとベクタ以外の出力ではマークが不要であり、事前のセルの先頭スロット・クリアは無駄に重い処理になるので、マーク・クリアとマーキングは必要なときしかおこなわないようにします。

void
svmwrite (svm_t* svm, svmvalue_t x)
{
    long labeling = 0;

    if (svmptrok (x.u)
            && x.p >= svm->heap.live && x.p < svm->heap.free
            && (svmpairok (x.p[0].u) || svmtype (x.p[0].u) == SVMCVEC)) {
        svmwrunmark (svm);
        svmwrmark (svm, x, &labeling);
    }
    svmwrlist (svm, x);
}

クリアが終わると、マークを始めます。マーク・フェーズではマーク・スロットに書き込む値は 2 種類あります。一つ目は始めて訪れたことを示すマークで、値は 1 です。二つ目は 1 にマーク済みのセルに再び訪れたときに書き込まれるもので、値は 3 です。奇数にしてあるのは、この仮想マシンでは奇数は整数を、偶数はポインタかセルヘッダとして区別するためです。待機領域にはこの区別を無視して書き込んでも実害はないのですが、保険として区別のルールを守っています。値 1 のマークのままでマーク・フェーズが終わったセルを参照しているセルの数は一個だけであり、値 3 のマークでマーク・フェーズを終えたセルを参照しているセルは二個以上ということを示しています。ということで、出力時に値 3 でマークしてあるセルにラベルが付きます。

void
svmwrmark (svm_t* svm, svmvalue_t x, long* plabeling)
{
    if (svmptrok (x.u)
            && x.p >= svm->heap.live && x.p < svm->heap.free
            && (svmpairok (x.p[0].u) || svmtype (x.p[0].u) == SVMCVEC)) {
        svmvalue_t* mark = svm->heap.room + (x.p - svm->heap.live);
        if (mark[0].u == 3U)
            return;
        if (mark[0].u == 1U) {
            mark[1].i = svmi (*plabeling);
            (*plabeling)++;
            mark[0].u = 3U;
            return;
        }
        mark[0].u = 1U;
        if (svmpairok (x.p[0].u)) {
            svmwrmark (svm, x.p[0], plabeling);
            svmwrmark (svm, x.p[1], plabeling);
        }
        else {
            size_t n = svmsize (x.p[0].u);
            svmvalue_t* slot = x.p + 1;
            for (long i = 0; i < n; i++)
                svmwrmark (svm, *slot++, plabeling);
        }
    }
}

リスト出力のラベルが付く可能性があるのは、ペアとベクタだけです。ここで、値が 3 のマークがついているセルに出会うとラベルを付けて、マークの値を 5 に変更します。マークの値が 5 のセルに対しては、ラベル参照を出力します。ラベルを付けたときはセルの出力をおこない、参照をつけたときはセルを出力せずに抜け出します。

void
svmwrlist (svm_t* svm, svmvalue_t x)
{
    if (svmintok (x.u)) {
        printf ("%d", svmi (x.i));
    }
    /* 途中略 */
    else if (svmpairok (x.p[0].u) || svmtype (x.p[0].u) == SVMCVEC) {
        svmvalue_t* mark = svm->heap.room + (x.p - svm->heap.live);
        if (mark[0].u == 3U) {
            printf ("#%d=", svmi (mark[1].i));
            mark[0].u = 5U;
        }
        else if (mark[0].u == 5U) {
            printf ("#%d#", svmi (mark[1].i));
            return;
        }
        if (svm->symquote.p != SVMUNBOUND.p && x.p[0].p == svm->symquote.p) {
            printf ("'"); svmwrlist (svm, x.p[1].p[0]);
        }
        else if (svmpairok (x.p[0].u)) {
            svmwrpair (svm, x);
        }
        else if (svmtype (x.p[0].u) == SVMCVEC) {
            svmwrvec (svm, x);
        }
    }
    /* 途中略 */
}

もう一ヶ所、マークを配慮しないといけないところがります。ペアのリストの途中にマークがついているときは、そこでリストの出力をドット対に変更します。

void
svmwrpair (svm_t* svm, svmvalue_t x)
{
    printf ("(");
    svmwrlist (svm, x.p[0]);
    for (svmvalue_t e = x.p[1]; ; e = e.p[1]) {
        if (e.u == SVMNIL.u) {
            printf (")");
            break;
        }
        if (svmintok (e.u) || ! svmpairok (e.p[0].u)) {
            printf (" . ");
            svmwrlist (svm, e);
            printf (")");
            break;
        }
        svmvalue_t* mark = svm->heap.room + (e.p - svm->heap.live);
        if (mark[0].u == 3U) {
            /* the case of (1 . #0=(2 3 #0#)) */
            printf (" . ");
            svmwrlist (svm, e);
            printf (")");
            return;
        }
        printf (" ");
        svmwrlist (svm, e.p[0]);
    }
}

ストップ&コピーの待機領域は無駄なように感じることもありますが、この例のように、他の作業領域の割り当てなしでグラフ構造のトレースに使うことができます。