c - 为什么 GC 中的白色/灰色/黑色？

Question

我正在使用一种简单的脚本语言 API 实现标记清除垃圾回收，我正在研究它，并且一直在阅读有关垃圾回收的各种实现的信息。 Lua 等 API 使用白名单、灰名单和黑名单的标记清除。

问题是，我似乎无法找到解释为什么会有这样的列表以及为什么将它们放入这些特定颜色。

在我当前的简单实现中，我只使用“死”或“活”状态。在扫掠中，死对象被删除。我正在使用 native 堆，所以我没有在我的 GC 中进行任何移动。

我用 C 写的。

// Performs a full garbage collection
void GorCollect(GorContext *ctx)
{
    Value *v, *end;
    Collectable *c, *n;

    // mark stack references
    end = ctx->stack + ctx->stackTop + 1;
    v = ctx->stack;
    while(v != end)
    {
        if (gvisgc(v) && v->v.gc) // mark if a collectable obj
            Mark(v->v.gc);
        v = v++;
    }

    // mark global references
    if (ctx->global)
        Mark((Collectable *)ctx->global); // ctx->global is a collectable obj

    // perform sweep
    c = ctx->gchead; // full list of collectable objs
    ctx->gchead = 0;
    while(c) {
        n = c->next;    
        // destroy unmarked collectable
        if (!c->marked)
            FreeCollectable(ctx, c);

        // rebuild gc list (singly-linked)
        else
        {
            c->marked = 0;
            if (!ctx->gchead)
                c->next = 0;
            else
                c->next = ctx->gchead;
            ctx->gchead = c;
        }
        c = n;
    }
}

Answer 1

灰色表示“事件但未扫描”:并非灰色 block 的所有后代都已标记为黑色。灰色在增量垃圾收集器中是必需的。它有助于标记清除 GC 在下次有机会进行一些标记时继续它正在做的事情。

如果您的 GC 是非增量的，那么在您看来您不一定需要灰色:您可以简单地始终递归遇到的任何事件 block 的所有子 block 。然而，另一个更微妙的问题是这种朴素的非增量递归算法可能会溢出堆栈。灰色也有助于将有关接下来要访问的内容的信息存储在堆中，而不是堆栈中。

即使您为此目的使用灰色，也不会阻止您保留一个 block 缓冲区以提高效率。与朴素递归实现的唯一区别是当缓冲区已满时停止更新缓冲区，如果缓冲区在满后变空，则线性扫描堆以查找灰色对象。