本文已经迁移到： 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）的内存空间是多大。或者说，通常它们也许并不大。而在仅仅申请少量内存的情形下，使用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有更好的适应性，适合更为广泛的问题域。
