【Unity优化】如何写一个C++垃圾回收器!
最近因为工作缘故，通过为一款Unity手游做性能优化，接触到一个写的很好，也是在实际中应用非常广泛的一个C++垃圾回收器————BoehmGC。这里直接引用来自维基百科的词条
Boehm-Demers-Weiser garbage collector，也就是著名的Boehm GC，是计算机应用在C/C++语言上的一个保守的垃圾回收器，可应用于许多经由C/C++开发的项目，同时也适用于其它运行环境的各类编程语言，包括了GNU版Java编译器运行环境，以及Mono的Microsoft .NET移植平台。
我之前对垃圾收集领域的经验，主要来自自研引擎的GC模块，类似Unreal Engine里基于UObject的垃圾回收。和BoehmGC相比，虽然两者原理都是差不多（无非是对二十年前基本都已成型的垃圾回收算法的实现），但毕竟只作用于一个大型系统中一个相对小而核心的模块，和BoehmGC这种系统级的库在工程规模、实现难度、代码质量上还是有着不小的差距。
当然，具体到游戏引擎这个case，具体使用哪个方案，仍然要看引擎的设计理念和技术框架。比如我们的自研引擎和UE4，因为是从底层架构到逻辑代码都基于C++实现，所以可以用一个相对轻量级的GC实现（实际上窃以为，GC即便没有也并非无法接受）。而Unity选择了对开发者相对更友好的C#语言，在底层采用BoehmGC这种相对重量级的框架也无可厚非。
本文的主旨并不在于讨论这种设计上的取舍，所以我们还是尽快进入正题————从BoehmGC源码学习如何写一个C++垃圾回收器吧！
BoehmGC中的内存分配
看到这里，你可能会有点儿不解，我们不是要谈怎么写内存回收器么，为什么要扯内存分配呢？
其实，垃圾回收和内存分配本就是一体两面，是垃圾回收器设计的时候就会考虑到的问题。接管应用的内存分配，也就拥有了“哪些内存可能需要归还给系统”这样的重要信息。
作为一个重量级的基础组件库，BoehmGC的使用方法非常简单，只需要把系统函数malloc替换为GC_malloc即可，之后你就完全不用管何时free的问题。在小型项目里，你甚至可以直接
#define malloc(n) GC_malloc(n)然后再不用管free，BoehmGC自会帮你打理好一切。
既然全盘接管了内存分配，那就必须做到以下两点，才能称得上是合格的分配器 1. 分配的效率要高 2. 尽量避免内存浪费，避免碎片化等
BoehmGC的内存分配架构
在整个内存分配链的最底部，BoehmGC通过平台相关接口来向操作系统申请内存（可能是malloc, sbrk, 或者mmap等）。为了提高效率会根据配置，每次批量申请4K的倍数大小，除了用户能使用的内存之外，还有BoehmGC内部维护的数据结构(通过GC_scratch_alloc分配)。
分配器的核心是一个分级的结构，BoehmGC把每次申请根据内存大小归类成小内存对象(Small Object)和大内存对象(Large Object)，这点和STL的分配器也比较相似。归类的依据具体来说就是，
不超过PageSize/2，也就是2048字节的对象为小内存对象
大于PageSize/2的对象为大内存对象
//heap block定义了一个页，大小为4K的倍数
struct hblk {
char hb_body[HBLKSIZE];
};对于Large Object，向上取整到4K的倍数大小，直接以整数个hblk的形式给出。而Small Object则会先申请一个hblk出来，而后在这块内存上进一步细分为Small Objects，形成free-list。
BoehmGC的内存管理策略
为了尽量减少碎片化和加速分配，BoehmGC在设计上就做了一些限制，充分体现了“物以类聚”的思想。
首先，GC管理的对象有一个最小的“粒度”，即Granule。32位上这个值是8字节，64位则是16字节。在64位环境下，即使用户申请的内存是10个字节，也会被向上调整到16字节。
一个在用的hblk如果不是属于一个large object，那就是容纳了若干个等大小的small object。
对于有一定内存分配器实现经验的开发者来说，以上两点应该都比较熟悉了，不过BoehmGC把这种“物以类聚”的设计贯彻落实得更加彻底。
对于大内存对象(large object)，按照对应的hblk数，把他们归类到若干个freelist中。具体的做法可以参考GC_hblk_fl_from_blocks和GC_allochblk_nth。
当大内存对象被垃圾回收的时候，会尝试把相邻的hblk合并，减少内存碎片。
对于小内存对象的大小分档，也不是完全按照Granule的等差数列来决定。有些临近的大小会被优化合并掉，比如系统当前有很多1024字节的闲置块，但申请1008字节的小内存对象仍然可能miss。此时用1024字节的块可能是更好的选择，适当的合并临近的block size可以优化内存分配效率。这块的做法可以参考GC_init_size_map和GC_extend_size_map。
BoehmGC的代码实现
对于很多工程问题来说，算法或者大体的思路，大家可能都是相差不多，最终的品质很大程度上取决于代码实现的功力，而BoehmGC的代码就展现了这番功力。
GC_arrays
BoehmGC把全局数据结构放在GC_arrays这个全局变量里，并定义了各个字段的快速访问方式。
struct _GC_arrays {
word _heapsize; /* Heap size in bytes (value never goes down). */
word _requested_heapsize; /* Heap size due to explicit expansion. */
ptr_t _last_heap_addr;
ptr_t _prev_heap_addr;
word _large_free_bytes;
...
mse *_mark_stack; //gc的时候用来做mark的数据结构
...
bottom_index * _top_index[TOP_SZ]; //二级页表
};
GC_API_PRIV GC_FAR struct _GC_arrays GC_arrays;
#define GC_mark_stack GC_arrays._mark_stack //mark_stack快捷访问方式
#define GC_top_index GC_arrays._top_index //top_index快捷访问方式
二级页表
每个hblk对应有一个元信息(hblkhdr)，里面存放了object类型、大小等信息，也包含GC所需要的字段比如mark数组等。
struct hblkhdr {
struct hblk * hb_next; /* Link field for hblk free list */
/* and for lists of chunks waiting to be */
/* reclaimed. */
struct hblk * hb_prev; /* Backwards link for free list. */
struct hblk * hb_block; /* The corresponding block. */
unsigned char hb_obj_kind;
/* Kind of objects in the block. Each kind */
/* identifies a mark procedure and a set of */
/* list headers. Sometimes called regions. */
unsigned char hb_flags;
...
word hb_marks[MARK_BITS_SZ]; /*用来放mark信息的数组*/
}typedef struct bi {
hdr * index[BOTTOM_SZ]; /* BOTTOM_SZ = 2**10 */
struct bi * asc_link;
struct bi * desc_link;
word key; /* high order address bits. */
# ifdef HASH_TL
struct bi * hash_link; /* Hash chain link. */
# endif
} bottom_index;而计算hdr的代码为了性能考虑，也多用宏和内联函数来实现，
/*LOG_HBLKSIZE = 12, BOTTOM_SZ = 10*/
#define HDR_FROM_BI(bi, p) \
((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
# define GET_HDR_ADDR(p, ha) \
do { \
REGISTER bottom_index * bi; \
GET_BI(p, bi); \
(ha) = &HDR_FROM_BI(bi, p); \
} while (0)
总结
在3A游戏引擎这种大工程里，一般都不会直接用操作系统自带的内存分配函数例如malloc等。标准做法是写一套自己的内存分配类/函数接管所有内存分配，所以BoehmGC的源码其实也是一个非常好的学习例子。
下一篇来学习BohemGC的垃圾回收实现。