C++内存管理变革(6):通用型垃圾回收器 - ScopeAlloc

引言

在前文,我们引入了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内部计算用的临时内存在该步骤结束时释放。示意图如下:

ScopeAlloc.png

图1

由于引入私有存储(Private GC Allocator),模型看起来就变得很复杂。上面这个图也许让你看晕了。不过没有关系,我们把上图中与步骤i相关的内容独立出来看,得到下图:

ScopeAlloc2.png

图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_NEWStdExt库中用于生成对象实例的宏,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有更好的适应性,适合更为广泛的问题域。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License

Subscription expired — please renew

Pro account upgrade has expired for this site and the site is now locked. If you are the master administrator for this site, please renew your subscription or delete your outstanding sites or stored files, so that your account fits in the free plan.