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