给 C 实现一个垃圾收集器
粽子节假期,欧洲杯开战。为了晚上不打瞌睡,我决定写程序提神。这三天的成果就是:实现了一个 C 用的垃圾收集器。感觉不错。
话说这 C 用的垃圾收集器,也不是没人做过,比如 这个 。不过它用的指针猜测的方法,总让人心里不塌实,也让人担心其收集的效率。
我希望做一个更纯粹的 gc for C/C++ 模块,接口保持足够简单。效率足够的高。三天下来,基本完成,正在考虑要不要放到 sourceforge 上开源。等过两天彻底测试过再做打算(或许再支持一下多线程收集)。
下面列一下设计目标和实现思路。
首先,采用标记清除的 gc 策略,这是目前公认的最有效的 gc 方案。远强过用引用计数的 boost::smart_ptr
那种。
接口保持足够简单,没有太多多余的东西需要使用者留意。
最重要的是效率,除了收集过程外,所有的 api 调用都要求是近似 O(1) 的时间复杂度。
先谈谈我对传统的标记清除的 gc 算法实现的一些看法。大多数实现中,都需要对 gc 模块分配出来的内存做特殊处理,在内存的头上放一些链接数据和预留标记位。IMHO ,当内存使用量较大,大过物理内存的量时,这种方案会导致收集过程异常缓慢。因为标记的过程需要访问几乎所有的内存块,这会导致大量的虚拟内存交换。就是说,无论你是否立即需要内存块里的数据,在收集过程中,每个内存块都需要碰一下。如果还包括设置标记的话,甚至需要改写虚拟内存中的数据。
我希望改进这一点,也就是说,那所有 gc 相关的数据集中在一起,整个收集过程,除了最终释放那些不再使用的内存外,不会碰用户数据块的内存。
gc 最重要的一点,就是要对堆栈上的数据进行关联。在收集发生时,堆栈上所有临时分配出来的内存块都不应该被释放掉。C 语言本身不提供堆栈遍历的特性,所以要想个自然的方案让用户可以方便的做到这点。
在用户的调用栈上,每个调用级上,临时分配的内存都被自然挂接在当前级别的堆栈挂接点上,一旦调用返回,当前级别的所有临时内存块都应该和根断开。当然,如果内存块作为返回值出现的话,需要保留。在 C 里,我们需要给每个函数的入口和出口都做一个监护,保证 gc 的正确工作。(如果是 C++ ,要稍微方便一点,在函数进入点设置一个 guard 对象即可)因为这个监护过程会非常频繁,对其的优化是重点工作。
最终,我的 gc 库暴露了 5 个 api 供用户使用:
void * gc_malloc(size_t sz, void (*free)(const void *)); void gc_link(const void *parent, const void *prev, const void *child); void gc_enter(); void gc_leave(const void *value, ... ); void gc_collect();
要申请内存时,可以调用 gc_malloc
申请 sz 大小的内存。free 函数指针可选。它提供一个机会,在内存真正释放之前做一些事情。
gc_link
用于建立内存块之间的联系。可以让 child 指针依赖 parent 指针。既,child 的生命期不会短于 parent 。这个 api 还可以取消 prev 和 parent 之间的联系。parent prev child 中任何一个都可以传空指针。当parent 为空时,child 挂接到根上。这通常用于维系全局变量的生命期。gc_link
保证 prev 在堆栈上有一次临时的引用。
gc_enter
和 gc_leave
当配对使用,放在一个函数或一段语句块的入口和出口处。夹在 enter 和 leave 之间的 gc_malloc
申请的内存块,生命期不会超过临近的 leave 指令。除非在 gc_leave
的参数中指明需要延长生命期。gc_leave
可以带多个指针,只需要最后一个以 0 结束。这通常用于函数的返回值。
gc_collect
用于垃圾收集,它可以在任何时机调用,把和根没有关联的内存块全部释放掉。堆栈上(没有闭合的 enter / leave 对)的所有 gc_malloc
分配的内存块都会被自动挂接在根上;用户也可以用 gc_link
主动挂接(parent 传 0)。
这套接口设计的应该是足够简洁了。用户只需要自己描述对象和对象之间的关系(使用 gc_link
),别的不用太操心。
如果使用 C++ 可以进一步的封装,重载赋值操作符来做到这些。而 C 也可以定义一个宏来辅助(注意宏的一些问题,比如重复计算)。比如:
static void eval(void *parent,void **node,void *child) { gc_link(parent,*node,child); *node=child; } #define EVAL(obj, prop, value) eval( (obj), & ((obj)-> ## prop), (value)) struct tree { struct tree *left; struct tree *right; }; struct tree * new_node() { struct tree *n=(struct tree *)gc_malloc(sizeof(*n),0); memset(n,0,sizeof(*n)); return p; } struct tree * foo() { struct tree *t; gc_enter(); t=new_node(); EVAL(t,left,new_node()); EVAL(t,right,new_node()); gc_leave(t,0); return t; }
上面这个 foo 函数演示了 gc 模块的基本用法:构造了一个节点 t ,以及另外两个临时节点连接到 t 的 left 和 right 两个成员上。最后把 t 返回。
下面谈一下优化:
为了让用户数据块和关联数据分离,所以模块内部实现的时候,将指针映射到了内部 id 上,这里使用了一个 hash map 。这样,可以使用 id 保持相互关联的信息。
对象之间的关联信息是一个图结构。图的边的构建和变动复杂度较大。在实现时,做了一个 cache ,在 gc_link
的时候,不直接增删边。而是缓存对图变更的请求,并在缓冲期间合并一些操作。例如,一些临时的关联信息,可能因为周期很短,在 collect 发生前就已经解除关联,其操作就会被抵消掉。
cache 了大量操作后,对操作进行排序。批量修改图的边时,也可以减少大量的运算。(内部数据结构对图的每个节点的孩子采用一个有序数组保存,比较适合批量增删)
gc_enter
和 gc_leave
是优化的重点。因为这个调用最为频繁。而 gc_collect
发生较少,对象频繁进出堆栈,不需要重复挂接。
采用另一个 cache ,直接保存内存指针,甚至可以不做 hash map 查询(映射到内部 id ),只到 collect 发生时再一次计算。临时对象存在于堆栈上时,是一个树结构,而非图结构的关联关系(每个堆栈上的调用级是一个树节点)。这也有利于优化处理。
整个实现代码只用了 600 多行,但是却写了三个晚上。主要是为了提高处理效率(时间和空间效率),设计了一些精巧的数据结构,控制起来非常麻烦,写起来也很是小心。这次完成后,就可以替换掉去年实现的一个不太地道的 gc 模块了。当时的那个需要依赖一个单根的类树,用起来要麻烦的多。
如果日后开源的话,还有一些事情要做:代码需要更规范,补上更详细的测试代码,以及支持 64 位系统等。
6 月 10 日补充:
今天把它在 google code 上开源了,用的 BSD 的许可协议。第一个版本还很 dirty 。没有怎么测试,可能还有许多 bug 。
有兴趣的同学可以在这里用 svn check out (尚未 release ,没做下载包) :
http://code.google.com/p/manualgc/
ps. 我的英文很滥,注释和说明可以无视。
Comments
Posted by: Ali.kk | (63) June 9, 2018 07:19 PM
Posted by: 若尘 | (62) May 4, 2018 09:29 AM
Posted by: yangyu | (61) September 11, 2014 04:02 PM
Posted by: weijia | (60) June 27, 2012 05:25 PM
Posted by: mike | (59) April 9, 2012 06:22 PM
Posted by: Cloud | (58) May 27, 2011 02:53 PM
Posted by: Joe | (57) May 27, 2011 02:34 PM
Posted by: Mike | (56) January 27, 2011 05:10 PM
Posted by: 服务器托管 | (55) June 13, 2010 12:01 PM
Posted by: anon | (54) January 25, 2010 01:13 PM
Posted by: cloud | (53) January 13, 2010 04:17 PM
Posted by: anon | (52) January 13, 2010 03:42 PM
Posted by: cloud | (51) January 6, 2010 06:37 PM
Posted by: anon | (50) January 4, 2010 05:12 PM
Posted by: 安 | (49) March 27, 2009 10:51 PM
Posted by: phoolimin | (48) March 19, 2009 05:54 PM
Posted by: HelloKarl | (47) March 19, 2009 02:54 PM
Posted by: bochs | (46) September 28, 2008 04:42 PM
Posted by: seatle | (45) July 15, 2008 06:11 PM
Posted by: Linker M Lin | (44) June 16, 2008 02:01 PM
Posted by: Anonymous | (43) June 13, 2008 11:15 AM
Posted by: 饭中淹 | (42) June 12, 2008 10:44 PM
Posted by: Cloud | (41) June 12, 2008 01:02 PM
Posted by: tigerdx8 | (40) June 12, 2008 11:05 AM
Posted by: bennie | (39) June 12, 2008 10:10 AM
Posted by: mike | (38) June 12, 2008 08:33 AM
Posted by: Xiaofeng | (37) June 11, 2008 09:27 PM
Posted by: Xiaofeng | (36) June 11, 2008 09:13 PM
Posted by: Xiaofeng | (35) June 11, 2008 09:05 PM
Posted by: 程序狂 | (34) June 11, 2008 08:47 PM
Posted by: Cloud | (33) June 11, 2008 05:49 PM
Posted by: Cloud | (32) June 11, 2008 05:33 PM
Posted by: bennie | (31) June 11, 2008 05:03 PM
Posted by: Siney | (30) June 11, 2008 04:15 PM
Posted by: joe wulf | (29) June 11, 2008 03:14 PM
Posted by: Cloud | (28) June 11, 2008 01:04 PM
Posted by: Anonymous | (27) June 11, 2008 12:58 PM
Posted by: Anonymous | (26) June 11, 2008 11:11 AM
Posted by: Anonymous | (25) June 11, 2008 10:58 AM
Posted by: teddy | (24) June 11, 2008 10:50 AM
Posted by: bennie | (23) June 11, 2008 10:45 AM
Posted by: mike | (22) June 11, 2008 10:10 AM
Posted by: Siney | (21) June 11, 2008 10:00 AM
Posted by: nothanks | (20) June 11, 2008 09:56 AM
Posted by: 白鸟 | (19) June 11, 2008 09:54 AM
Posted by: Cloud | (18) June 11, 2008 12:16 AM
Posted by: DD | (17) June 10, 2008 11:53 PM
Posted by: Cloud | (16) June 10, 2008 10:26 PM
Posted by: Wiz_chen | (15) June 10, 2008 10:10 PM
Posted by: 啃饼 | (14) June 10, 2008 07:18 PM
Posted by: txw | (13) June 10, 2008 06:49 PM
Posted by: Cloud | (12) June 10, 2008 05:42 PM
Posted by: Cloud | (11) June 10, 2008 05:22 PM
Posted by: westhood | (10) June 10, 2008 04:35 PM
Posted by: 游客 | (9) June 10, 2008 03:05 PM
Posted by: joe wulf | (8) June 10, 2008 02:21 PM
Posted by: Liyan | (7) June 10, 2008 12:36 PM
Posted by: 永恒白天 | (6) June 10, 2008 12:25 PM
Posted by: jtuki | (5) June 10, 2008 12:16 PM
Posted by: nothanks | (4) June 10, 2008 10:01 AM
Posted by: dikatour | (3) June 10, 2008 10:00 AM
Posted by: Anonymous | (2) June 10, 2008 09:39 AM
Posted by: phoenixbing | (1) June 10, 2008 07:39 AM