之前学习了 Lua 的 Table 和协程，对 Lua 中另一个重要模块 GC 还有很多疑问，这次就来学习一下。
GC 简介与策略分类
在计算机科学中，垃圾收集(GC)是一种自动内存管理形式。垃圾收集器尝试回收程序分配但不再引用的内存；这样的内存被称为垃圾。
追踪(Tracing)
Tracing 的策略简单讲就是使用一些根对象来遍历所有的引用，可以访问到的就不是垃圾，不能访问到的就是需要回收的垃圾。虽然这个说起来和实现起来很简单，但是想要使其有较好的性能并不是一件很容易的事情。Tracing 有很多需要考虑的问题，例如收集的周期(步进 Pace)是什么，是按照时间片还是按照已经分配过的内存，是否会出现为了收集垃圾程序执行出现明显卡死现象等。
之后用到的 Lisp 和 Lua 的例子都以 Tracing 策略为主。
引用计数(Reference counting)
引用计数垃圾收集是每个对象都有一个对它的引用数的计数。垃圾通过引用计数为零来标识。对象的引用计数在创建对它的引用时增加，在引用被销毁时减少。当计数达到零时，对象的内存被回收。
循环引用
如果有两个对象相互引用，就会导致它们的引用计数永远大于等于 1 ，它们永远不会被回收。对于这个问题，一般有两种解决方案。一种比较直观，直接检测是否出现循环，cpython 就使用的这种方法；另一种就是引入弱引用的概念。
弱引用不会增加引用计数，而且指向的对象可能是已经被回收的，因此可以简单地检测出是否失效，而不是保持引用悬垂。
额外空间开销
明显地，如果使用引用计数的策略就需要额外的空间来存储计数。有的是存在对象中，有的是存在一个表之中。在一些语言例如 objective-c 中，它们将引用计数存在指针地址未使用的位当中（我认为这对不同处理器间可移植性有影响）。
额外时间开销
例如如果使用for item in something的方法遍历，在每个循环开始都有rc++每个结尾都有rc--，优秀的 GC 应该把这个消除掉。
并行
如果需要编写并行代码则需让 rc 的操作具有原子性，最重要的一点是它们不可以是全局变量了。
自动引用计数(Automatic Reference counting)
自动引用计数无需运行时，会在编译阶段处理引用计数并实现内存管理，但是难以处理循环引用的问题。神奇的 Rust 较好地解决了这个问题，方法还是使用弱引用，可以看 Arc 的实现：
Breaking cycles with Weak
The downgrade method can be used to create a non-owning Weak pointer. A Weak pointer can be upgraded to an Arc, but this will return None if the value stored in the allocation has already been dropped. In other words, Weak pointers do not keep the value inside the allocation alive; however, they do keep the allocation (the backing store for the value) alive.
A cycle between Arc pointers will never be deallocated. For this reason, Weak is used to break cycles. For example, a tree could have strong Arc pointers from parent nodes to children, and Weak pointers from children back to their parents.
不过，无论是朴素的引用计数还是自动引用计数，一旦引入弱引用就可能增加代码编写者的心智负担和精神内耗，让垃圾回收没有那么省心省力。
逃逸分析(Escape analysis)
这个比较好理解，它的原理就是将一些不必要的堆分配变成栈分配，例如在一个函数之中，如果一个对象不会被传递到外部，Escape analysis 就可以将它从堆分配变为栈分配从而减少所需要的垃圾收集量。
ulisp GC
这是一种很 naive 的 GC ，采用的是最为朴素的 mark-and-sweep 中的双色标记法。
首先调用 markobject() 函数对所有还能够访问的对象进行标记
ulisp 是一种广泛用于嵌入式的 lisp 方言
void markobject (object *obj) {
MARK:
if (obj == NULL) return;
if (marked(obj)) return;
object* arg = car(obj);
unsigned int type = obj->type;
mark(obj);
if (type >= PAIR || type == ZERO) { // cons
markobject(arg);
obj = cdr(obj);
goto MARK;
}
}
这里的 cons 是一种广义表，由两个指针组成，car 提取第一个指针，cdr 提取第二个指针。上面这个函数用了一种不够美观的方式消除了部分递归。
这里的 mark(x) 宏利用内存对齐使用了一个技巧：
#define mark(x) (car(x) = (object *)(((unsigned int)(car(x))) | 0x0001))
因为内存对齐到偶数位，所以最低位为 0 ，将 car(x) 的最低位置为 1 的标记操作是合理的，而且节约了内存。
sweep() 函数则用于清理对象。
void sweep () {
Freelist = NULL;
Freespace = 0;
for (int i=WORKSPACESIZE-1; i>=0; i--) {
object *obj = &Workspace[i];
if (!marked(obj)) myfree(obj); else unmark(obj);
}
}
inline void myfree (object *obj) {
car(obj) = NULL;
cdr(obj) = Freelist;
Freelist = obj;
Freespace++;
}
这里的清理没有使用 free 等库函数是因为 ulisp 一般用于嵌入式环境中，它的内存管理就是管理一个保存对象地址的静态大数组，全局变量 Freelist 指向数组第一个为空的地方，Freespace 表示还剩余多少空间。
ulisp 的 gc 周期设置也比较朴素，每次 eval 被调用时检测一下剩余内存空间，如果小于 20 个对象的大小就垃圾收集。
if (Freespace < 20) gc(form, env);
Lua GC
Lua GC 也采用了 mark-and-sweep 的策略，但是它使用的不再是双色标记，而是更加优秀的三色标记法。
Lua 5.0 之前使用的是双色标记法，和 ulisp 大同小异。
Lua GC 规则
- Lua 中所有对象需要垃圾回收，包括了 table 、函数、协程、模组。
- 只有通过根集(root set)可以访问到的对象才会被保存。
- root set ::= registry + shared metatables
- registry ::= global table(_G) + main thread + package.loaded
- Lua 垃圾收集调用的是标准库内存分配函数（其实整个 Lua 都只用了标准库）。
- 所有的对象都被一个链表储存。
Lua GC Pace
如果 GC 从不运行就没有消耗额外的 CPU 周期，但是会浪费大量内存；如果 GC 一直运行就不会浪费额外的内存，但是会消耗大量 CPU 周期。因此我们需要找到一个合适的 GC 运行间隔。
Lua 5.0 采取的方法是当此次内存分配达到上次内存分配的两倍时调用 GC 。但这就造成了一个问题，虚拟机会停下来收集完垃圾再继续执行(stop the world)，这也就是 Lua 5.0 及之前都只能作为小小胶水语言使用的原因。
增量收集
在 5.1 版本中，Lua 有了一个增量收集器，将收集器的执行与主程序交错执行。这也导致 GC 内保存的不再是一个可以直接分析的静态数据，必须引入三色标记。
三色标记法
采用了一种三色标记的算法。每个对象都有三个状态：无法被访问到的对象是白色，可访问到，但没有递归扫描完全的对象是灰色，完全扫描过的对象是黑色。理想状况下，GC 只需要充分遍历灰色对象就可以完成收集。
Mutator 导致的问题
考虑一种情况，一个变量 x 已经被标记为黑色，但是解释执行x.a = {}，很明显{}是一个白色对象，这就形成了黑色对象指向白色对象的问题（导致这个问题的原因是对象的可变性）。此时我们不得不改变 x 的颜色，给死去的变量打复活赛。
这时是将 {} 改变为灰色，还是把 x 变成灰色是个问题，刚好 Lua 提供了这两个接口：
LUAI_FUNC void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v);
LUAI_FUNC void luaC_barrierback_ (lua_State *L, GCObject *o);
何时使用何种方法其实是看设计者的经验。
在刚刚说的这种情况中，Lua 采用的是将 x 变为灰色的方法，因为给一个 table 中的字段赋值说明这个 table 很有可能还要被复用；而在 metatable 中遇到这种情况就采取的是另一种方法。
分代式 GC
想象一个场景，我们在代码的某处（甚至可以想象就是代码开头）使用了一个巨大的矩阵，之后再也没有比它更大的内存分配了，那么 Lua 5.1 的 GC 可能只会运行一次。
因此基于假设大部分对象在创建出来后不久就被回收掉(most objects die young)的假设，Lua 5.2 设计了分代式 GC ，并在 5.4 中完善。
Old and Young
所有的对象被划分为年轻的(young)和年老的(old)：对象刚被创建时是年轻的，当存活过两轮垃圾收集则变为年老的。在每次次级垃圾收集中，GC 只遍历并清除年轻的变量。
注意在分代中的重要规则：老对象不能指向新对象。因此遇到这种情况时，如果我们将新对象变为老对象(forward)就可能出现大量的老对象，让分代式退化到原来的版本；如果我们将老对象变为新对象(backward)，就可能在别的地方破坏规则（例如这个老对象被别的对象引用）。
The Touched Objects
为了解决上述的问题，Lua 引入了被触碰过的对象这一概念，在刚刚的情景下，老对象会被标记为被触碰过的对象并被放入一个特殊的列表中。
在每次次级垃圾收集中，被触碰过的变量会被遍历，但不会被收集（可能会收集它们指向的新对象）。
在经历两次垃圾收集（非次级）后，被触碰过的变量指向的子对象都变成老对象了，因此他们也会恢复成为老对象。
Lua 5.2 分代的问题
在 Lua 5.3 的设计中，一个新对象经历一次收集而不被回收就会成为老对象。如果它刚好在一次回收前被创建而且本应该在那次回收之后不久被回收，本不应该成为老对象的它就会成为老对象。
过多的老对象就导致 5.2 的性能堪忧。
userdata 导致的问题
由于 Lua 是一种可以与 C 互相嵌入的语言，因此不可避免地会使用到 C 中的数据结构(userdata)，但又由于 Lua 支持给 userdata 定义 __gc 方法，故要区分有无 __gc 方法的 userdata 。
标记流程要分为两步，先是把包括 userdata 的死对象标记，再将 userdata 中有 __gc 方法的复活，让它们在下一轮被收集。