(本文中出现的Lua均只限于Lua 5.1.3; Python均只限于Python 2.5)?

Lua的垃圾收集机制使用了名为标志和清扫(Mark-and-Sweep)的方式。?

1、Mark-and-Sweep

基础的Mark-and-Sweep算法是最古老的解决循环引用情况垃圾收集算法之一。?
顾名思义，这是一个two phases的算法，可用很简单的文字描述：?
(1)Mark phase(标志阶段)?
1> 每个可被gc的对象都拥有一个标志位，初始为0(unmarked)。?
2> 定义程序中第一层可访问的对象集合为 根对象集合(root set)。?
3> 递归遍历根集合中所有对象的引用关系，如果某对象标志位为unmarked，?
则标志为1(marked)。?
(2)Sweep phase(清扫阶段)?
1> 遍历所有现存的对象：将标志位还是marked的对象释放；?
同时将标志为marked的对象重新标志为unmarked，为下次gc做准备。?

?

基础的Mark-and-Sweep简单一个处理流程的例子是：?
(0)初始状态?
root(0) ──> a(0) ──> b(0) ──> c(0)?
↑└────────┐?
┌────┘ ↓?
x(0) ──> y(0) ──> z(0)?
(1)执行完Mark phase后?
root(1) ──> a(1) ──> b(1) ──> c(1)?
x(0) ──> y(0) ──> z(1)?
(2)执行完Sweep phase后?
└────────┐?
↓?
z(0)?


说回Lua的gc实现。Lua gc的实现模块主要是lgc.c/lgc.h。?
首先需要注意的是，Lua中并不是所有对象都可被gc，在全部9种对象类型：?
#define LUA_TNONE (-1)?
#define LUA_TNIL 0?
#define LUA_TBOOLEAN 1?
#define LUA_TLIGHTUSERDATA 2?
#define LUA_TNUMBER 3?
#define LUA_TSTRING 4?
#define LUA_TTABLE 5?
#define LUA_TFUNCTION 6?
#define LUA_TUSERDATA 7?

#define LUA_TTHREAD 8?

可被垃圾回收（gc）类型：
LUA_TSTRING,LUA_TTABLE,LUA_TFUNCTION,LUA_TUSERDATA,?TLUA_TTHREAD

为此lobject.h专门定义了一个宏：?

#define iscollectable(o) (ttype(o) >= LUA_TSTRING)?
跟基础Mark and Sweep算法有些不同的是，?
Lua引入了?
白(old white): 老对象初始状态?
白(current white)：新对象的初始状态?
灰(gray)：待变黑色状态?
黑(black)：老变量继续存活的状态?

几种颜色之一来标志一个对象当前的状态。?
PS:old white和current white每轮gc会互换，以区分gc过程中产生的新对象。?

2、增量式回收

Lua gc是一个增量式的实现，在代码术语中称为一个step；?
gc的过程归为5个按顺序的状态(设定参数可使某些状态中用多次step迭代)：?

(1)GCSpause （添加old white对象到gray list）

新gc过程的开始。?
此时root set中包含：?
* lua_State对象?
* _G table?
* Registry?
* metatable数组?
本状态将root set中所有old white对象变gray，并至于gray list中。?
处理完毕后，状态转变为GCSpropagate。?
(2)GCSpropagate （追踪gray list中的对象的引用关系） 将gray list中的每个对象标志为black并从gray list中移出，并遍历每个?
对象引用关系，将所有仍为old white的对象变成gray并添加到gray list。?
当gray list中没有任何对象时，将old white翻转为current white。?
处理完毕后，状态转变为GCSsweepstring。?

(3)GCSsweepstring （释放可被gc的string对象）

检查string列表中的每个string对象：old white的string对象将被释放；?
其他颜色string对象将被标志为current white(作下一轮gc的old white)。?
处理完毕后，状态转变为GCSsweep。?
(因为Lua中字符串存放在独立的g->strt.hash处，所以sweep阶段为string? 类型单独规划了一个状态来处理。)?

(4)GCSsweep ?（释放除了string外可被gc对象）

检查所有除string外的可被gc对象(即检查g->rootgc列表)，处理过程? 和GCSsweepstring中的一样。?
处理完毕后，状态转变为GCSfinalize。?
(5)GCSfinalize? 将所有已经无引用的userdata释放(调用其__gc metamethod)。?
处理完毕后，状态转变为GCSpause，等待下一次的全新gc过程。?
Lua在语言层面上只提供了一个collectgarbage接口用于定制gc过程的细节，?
简洁且足够好用，具体的项目可以根据自身情况找出最适合的gc参数配置：?
collectgarbage (opt [,arg])?
This function is a generic interface to the garbage collector.?
It performs different functions according to its first argument,opt:?
"stop": stops the garbage collector.?
"restart": restarts the garbage collector.?
"collect": performs a full garbage-collection cycle.?
"count": returns the total memory in use by Lua (in Kbytes).?
"step": performs a garbage-collection step.?
The step "size" is controlled by arg?
(larger values mean more steps) in a non-specified way.?
If you want to control the step size you?
must experimentally tune the value of arg.?
Returns true if the step finished a collection cycle.?
"setpause": sets arg/100 as the new value for the?
pause of the collector.?
"setstepmul": sets arg/100 as the new value for the?
step multiplier of the collector.?

3、与python垃圾回收比较

（1）引用计数

与Python引用计数(Reference Counting)垃圾收集方式相比，Mark-and-Sweep?

方式避免了对象间循环引用而导致连cycle detector都不能收集的尴尬(在Python?
Script层次上重载过对象__del__方法且多对象间互相引用致bug的时候，真抓狂)。?
同时，C API层次上可以忽略reference这个概念，使用时不再需要每个API查文档?
看是 New reference / Borrowed reference ...，也不需编写C扩展时刻谨慎地?
INCREF/DECREF reference(或借助C++ Wrapper)。?

（2）性能比较

至于收集性能上，Reference Counting占优，因为它把消耗分摊到每次的?
对象创建和引用上了；而Mark-and-Sweep则需扫描整个对象空间所有对象(两次)，?
这常常会导致长时间的线程忙来专门做gc，在一些需要流畅感的应用，比如游戏?
服务器上，这样会不定期的导致间歇性阻塞感。还好Lua引入了增量式收集器?
(incremental garbage collector)，使gc开销一定程度上可控。