# 在 C++ 中实现一个轻量的标记清除 gc 系统
[引用](https://blog.codingnow.com/2010/02/cpp_gc.html)
最近想把 engine 做一个简单 C++ 封装，结合 QT 使用。engine 本身是用纯 C 实现的，大部分应用基于 lua 开发。对对象生命期管理也依赖 lua 的 gc 系统。关于这部分的设计，可以参考我以前写的一篇 为 lua 封装 C 对象的生存期管理问题 。
当我们把中间层搬到 C++ 中时，遇到的问题之一就是，C++ 没有原生的 gc 支持。我也曾经写过一个 gc 库。但在特定应用下还不够简洁。这几天过年休息，仔细考虑了一下相关的需求，尝试实现了一个更简单的 gc 框架。不到 200 行代码吧，我直接列在这篇 blog 里。
这些尚是一些玩具代码，我花了一天时间来写。有许多考虑不周的地方，以及不完整的功能。但可以阐明一些基本思路。
首先我需要一个`标记清除`的 `gc系统`，用来解决`引用记数`不容易解决的`循环引用`问题。它的实现不想比`引用记数`复杂太多，并有相同甚至更高的性能。
我不想使用复杂的 template 技术，利用太多的语法糖让使用看起来简单。如果需要让这些 C++ 代码看起来更现代，更有“品味”，我想也不是很难的事情。
接口和实现希望尽量分离，对用的人少暴露细节。但不拘泥于教条，强求做成类似 COM 那样的通用 ABI 。还是尽量利用 C++ 语言本身提供的机制，不滥用。
使用尽量简单，不要让使用人员有太大负担。
功能满足最低需求即可。代码容易阅读，使用人员可以很快理解原理，不至于误用。也方便日后扩展以适应新的需求。
代码如下：
1 /*
2 * filename: i_gcobject.h
3 * Copyright (c) 2010 ,
4 * Cloud Wu . All rights reserved.
5 *
6 * http://www.codingnow.com
7 *
8 * Use, modification and distribution are subject to the "New BSD License"
9 * as listed at .
10 */
11
12 #ifndef interfacce_gcobject_h
13 #define interfacce_gcobject_h
14
15 #define interface struct
16
17 interface i_gcobject {
18 virtual ~i_gcobject() {}
19
20 virtual void touch() {}
21
22 virtual void mark() = 0 ;
23 virtual void grab() = 0 ;
24 virtual void release() = 0 ;
25
26 static void collect();
27 };
28 #endif
所有支持 `gc管理的接口`都继承至 `i_gcobject` ，提供三个方法:
* mark 可以把这个对象打上标记，被标记的对象将不会被 collect 回收。
* grab 将对象挂接到一个被称呼为 root 的特殊 gcobject 上。
* release 将对象从 root 上取掉。
另提供 touch 的模板方法供 mark 回调，用来标记同一对象中的不同部分。
mark 方法一般在 touch 方法中使用，另外，collect 方法将主动调用 root 的 mark 。
1 /* filename: i_gcholder.h
2 * Copyright (c) 2010 ,
3 * Cloud Wu . All rights reserved.
4 *
5 * http://www.codingnow.com
6 *
7 * Use, modification and distribution are subject to the "New BSD License"
8 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
9 */
10
11 #ifndef interfacce_gcholder_h
12 #define interfacce_gcholder_h
13
14 #include "i_gcobject.h"
15
16 interface i_gcholder : virtual i_gcobject {
17 virtual void hold(i_gcobject *) = 0;
18 virtual void unhold(i_gcobject *) = 0;
19
20 static i_gcholder * create();
21 };
22 #endif
`i_gcholder` 为 root 的接口，提供 `hold` 和 `unhold` 方法来挂接需要持久保留的 gcobject 。
1 /* filename: i_gcobject.h
2 * Copyright (c) 2010 ,
3 * Cloud Wu . All rights reserved.
4 *
5 * http://www.codingnow.com
6 *
7 * Use, modification and distribution are subject to the "New BSD License"
8 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
9 */
10
11 #ifndef interfacce_gcobject_h
12 #define interfacce_gcobject_h
13 #define interface struct
14
15 interface i_gcobject {
16
17 virtual ~i_gcobject() {}
18
19 virtual void touch() {}
20
21 virtual void mark() = 0 ;
22 virtual void grab() = 0 ;
23 virtual void release() = 0 ;
24
25 static void collect();
26 };
27 #endif
1 /* filename: gcobject.h
2 * Copyright (c) 2010 ,
3 * Cloud Wu . All rights reserved.
4 *
5 * http://www.codingnow.com
6 *
7 * Use, modification and distribution are subject to the "New BSD License"
8 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
9 */10 11 #ifndef gc_object_h
12 #define gc_object_h
13 14 #include "i_gcobject.h"
15 16 class gcobject :
virtual i_gcobject {
17 bool marked;
18 19 public:
20 gcobject();
21 22 virtual void mark();
23 virtual void grab();
24 virtual void release();
25 26 struct f_unmarked;
27 28 };
29 #endif30 ```
31 32 ```c++
33 /* filename: gcobject.cpp
34 * Copyright (c) 2010 ,
35 * Cloud Wu . All rights reserved.
36 *
37 * http://www.codingnow.com
38 *
39 * Use, modification and distribution are subject to the "New BSD License"
40 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
41 */42 43 #include "gcobject.h"
44 #include "i_gcholder.h"
45 #include <vector>
46 #include <algorithm>
47 48 static bool gc_trigger;
49 static std::vector<gcobject *> gc_pool;
50 static i_gcholder * gc_root = i_gcholder::create();
51 52 53 struct gcobject::f_unmarked {
54 bool operator() (gcobject * value) {
55 bool unmarked = value->marked != gc_trigger;
56 if (unmarked) {
57 delete value;
58 }
59 return unmarked;
60 }
61 };
62 63 gcobject::gcobject() : marked(!gc_trigger) {
64 gc_pool.push_back(
this);
65 }
66 67 void gcobject::mark() {
68 if (marked != gc_trigger) {
69 marked = gc_trigger;
70 touch();
71 }
72 }
73 74 void gcobject::grab(){
75 gc_root->hold(
this);
76 }
77 78 void gcobject::release(){
79 gc_root->unhold(
this);
80 }
81 82 void i_gcobject::collect() {
83 gc_root->mark();
84 gc_pool.erase(remove_if(gc_pool.begin(), gc_pool.end() , gcobject::f_unmarked()), gc_pool.end());
85 gc_trigger = !gc_trigger;
86 }
gcobject 为具体的 gc 实现，实现了 `mark` 、`grab`、`release` 和 `collect` 方法。
`mark` 采用的直接向一 bool 变量设置标记。这个标记利用了 `trigger` 这个乒乓开关，每次 `collect` 都会切换状态。
`grab` 和 `release` 可以把对象挂接到 root 上，或从上取掉。
`collect` 会主动从 root 开始 `mark` ，并释放那些没有 `mark` 的对象。
1 /* filename: gcholder.cpp
2 * Copyright (c) 2010 ,
3 * Cloud Wu . All rights reserved.
4 *
5 * http://www.codingnow.com
6 *
7 * Use, modification and distribution are subject to the "New BSD License"
8 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
9 */10 11 #include "i_gcholder.h"
12 #include "gcobject.h"
13 #include <vector>
14 #include <algorithm>
15 #include <cassert>
16 17 class gcholder :
public virtual i_gcholder,
virtual gcobject {
18 std::vector<i_gcobject *> hold_set;
19 std::vector<i_gcobject *> unhold_set;
20 21 bool set_changed;
22 bool hold_set_sorted;
23 bool unhold_set_sorted;
24 25 void combine_set();
26 virtual void touch();
27 28 virtual void hold(i_gcobject *obj) {
29 hold_set.push_back(obj);
30 hold_set_sorted =
false;
31 set_changed =
true;
32 }
33 34 virtual void unhold(i_gcobject *obj) {
35 unhold_set.push_back(obj);
36 unhold_set_sorted =
false;
37 set_changed =
true;
38 }
39 40 struct f_mark {
41 void operator() (i_gcobject *obj) {
42 obj->mark();
43 }
44 };
45 46 public:
47 48 gcholder() : set_changed(
false), hold_set_sorted(
true) , unhold_set_sorted(
true) { }
49 50 };
51 52 void gcholder::combine_set(){
53 if (!hold_set_sorted) {
54 std::sort(hold_set.begin(),hold_set.end());
55 hold_set_sorted =
true;
56 }
57 if (!unhold_set_sorted) {
58 std::sort(unhold_set.begin(),unhold_set.end());
59 unhold_set_sorted =
true;
60 }
61 if (!unhold_set.empty()) {
62 std::vector<i_gcobject *>::iterator iter1 = hold_set.begin();
63 std::vector<i_gcobject *>::iterator iter2 = unhold_set.begin();
64 while (iter1 != hold_set.end() && iter2 != unhold_set.end()) {
65 if (*iter1 == *iter2) {
66 *iter1 = NULL;
67 ++iter1;
68 ++iter2;
69 }
else {
70 assert(*iter1 < *iter2);
71 ++iter1;
72 }
73 }
74 i_gcobject *
null = NULL;
75 hold_set.erase(std::remove(hold_set.begin(),hold_set.end(),
null) , hold_set.end());
76 unhold_set.clear();
77 }
78 }
79 80 void gcholder::touch(){
81 if (set_changed) {
82 combine_set();
83 set_changed =
false;
84 }
85 std::for_each(hold_set.begin(), hold_set.end(), f_mark());
86 }
87 88 i_gcholder * i_gcholder::create(){
89 return new gcholder;
90 }
gcholder 理论上可以有多个实例，并相互挂接。（否则不需要继承至 i_gcobject ）这个设计可以用来模拟多级的堆栈。但实际上并不需要这么复杂。因为在大部分应用里，如果你的程序有一个周期性的主循环，就可以不在 gc 系统里模拟出一个多级的堆栈。我们只用在循环之外做 collect 即可。再堆栈调用的较深层次触发 collect 反而效果不佳，会导致许多临时 gc 对象无法回收。
最后来看一个玩具代码，用 stl 里的 mutliset 实现了一个简单的树接口。可能没有什么使用价值，但它演示了一个较复杂的对象相互引用的关系。并可以展示 gc 如何正确工作。
1 /* filename: test.cpp
2 * Copyright (c) 2010 ,
3 * Cloud Wu . All rights reserved.
4 *
5 * http://www.codingnow.com
6 *
7 * Use, modification and distribution are subject to the "New BSD License"
8 * as listed at <url: http://www.opensource.org/licenses/bsd-license.php >.
9 */10 #include "gcobject.h"
11 #include <cstdio>
12 #include <
set>
13 #include <algorithm>
14 15 interface i_tree :
virtual i_gcobject {
16 virtual void link(i_tree *p) = 0;
17 static i_tree * create();
18 };
19 20 class tree :
public virtual i_tree ,
virtual gcobject {
21 tree *parent;
22 std::multiset<tree *> children;
23 struct f_mark {
24 void operator() (tree *node) {
25 node->mark();
26 }
27 };
28 29 virtual void touch() {
30 if (parent)
31 parent->mark();
32 std::for_each(children.begin(), children.end(), f_mark());
33 }
34 35 void unlink();
36 virtual void link(i_tree *parent);
37 38 public:
39 tree() : parent(NULL) {
40 printf("create node %p\n",
this);
41 }
42 43 ~tree() {
44 printf("release node %p\n",
this);
45 }
46 47 };
48 49 50 void tree::unlink() {
51 if (parent) {
52 parent->children.erase(
this);
53 parent = NULL;
54 }
55 }
56 57 void tree::link(i_tree *p){
58 unlink();
59 if (p) {
60 tree * cp = dynamic_cast<tree *>(p);
61 cp->children.insert(
this);
62 parent = cp;
63 }
64 }
65 66 i_tree *i_tree::create(){
67 return new tree;
68 }
69 70 int main(){
71 i_tree *root = i_tree::create();
72 root->grab();
73 i_tree *node;
74 node = i_tree::create();
75 node->link(root);
76 node = i_tree::create();
77 node->link(root);
78 i_gcobject::collect();
79 printf("collected\n");
80 node->link(NULL);
81 i_gcobject::collect();
82 printf("finalize\n");
83 root->release();
84 i_gcobject::collect();
85 return 0;
86 }
我们在实现一个基于 gc 的对象时，可以先定义出需要的接口，让接口从 i_gcobject 继承。例如上例中的 i_tree 。
然后在实现这个接口时，可以虚继承 gcobject 。例如上例中的 tree 。
如果有需要，就重载 touch 方法，在 touch 方法中 mark 相关的 gcobject 。对于 tree 这个例子，就是调用父亲和孩子节点的 mark 。
对象依然可以写析构函数，相当于对象的 finalize 。在析构函数中，不要再释放和它相关的 gcobject ，那些留给 gc 系统去完成。（例如在 tree 里，就不要在 ~tree 中 delete children 容器中的变量，也不需要把自己从父亲节点上摘掉）
如果仅仅只是使用那些接口，则不需要再包含 gcobject.h ，因为 gcobject 的细节只供实现 i_gcobject 时使用。
posted on 2019-08-01 10:57
Khan 阅读(488)
评论(0) 编辑 收藏 引用 所属分类:
GCC/G++ 、
跨平台开发