江苏快三开奖结果

Khan's Notebook GCC/GNU/Linux Delphi/Window Java/Anywhere

LUMANMAN,CHANGXIUYUAN,WOMENBUNENGMEIYOUQIAN

在 C++ 中實現一個輕量的標記清除 gc 系統(轉載)

# 在 C++ 中實現一個輕量的標記清除 gc 系統
[引用](http://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 #endif
30 ```
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 閱讀(145) 評論(0)  編輯 收藏 引用 所屬分類: GCC/G++跨平臺開發


只有注冊用戶登錄后才能發表評論。

網站導航:                管理


<2020年2月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
1234567

導航

統計

公告

現在時刻

IM在線情況:

常用鏈接

留言簿(33)

隨筆分類(220)

隨筆檔案(164)

相冊

技術

友情鏈接

最新隨筆

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜