自己动手做 GC (1)

自己动手,丰衣足食——垃圾回收 Part 1

提示:本文所用的语法为 C++11 语法。

看来我想要做一个 Visual Novel 引擎的愿望一直没有消失。我最近见到了 nw.js,不过我对一个难以自适应的呈现器展示动态的、元素主要是位图和渲染的文字的东西抱有怀疑的态度,毕竟 CSS3 没掌握,也还不了解精髓。因此我做着第二手准备,就是开发自己的脚本引擎,以此为基础构建完整的 VN 引擎。(内容啥的……那只能看会不会遇到合适的人了。)一方面这是我的梦想之一,另一方面即使最后 VN 引擎万一冷场了,至少还给我留下一个脚本解释器作为自学编译原理的成果嘛。

闲话少说。在一个脚本解释器中,特别是动态类型的,我认为垃圾回收扮演着至关重要的角色——负责所有对象的生命周期管理。所以,在以前尝试从编译器下手和从表现层下手之后,这次要从最基础的垃圾回收器(garbage collector,GC)下手。

纵观现代的 GC,主要有两种方式:引用计数(reference counting)和标记-清除(mark and sweep)。其中,后者还衍生出如标记-压缩(mark and compact)、分代回收(generational garbage collection)等技术。

引用计数的优点在于实时性。每个对象被引用时引用计数增加1,被解除引用后引用计数减少1,计数器为0时就直接回收了。这样可以保证对象在确定不被需要的时候立即回收。缺点是频繁地计算引用计数会有轻微的性能影响,以及循环引用(例如 A-B-C-A 三元闭环)会导致无法回收的问题。采用此方式的有微软的 COM 技术、Python 语言、KiriKiri 2/KAG3 等等。

标记-清除的优点在于在空闲(idle)时间内不影响程序运行。在内存使用达到了阈值之后,先停止世界(stop the world),挂起主程序,对每个可达(reachable)对象进行标记,然后清除不可达(unreachable)的对象。缺点是,如果不进行执行优化,对象数多时在挂起的时候会产生显著的停顿。而且管理上,例如如果要压缩(移动指针)、分代(设置写屏障,write barrier),编写的难度会比较大。采用此方式的有 C# 的虚拟机(无论是微软的还是 Mono 的)、Java 的虚拟机、各大浏览器中的 JavaScript 虚拟机等等。

综合考虑,我还是选择实现一个标记-清除的 GC。(有种感觉,哪个地方漏了减少计数就糟糕了。)为此我读过一些文献,不过上面的措辞还是比较含糊。

将所有全局对象和栈上的对象标记为可达,然后以这些对象为根,进行对象遍历。遍历完成后,释放未被标记的对象。

思想很简单,实现上有两个问题。

  1. 如何保存所有的对象(因为要遍历)?
  2. 对象之间的相互引用是如何保存的?

我看完之后总是想不出这个思想在计算机中的映射是如何的。后来脑子一抽,想既然从最简单的开始实现,那就用一个数组呗。于是我们就有了一个数组。

std::vector<void *> *m_pAllObjects;

考虑到在实现中纯指针操作会很麻烦,就封装为一个结构体。

struct GCRecord
{
    // 要使用的内存空间
    void *ptr;
};
std::vector<GCRecord *> *m_pAllObjects;

这样问题1就解决了。轮到问题2。先想到对象之间是 n:n 映射,所以每个引用域也必须是数组。于是改变GCRecord的结构如下。

struct GCRecord
{
    void *ptr;
    // 指向该对象的对象
    std::vector<GCRecord *> *references_in;
    // 该对象指向的对象
    std::vector<GCRecord *> *references_out;
};

为了预留分代回收和增量回收(incremental garbage collection)的实现空间,以及结合应用场景(动态类型的脚本解释器),再增加几个字段,然后添加成员函数。

struct GCRecord
{
    // 标记状态(黑白灰)
    AGC_MARK_STATE markState;
    void *ptr;
    std::vector<GCRecord *> *references_in;
    std::vector<GCRecord *> *references_out;
    // 给 ptr 分配的空间
    asize_t allocatedSize;
    // ptr 指向的类的类 ID
    unsigned long classID;

    GCRecord();
    ~GCRecord();
};

(吐槽:上面的命名方式混合了 UNIX 小写+下划线命名法、匈牙利命名法和 camelCase 命名法,写的时候随手写的,要统一啊!)

在释放阶段,只有未被标记(不可达)的GCRecord的析构函数会被调用。因此,指向其的所有对象都是不可达的,应该释放。

GCRecord::~GCRecord()
{
    for (auto r : *references_in)
    {
        delete static_cast<GCRecord *>(r);
    }
    // destructor = find_destructor_by_classid(this->classID);
    // destructor(this->ptr)
    free(this->ptr);
    delete references_out;
    delete references_in;
}

OK,感觉这就是所需的数据结构了。那么接下来来构造一个简单的标记-清除回收器。思想很简单,标记+清除即可。

class PlanC
{

public:

    // 初始化成员
    static void Initialize();
    // 释放成员
    static void Uninitialize();

    // 收集 = 标记+清除
    static void Collect();

    // 在堆上分配内存(不在根中)
    static void *AllocHeap(asize_t size);
    // 在全局对象堆上分配内存(在根中)
    static void *AllocGlobal(asize_t size);

private:

    // 标记
    static void Mark();
    // 清除
    static void Sweep();

};

初始化和释放就太简单了,执行该执行的操作即可。现在来看看标记的过程。

void PlanC::Mark()
{
    queue<GCRecord *> records;

    // 全局对象
    for (auto iter : *m_pGlobalSet)
    {
        if (iter)
        {
            records.push(iter);
        }
    }
    // 当前的栈环境
    for (auto iter : *m_pRuntimeStack)
    {
        if (iter)
        {
            records.push(iter);
        }
    }

    // 以下就是经典的非递归的图的广度遍历啦
    asize_t xs = records.size();
    while (xs > 0)
    {
        GCRecord *rec = records.front();
        // 标记为已经遍历(黑色)
        rec->markState = AGC_MARK_BLACK;
        records.pop();
        xs--;
        for (auto r2 : *rec->references_out)
        {
            // 灰色和白色都是不用回收的对象
            if (r2->markState != AGC_MARK_BLACK)
            {
                records.push(r2);
                xs++;
            }
        }
    }
}

标记完毕之后就是清除。

void PlanC::Sweep()
{
    GCRecord *p;
    unsigned int c = m_pAllObjects->size();
    for (auto iter = m_pAllObjects->begin(); c > 0;)
    {
        // 过滤空指针
        if (*iter)
        {
            if ((*iter)->markState == AGC_MARK_WHITE)
            {
                // 由于 iter 即将无效,这里需要保存其指向的位置(类型是 GCRecord *)
                p = static_cast<GCRecord *>(*iter);
                m_uAllocatedSize -= p->allocatedSize;
                // 然后调用析构函数释放空间
                delete p;
                iter = m_pAllObjects->erase(iter);
                c--;
            }
            else
            {
                // 将处理过的对象标记为未被遍历(白色)
                (*iter)->markState = AGC_MARK_WHITE;
                // vector::erase() 的陷阱
                // http://blog.csdn.net/yang3wei/article/details/7589344
                iter++;
                c--;
            }
        }
        else
        {
            // 对于空指针,不需要执行操作
        }
    }
}

在附上的代码中漏了重置状态为AGC_MARK_WHITE的那一行。

最后的PlanC::Collect()函数是二者的综合。

void PlanC::Collect()
{
    PlanC::Mark();
    PlanC::Sweep();
    // 利用 vector::swap() 释放 vector 不自动释放的空间
    // http://www.cnblogs.com/viviman/archive/2012/10/29/2775104.html
    ClearVector(*m_pAllObjects);
}

至此一个思想简单、实现简单的标记-清除 GC 就完成了,在不考虑增量回收、写屏障等等的情况下。来实测一下。

#include <iostream>

int main()
{
    PlanC::Initialize();
    std::cout << "Ready.\r\n";
    getchar();
    for (auto j = 0; j < 3; j++)
    {
        std::cout << "Begin!\r\n";
        for (auto i = 0; i < 10000; i++)
        {
            PlanC::AllocHeap(100 * 1024);
        }
        std::cout << "Filled.\r\n";
        getchar();
        PlanC::Collect();
        std::cout << "Collected.\r\n";
    }
    getchar();
    return 0;
}

上面的代码会分配大约 990 MB 的内存,所以请内存不足的同学谨慎运行。

有细心的同学可能会注意到,在PlanC::Sweep()中有一行:

m_uAllocatedSize -= p->allocatedSize;

这是一个可调的内存阈值。在完整的代码中,设置了一个内存阈值,当分配的内存即将超过阈值时强制垃圾回收。可以将m_uAllocatedSize设置为512 * 1024 * 1024(512 MB),在运行上面的代码时会触发超过3次垃圾回收。(那是自然……)


现在问题来了。试着运行并观察现象的同学可能会发现,运行结束后并没有像料想的那样收回全部内存,而是会剩下一些。

我的实验数据如下。

  1. Win32,三次回收(j = 3)。内存阈值 2 GB 时剩余大约 60 MB,阈值 512 MB 时候剩余大约 30 MB。
  2. Win32,单次回收(j = 1)。内存阈值 2 GB 时剩余大约 90 MB。
  3. x64,三次回收(j = 3)。内存阈值 512 MB 时剩余大约 90 MB。

大约也可以看出,这是某些指针域未释放的缘故。不过目前还没找到原因。


现在的代码中还存在问题。

  • GCRecord::~GCRecord()中未判明指针的有效性。当 A->B->C 这样的情况发生时,如果 B 先被释放了,那么在释放 C 时就会发生一个无效指针的错误。(实际上,在遍历的时候每个 GCRecord 是独立加入的,在 Sweep() 中也不进行耦合处理,所以实际上每个 GCRecord 被单独销毁,不会影响其他的 GCRecord
  • 压力小于10000的时候回收的过程就有明显的停顿感了。这是有待增量回收解决的。

日后分解吧!


附件:完整(?)代码

分享到 评论