自己动手，丰衣足食——垃圾回收 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。（有种感觉，哪个地方漏了减少计数就糟糕了。）为此我读过一些文献，不过上面的措辞还是比较含糊。
将所有全局对象和栈上的对象标记为可达，然后以这些对象为根，进行对象遍历。遍历完成后，释放未被标记的对象。
思想很简单，实现上有两个问题。
- 如何保存所有的对象（因为要遍历）？
- 对象之间的相互引用是如何保存的？
我看完之后总是想不出这个思想在计算机中的映射是如何的。后来脑子一抽，想既然从最简单的开始实现，那就用一个数组呗。于是我们就有了一个数组。
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次垃圾回收。（那是自然……）
现在问题来了。试着运行并观察现象的同学可能会发现，运行结束后并没有像料想的那样收回全部内存，而是会剩下一些。
我的实验数据如下。
- Win32，三次回收（
j= 3）。内存阈值 2 GB 时剩余大约 60 MB，阈值 512 MB 时候剩余大约 30 MB。 - Win32，单次回收（
j= 1）。内存阈值 2 GB 时剩余大约 90 MB。 - x64，三次回收（
j= 3）。内存阈值 512 MB 时剩余大约 90 MB。
大约也可以看出，这是某些指针域未释放的缘故。不过目前还没找到原因。
现在的代码中还存在问题。
GCRecord::~GCRecord()中未判明指针的有效性。当 A->B->C 这样的情况发生时，如果 B 先被释放了，那么在释放 C 时就会发生一个无效指针的错误。（实际上，在遍历的时候每个GCRecord是独立加入的，在Sweep()中也不进行耦合处理，所以实际上每个GCRecord被单独销毁，不会影响其他的GCRecord。- 压力小于10000的时候回收的过程就有明显的停顿感了。这是有待增量回收解决的。
日后分解吧！
附件：完整(?)代码