本文已經遷移到： http://cpp.winxgui.com/cn:a-general-gc-allocator-scopealloc
C++內存管理變革(6)：通用型垃圾回收器 - ScopeAlloc
許式偉
2008-1-22
引言
在前文，我們引入了 GC Allocator（具備垃圾回收能力的Allocator） ，并提供了一個實作： AutoFreeAlloc （詳細內容參見《 C++內存管理變革(2)：最袖珍的垃圾回收器 - AutoFreeAlloc 》）。
但是，如前所述，AutoFreeAlloc是有其特定的適用環境的（它對內存管理的環境進行了簡化，這種簡化環境是常見的。詳細參閱《 C++內存管理變革(3)：另類內存管理 - AutoFreeAlloc典型應用 》）。那么，在AutoFreeAlloc不能適用的情形下，我們可以有什么選擇？
本文要討論的，正是這樣一個GC Allocator實作。它所抽象的內存管理的環境比之AutoFreeAlloc復雜許多，適用范圍也廣泛很多。這個GC Allocator我們稱之為 ScopeAlloc 。
思路
在AutoFreeAlloc假象的模型里，一個算法的所有步驟都統一使用同一個GC Allocator，最后的內存由該Allocator統一回收。這個模型很簡潔，很容易理解和掌握。
理解ScopeAlloc的關鍵，在于理解我們對AutoFreeAlloc的模型所作的修正。我們設想一個算法的第i步驟比較復雜，其內存開銷也 頗為可觀，希望為步驟i引入一個私有存儲（Private GC Allocator），以便哪些步驟i內部計算用的臨時內存在該步驟結束時釋放。示意圖如下：
圖1
由于引入私有存儲（Private GC Allocator），模型看起來就變得很復雜。上面這個圖也許讓你看暈了。不過沒有關系，我們把上圖中與步驟i相關的內容獨立出來看，得到下圖：
圖2
如圖2顯示，一個算法會有自己的私有存儲（Private GC Allocator），也會使用外部公有的存儲（Share GC Allocator）。之所以是這樣，是因為算法的結果集（Result DOM）不能在算法結束時銷毀，而應該返回出去。這我們大致可以用以下偽代碼表示：
ResultDOM
*
algorithm
(
InputArgs
args
,
ScopeAlloc
&
shareAlloc
)
{
ScopeAlloc
privateAlloc
(
shareAlloc
)
;
...
ResultDOM
*
result
=
STD_NEW
(
shareAlloc
,
ResultDOM
)
;
ResultNode
*
node
=
STD_NEW
(
shareAlloc
,
ResultNode
)
;
result
->
addNode
(
node
)
;
...
TempVariable
*
temp
=
STD_NEW
(
privateAlloc
,
TempVariable
)
;
...
return
result
;
}
在這段偽代碼中，ScopeAlloc是今天的主角。 STD_NEW 是 StdExt庫 中用于生成對象實例的宏，STD_NEW(alloc, Type)其功用等價于《 C++內存管理變革(1): GC Allocator 》中的New<Type>(alloc)。只是New<Type>模板函數比較“C++”，比較正統，也比較偏于理論 1 。而STD_NEW則是實際工程中的使用方式。
挑戰
你可能說，要引入私有存儲（Private GC Allocator），為什么非要提供一個新的Allocator？為什么不能是AutoFreeAlloc？為什么不能像下面這樣：
ResultDOM
*
algorithm
(
InputArgs
args
,
AutoFreeAlloc
&
shareAlloc
)
{
AutoFreeAlloc
privateAlloc
;
...
ResultDOM
*
result
=
STD_NEW
(
shareAlloc
,
ResultDOM
)
;
ResultNode
*
node
=
STD_NEW
(
shareAlloc
,
ResultNode
)
;
result
->
addNode
(
node
)
;
...
TempVariable
*
temp
=
STD_NEW
(
privateAlloc
,
TempVariable
)
;
...
return
result
;
}
答案是，性能問題。我們這里 對AutoFreeAlloc和ScopeAlloc這兩個GC Allocator的性能進行了對比 ，結論如下：
生成一個新的AutoFreeAlloc實例是一個比較費時的操作，其用戶應注意做好內存管理的規劃。而生成一個ScopeAlloc實例的開銷很小，你甚至可以哪怕為生成每一個對象都去生產一個ScopeAlloc都沒有關系（當然我們并不建議你這樣做）。
對于多數的算法而言，我們不能確定它所需要的私有存儲（Private GC Allocator）的內存空間是多大?；蛘哒f，通常它們也許并不大。而在僅僅申請少量內存的情形下，使用AutoFreeAlloc是不太經濟的做法。 而相對的，無論算法所需的內存多少，使用ScopeAlloc都可以獲得非常平穩的性能。
故此，我們的第二個結論是：
AutoFreeAlloc有較強的局限性，僅僅適用于有限的場合（局部的復雜算法）；而ScopeAlloc是通用型的Allocator，基本在任何情況下，你都可通過使用ScopeAlloc來進行內存管理，以獲得良好的性能回報。
實現
看到這里，你的興趣相信來了，很想知道ScopeAlloc是長什么樣。其實，ScopeAlloc只是另一個“AutoFreeAlloc”。我們來看看它的定義：
typedef
AutoFreeAllocT
<
ProxyBlockPool
>
ScopeAlloc
;
而我們的AutoFreeAlloc它的定義是：
typedef
AutoFreeAllocT
<
DefaultStaticAlloc
>
AutoFreeAlloc
;
詳細的代碼，參考以下鏈接：
可以看出，ScopeAlloc和AutoFreeAlloc唯一的區別，在于AutoFreeAlloc向系統申請內存（調用的是 malloc/free），而ScopeAlloc向一個內存池（即BlockPool，調用的是BlockPool:: allocate/deallocate）。
BlockPool
BlockPool 就是通常我們所說的 內存池（Memory Pool） 。但是它比一般的內存池要簡單很多，因為它只是管理MemBlock，而不負責對MemBlock進行結點（Node） 2 的劃分（這個工作實際上由AutoFreeAllocT完成了）。
BlockPool的規格如下：
class
BlockPool
{
BlockPool
(
int
cbFreeLimit
,
int
cbBlock
)
;
void
*
allocate
(
size_t
cb
)
;
// 申請一個MemBlock
void
deallocate
(
void
*
p
)
;
// 釋放一個MemBlock
void
clear
()
;
// 清空所有申請的內存
}
;
關于該類的實現細節，我并不多解釋，大家可以參考 內存池(MemPool)技術詳解 。我解釋下構造函數的兩個參數：cbFreeLimit、cbBlock是什么。
cbBlock
這個量比較好解釋，是指單個MemBlock的字節數。
cbFreeLimit
大家都知道，內存池技術在釋放內存時，它并不是將內存真的釋放（還給系統），而是記錄到一個FreeList中，以加快內存申請的速度。但是這帶來 的一個問題是，內存池隨著時間的推移，其占有的內存會不斷 地增長，從而不斷地吃掉系統的內存。cbFreeLimit的引入是為了限制了FreeList中的內存總量，從而抑制這種情況的發生。在 BlockPool中的FreeList內存達到cbFreeLimit時，deallocate操作直接釋放MemBlock。代碼如下：
class BlockPool
{
public:
void deallocate(void* p) // 提醒：m_nFreeLimit = cbFreeLimit / cbBlock + 1
{
if (m_nFree >= m_nFreeLimit) {
free(p);
}
else {
_Block* blk = (_Block*)p;
blk->next = m_freeList;
m_freeList = blk;
++m_nFree;
}
}
}
ProxyBlockPool
它只是BlockPool的代理。定義如下：
typedef
ProxyAlloc
<
BlockPool
>
ProxyBlockPool
;
而Proxy是什么？簡單地不能再簡單：
template
<
class
AllocT
>
class
ProxyAlloc
{
private
:
AllocT
*
m_alloc
;
public
:
ProxyAlloc
(
AllocT
&
alloc
)
:
m_alloc
(
&
alloc
)
{}
public
:
void
*
allocate
(
size_t
cb
)
{
return
m_alloc
->
allocate
(
cb
)
;
}
void
deallocate
(
void
*
p
)
{
m_alloc
->
deallocate
(
p
)
;
}
void
swap
(
ProxyAlloc
&
o
)
{
std
::
swap
(
m_alloc
,
o
.
m_alloc
)
;
}
}
;
ScopeAlloc
如上所述，ScopeAlloc只是一個typedef：
typedef
AutoFreeAllocT
<
ProxyBlockPool
>
ScopeAlloc
;
而關于AutoFreeAlloc的細節，前面《 C++內存管理變革(2)：最袖珍的垃圾回收器 - AutoFreeAlloc 》中我們已經做了詳細介紹。
ThreadModel
關于 線程模型（ThreadModel） ，從上面給出的代碼（ ScopeAlloc.h ）中你可以看到相關的代碼。但是詳細的解釋超出了本文的范疇，我們會另外一篇專門解釋GC Allocator與線程模型（ThreadModel）之間的關系 3 。
時間性能分析
關于性能問題，我們前面已經作了 AutoFreeAlloc和ScopeAlloc的性能對比 。這里簡單再做一下分析。
內存申請/釋放過程
這兩個過程ScopeAlloc與AutoFreeAlloc基本差不多。考慮到ScopeAlloc使用了MemPool技術，從統計意義上來講，如果系統存在頻繁的內存申請和釋放，則ScopeAlloc性能略好于AutoFreeAlloc。
構造過程
基本上都只是指針賦值，可忽略不計。
析構過程
由于ScopeAlloc析構時將內存歸還給內存池，而不是還給系統，ScopeAlloc的時間性能要好過AutoFreeAlloc許多。更確 切地講，兩者的時間復雜度都是O(N)，其中N為MemBlock的個數（也就是Allocator所占的內存總量），但是由于釋放MemBlock操作 的單位時間不同（BlockPool::deallocate比free快許多），導致兩者的性能有異。
使用樣例
AutoFreeAlloc和ScopeAlloc的性能對比 中當然不是ScopeAlloc的典型用例。這里我們舉一個：
class
Obj
{
private
:
int
m_val
;
public
:
Obj
(
int
arg
=
0
)
{
m_val
=
arg
;
printf
(
"
construct Obj: %d
\n
"
,
m_val
)
;
}
~
Obj
()
{
printf
(
"
destruct Obj: %d
\n
"
,
m_val
)
;
}
}
;
void
testScope
()
{
std
::
BlockPool
recycle
;
std
::
ScopeAlloc
alloc
(
recycle
)
;
printf
(
"
\n
------------------- global: have 3 objs ----------------
\n
"
)
;
{
Obj
*
a1
=
STD_NEW
(
alloc
,
Obj
)(
0
)
;
Obj
*
a2
=
STD_NEW_ARRAY
(
alloc
,
Obj
,
2
)
;
printf
(
"
------------------- child 1: have 4 objs ----------------
\n
"
)
;
{
std
::
ScopeAlloc
child1
(
alloc
)
;
Obj
*
o1
=
STD_NEW
(
child1
,
Obj
)(
1
)
;
Obj
*
o2
=
STD_NEW_ARRAY
(
child1
,
Obj
,
3
)
;
printf
(
"
------------------- child 11: have 3 objs ----------------
\n
"
)
;
{
std
::
ScopeAlloc
*
child11
=
STD_NEW
(
child1
,
std
::
ScopeAlloc
)(
child1
)
;
Obj
*
o11
=
STD_NEW
(
*
child11
,
Obj
)(
11
)
;
Obj
*
o12
=
STD_NEW_ARRAY
(
*
child11
,
Obj
,
2
)
;
}
printf
(
"
------------------- leave child 11 ----------------
\n
"
)
;
printf
(
"
------------------- child 12: have 3 objs ----------------
\n
"
)
;
{
std
::
ScopeAlloc
child12
(
child1
)
;
Obj
*
o11
=
STD_NEW
(
child12
,
Obj
)(
12
)
;
Obj
*
o12
=
STD_NEW_ARRAY
(
child12
,
Obj
,
2
)
;
}
printf
(
"
------------------- leave child 12 ----------------
\n
"
)
;
}
printf
(
"
------------------- leave child 1 ----------------
\n
"
)
;
printf
(
"
------------------- child 2: have 4 objs ----------------
\n
"
)
;
{
std
::
ScopeAlloc
child2
(
alloc
)
;
Obj
*
o1
=
STD_NEW
(
child2
,
Obj
)(
2
)
;
Obj
*
o2
=
STD_NEW_ARRAY
(
child2
,
Obj
,
3
)
;
}
printf
(
"
------------------- leave child 2 ----------------
\n
"
)
;
}
}
這個樣例中，child11是特別要注意的。請注意child11它是new出來的，我們忘記釋放它 4 。但是不要緊，在child1析構時，child11將會被刪除。
我們看到，有了ScopeAlloc，內存管理就可以層層規劃，成為一個內存管理樹（邏輯ScopeAlloc樹 5 ）。你可以忘記釋放內存（事實上你不能釋放，只能clear），ScopeAlloc會記得為你做這樣的瑣事。這正是GC Allocator的精髓。
ScopeAlloc的名字來由，看這個樣例就可以體會一二了。在《 C++內存管理變革(1): GC Allocator 》我們特別提到，內存管理有很強的區域性。在不同的區域（Scope），由于算法不同，而導致對Allocator需求亦不同。從總體上來講，ScopeAlloc有更好的適應性，適合更為廣泛的問題域。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
