C++内存管理变革

billdoors 2007-04-23

展开全文

引言

C/C++语言的内存管理经历了几次变革，但至今仍未能趋于成熟。这几次变革主要包括：

1. 从malloc/free到new/delete。这场变革是OOP技术兴起的产物。C++是强类型语言，new/delete的主要成果也就是加强了类型观念，减少了强制类型转换的需求。但是从内存管理角度看，这个变革并没有多少的突破性。

2. 从new/delete 到内存配置器（allocator）。自从STL被纳入C++标准库后，C++世界产生了巨大的变化。而从内存管理角度来看，allocator的引入也是C++内存管理一个突破。留意一下你就可以发现，整个STL所有组件的内存均从allocator分配。也就是说，STL并不推荐使用 new/delete进行内存管理，而是推荐使用allocator。

然而，STL的allocator并没有导致C++语言在内存管理上发生巨大的变化。除了STL本身外，并没有多少人使用allocator，甚至是意识到allocator的重要性。所以C++程序员在使用STL的同时，依旧在使用new/delete进行烦琐的内存分配/释放过程。

究其原因，主要有二。一是allocator的引入，STL设计者主要可能还是出于将内存管理从容器的实现独立出来的设计理念作用，让STL使用者在内存管理算法上有选择的余地。设计者本身都可能也没有意识到allocator的重要性。二是allocator本身也只是侧重于关注效率上，而没有侧重于C++语言使用者对内存管理观念的变革上。

总之，在我看来，STL的引入allocator，是一件了不起的事情。但是这场变革被忽视了，没有得到贯彻。当然，这也与STL的allocator本身的缺陷有关。

本文要讨论的，正是如何贯彻STL的allocator思想，对其进行适当的改进，以期在C++内存管理观念上产生变革性的突破，彻底淘汰传统的new/delete内存管理方法[1]。

垃圾回收器

几乎所有目前流行的垃圾回收器，均倾向于将使用者当作一个傻瓜，期望能够让使用者在完全不理解内存管理的情况下，可以很好的使用它。应该说这它们基本上都也做到了（虽然使用者有时也有这样那样的烦恼，但总体来说情况确实得到了很大程度的改善）。然而这一设计理念我并不十分认同。

首先，可以在一个提供垃圾回收器的语言中自如的工作，没有被垃圾回收器所困扰，本身已经是很了不起的事情，他们绝对是非常聪明的人，而不是傻瓜。他们理解垃圾回收器的工作原理，选择它并且让它为他们工作，只是因为还有更重要的事情等着他们去做。必要的时候，他们需要有办法控制垃圾回收器，使它按照他们的意愿工作。因此，垃圾回收器的设计要点在于把使用者从烦琐的内存管理中解脱出来，使得他们可以将全部精力投入到本身的业务逻辑上，而不是让垃圾回收器看起来更傻瓜式。

其次，使用一个全自动的垃圾回收器，在内存回收的时机不明确的情况下，垃圾回收器的工作过程有很大的不确定性，这给使用者带来烦恼。例如C#在调用非管制代码（如调用Win32 api）时，这些问题变得突出。一个不小心，就有可能出现Win32 api还在使用一块内存，而垃圾回收器已经把它回收了的情形。在小心翼翼的避开这些陷阱时，这种感觉其实与C/C++程序员遗憾语言没有垃圾回收器的感觉有点类似。

因此，最理想的情况，是内存管理器提供垃圾回收的能力，但是它也只是提供这个能力而已，至于什么时候进行垃圾回收，完全可以由用户自己控制。另外，用户也可以强制释放一块内存，而不是完全被动的等待垃圾回收过程决策何时回收该内存。对于客户来说，他有权掌控一切，只是如果万一他确实疏忽了，垃圾回收器能够为他护航。

将垃圾回收器引入C++，有没有这种可能呢？我认为，如果我们试图提供一个全自动的垃圾回收器，这相当困难。我们看到以Microsoft之能，仍然无法把这件事做好[2]。或许，我们需要改变一下观念：一个半自动的垃圾回收器，也许就可能可以和C++融洽相处了呢？

初识allocator

allacator中文称为“内存配置器”，通常它是一个类，负责提供内存管理（可能包含内存分配、释放、自动回收等能力）相关的服务。例如，我们通过C提供的malloc/free即刻提供一个allocator实作出来：

class SimpleAlloc
{
public:
    //注意这里提供的参数fnDestroy，它是为那些具备垃圾回收能力的allocator需要提供。
void* Alloc(size_t cb, FnDestructor fnDestroy = NULL)
    {
        return malloc(cb);
    }

    //注意这里有看似多余的参数cb，这完全是为了和后续提供的allocator规格一致的需要。
    void Free(void* data, size_t cb)
    {
        free(data);
    }
};

有了allocator，我们可以申请内存了，但是我们还不能用它创建一个C++对象。为了方便创建C++对象，我们提供了辅助的New操作，原型大体如下：

template <class Type, class AllocType>
Type* New(AllocType& alloc); // 类似于new Type

template <class Type, class ArgType1, class AllocType>
Type* New(ArgType1 arg1, AllocType& alloc); // 类似于new Type(arg1)

template <class Type, class AllocType>
Type* NewArray(size_t count, AllocType& alloc);// 类似于new Type[count]

有了这些辅助函数，我们就可以创建对象了。使用样例：

SimpleAlloc alloc;
int* intArray = NewArray<int>(count, alloc);
MyClass* obj = New<MyClass>(alloc);
MyClass* objWithArg = New<MyClass>(arg1, alloc);
MyClass* objArray = NewArray<MyClass>(count, alloc);

这里我们虽然使用SimpleAlloc创建对象，但是需要提醒的是，这些New操作对所有的allocator有效。如果你关心New函数的代码，先不急，下面我们马上就可以看到了。但是首先我们要继续讨论一下allocator。

allocator引起的观念变化

接触allocator，你可以体会到了它与C++传统的new/delete观念的不同。这主要有以下几点：

1. 每个类（或者算法）本身，均有最合适它的内存管理机制，并不是向C++传统的做法那样，使用一个全局的new/delete。也许你会说，C++不也允许一个类定义自己的new和delete吗？是的，C++的确支持类定义自己的new/delete，但注意，它的理念和allocator完全不同。我不认为它是C++的一个优秀之作，相反，它起到了误导作用。

因为，决定一个类对象怎么去new出来，并不是取决于该类本身，而相反是取决于使用该类的人。一个类不需要关心自身被如何创造出来，更不能假定。它需要关心的是它自己的类成员如何被创建出来，它的算法（你可以把类看做一个算法集合）涉及到的所有组件如何被创建出来。而这，才是allocator带来的观念。

让各种各样的allocator创建同一个类的不同实例，这些实例甚至可能在一起工作，相互协作。从STL的角度讲，这完全是最正常不过的事情了。

2. 重要的是由allocator创建管理对象，避免在你的代码中使用new/delete。如果可能，你可以如STL那样，将allocator作为模板参数，不绑定具体的某个内存管理器。但是，如果你的算法依赖了某个allocator的实现特有的功能，这也并不要紧。你的目的不是要做到 allocator的可替换，不是吗？重要的是使用了这个allocator了，它给你在内存管理上带来了益处。

但是，应该看到，STL实作的各种allocator，目前来看除了最简单使用malloc/free实现的外，主要就是基于 mempool技术。而该技术的目标，不是让内存使用者更加方便有效地进行内存管理，而更多的是关注于内存分配的时间性能。为了让C++程序员从内存管理中解脱出来，我们需要实作新的alloctor，需要新的突破！

新视角：具垃圾回收能力的Allocator

对，我设想的一个做法是，贯彻STL的allocator观念，并且提供具备特定的内存管理能力（例如垃圾回收）的各种 allocator。让C++社区广泛接受allocator观念，并且从中受益。C++程序员是时候抛弃传统的new/delete，让他们退出历史舞台了。

我接下来会实作两个具体的allocator（均属原创）。相信它们会让你耳目一新，让你不禁想到：哦，原来在C++中，我还可以这样进行内存管理。

当然，我最大的希望就是，这两个allocator能够起到抛砖引玉的作用，让大家也清楚地意识到allocator的重要性，可以出现更多的具备各种能力的allocator，解脱C++程序员一直以来的苦难（可能是最大苦难[3]）。

这两个allocator均具备一定程度的垃圾回收能力。只是观念上各有各的侧重。我们接下来会分为两个专题专门对它们进行阐述。

辅助的New过程

我们终于可以开始讨论前文提到的New函数的实现上了。以不带参数的New为例，它的代码如下，可能并没有你想象的那么复杂：

#include <new>

template <class Type, class AllocType>
inline Type* New(AllocType& alloc)
{
void* obj = alloc.Alloc(sizeof(Type), DestructorTraits<Type>::Destruct);
return new(obj) Type;
}

其中DestructorTraits是一个根据类型Type萃取[4]析构函数的萃取器。它看起来是这样的：

template <class Type>
struct DestructorTraits
{
    static void Destruct(void* pThis)
    {
        ((Type*)pThis)->~Type();
    }
};

这样，你就可以通过以下代码new出对象了：

MyClassA* obj = New<MyClassA>(alloc);
MyClassB* obj = New<MyClassB>(alloc);

特别提醒：这里New函数在VC++ 6.0下编译通过，但是产生的执行代码存在严重bug。如果你只New一类对象，没有问题，但在New了多种对象后，似乎VC++对MyClassA、 MyClassB 两者混淆起来了。为了支持VC++ 6.0，你需要对这里的New做出调整（关于这一点，详细请参考：VC++ 6.0小技巧）。

COM技术[5]与内存管理

已经准备结束这篇短文的时候，忽然想到了长久以来使用COM技术形成的一些感想，这些想法恰恰与内存管理紧密相关。故此想就这个问题陈述一下。

从COM的IUnknown接口看，它主要关注两个问题：一个是QueryInterface，一个是引用计数（AddRef/Release）。COM组件很讲究信息的屏蔽，使用者对组件的认识有限，这就给组件升级、扩充功能提供了可能。 QueryInterface是一个很好的概念，需要发扬光大。

COM的引用计数则关注的是组件的生命期维护问题。换句话说，就是组件如何销毁的问题。诚然，组件对象的销毁问题，是内存管理的关键。无论是COM的引用计数，还是垃圾回收技术，均是要解决对象的销毁问题。只是两者的侧重点不太一样，COM引用计数更关注“确保组件不会被提前销毁了，确保组件访问的安全性”，而垃圾回收器则关注“不管怎样确保组件最终被销毁，没有内存泄漏”。

在COM中，确保组件访问的安全性（避免非法访问），这个观点太重要了，以至于它甚至不惜加重程序员的内存管理负担。所以，在 COM程序中，出现内存泄漏太正常了，而且一旦泄漏通常就是大片大片内存的漏。更加要命的是，你甚至不能有一个很简单有效的方法确认这个泄漏是由于哪段代码引起。因为组件所有的客户都是平等的，任何一个客户代码存在问题均将导致内存的泄漏。

刚开始接触COM技术的时候，我对引用计数持的是比较正面的态度。但是随着部门逐步加大COM技术的使用力度后，四五年下来，我渐渐开始迷惑起来。一切并不如想象的那样。这个引用计数的背后，需要我们付出多少额外的代价！

而这个迷惑、思索，可能就是本文以及后续相关内容的成因吧。

C++内存管理变革(2)：最袖珍的垃圾回收器

概述

C/C++最被人诟病的，可能是没有一个内存垃圾回收器（确切是说没有一个标准的垃圾回收器）。本文讨论的内容要点是，在C/C++中实现一个最袖珍的、功能受限的垃圾回收器。这个垃圾回收器区别于其他垃圾回收器的主要特征是：

1. 袖珍但具实用性。整个垃圾回收器代码行数100行左右（不含空白行），相当小巧。相对而言，它的功能也受到一定的限制。但是它在很多关键的场合恰恰非常有用。该垃圾回收器以实用作为首要目标，已经成为我和身边一些同事编程的重要工具。　

2. 高性能。区别于其他垃圾回收器的是这个袖珍的垃圾回收器非但不会导致性能的下降，反而提高了程序的时间性能（分配的速度加快）和空间性能（所占内存空间比正常的malloc/new少）。而这也是实用的重要指标。

本文算法并不复杂。技术上的东西，很多点明了就没有什么了，也许重要的意义是在于其首创性。其实，boost[1]提供的pool组件也在试图提供类似功能的自动内存回收能力。但是实现相对复杂且低效（基于经典的mempool技术[2]）。

现在，你也许急着想看看，这个垃圾回收器长什么样了。闲话少叙，那就让我们就开始一步步把谜底揭开吧。

思路

理解该垃圾回收器的关键点在于，是在于理解它的目标：为一个复杂的局部过程（算法）提供自动内存回收的能力。　

所谓局部过程（算法），是指那些算法复杂性较高，但在程序运行期所占的时间又比较短暂的过程[3]。例如：搜索引擎的搜索过程、读盘/存盘过程、显示（绘制）过程等等。通常这些过程可能需要申请很多内存，而且内存分配操作的入口点很多（就是调用new的地方很多），如果每调用一次new就要考虑应该在什么地方delete就徒然浪费我们宝贵的脑力，使得我们无法把全力精力集中在算法本身的设计上。也许就是在这种情形下，C/C++程序员特别羡慕那些具备垃圾回收器的语言。相对而言，如果算法复杂性不高的话，我们的程序员完全有能力控制好 new/delete的匹配关系。并且，这种“一切皆在我掌控之中”的感觉给了我们安全感[4]和满足感。　

因此，这个垃圾回收器的重心并不是要提供一个理论上功能完备的内存自动回收机制。它只是针对复杂性较高的局部过程（算法），为他们提供最实效的内存管理手段。从局部过程的一开始，你就只管去申请、使用内存，等到整个算法完成之后，这个过程申请的大部分内存（需要作为算法结果保留的例外），无论它是在算法的那个步骤申请的，均在这个结束点上由垃圾回收器自动销毁。我们画个示意图：

图 1

规格

我们将该垃圾回收器命名为AutoFreeAlloc。它的接口很简单，仅涉及两个概念：Alloc、Clear。

typedef void (*FnDestructor)(void* pThis);

class AutoFreeAlloc
{
public:
    ~AutoFreeAlloc();                           // 析构函数。自动调用Clear释放内存
    void* Alloc(size_t cb);                     // 类似于malloc(cb)
    void* Alloc(size_t cb, FnDestructor fn);    // 申请内存并指定析构函数
    void Clear();                               // 析构并释放所有分配的对象
};

为了方便，提供辅助的New操作（上一篇中已经简单介绍实现了），大体如下：

使用样例：

AutoFreeAlloc alloc;

int* intArray = (int*)alloc.Alloc(sizeof(int)*count);
int* intArray2 = NewArray<int>(count, alloc);

MyClass* obj = New<MyClass>(alloc);
MyClass* objWithArg = New<MyClass>(arg1, alloc);
MyClass* objArray = NewArray<MyClass>(count, alloc);

alloc.Clear();

// …
// 现在，不能再访问intArray, obj, objWithArg, objArray等数据了。

内存管理机制

class AutoFreeAlloc
{
public:
    enum { BlockSize = 2048 };
private:
    struct _MemBlock
    {
        _MemBlock* pPrev;
        char buffer[BlockSize];
    };
    enum { HeaderSize = sizeof(_MemBlock) - BlockSize };

    char* m_begin;
    char* m_end;
};

AutoFreeAlloc类与内存管理相关的变量只有两个：m_begin、m_end。单从变量定义来看，基本上很难看明白。但是有了下面这张示意图就容易理解多了：

图 2

整个AutoFreeAlloc申请的内存，通过_MemBlock构成链表。只要获得了链表的头，就可以遍历整个内存链，释放所有申请的内存了。而链表的头(图中标为_ChainHeader)，可以通过m_begin计算得到：

_MemBlock* AutoFreeAlloc::_ChainHeader() const
{
return (_MemBlock*)(m_begin - HeaderSize);
}

为了使得_ChainHeader初始值为null，构造函数我们这样写：

AutoFreeAlloc::AutoFreeAlloc()
{
m_begin = m_end = (char*)HeaderSize;
}

★ 下面我们考虑内存分配过程。Alloc过程主要会有三种情况，具体代码为：

void* AutoFreeAlloc::Alloc(size_t cb)
{
    if (m_end – m_begin < cb)
    {
        if (cb >= BlockSize)
        {
                _MemBlock* pHeader = _ChainHeader();
                _MemBlock* pNew = (_MemBlock*)m_alloc.allocate(HeaderSize + cb);
                if (pHeader)
                {
                 pNew->pPrev = pHeader->pPrev;
    　             pHeader->pPrev = pNew;
                }
                else
                {
        　         m_end = m_begin = pNew->buffer;
            　     pNew->pPrev = NULL;
                }
                return pNew->buffer;        }
        else
        {
            _MemBlock* pNew = (_MemBlock*)malloc(sizeof(_MemBlock));
            pNew->pPrev = _ChainHeader();
            m_begin = pNew->buffer;
            m_end = m_begin + BlockSize;
        }
    }
    return m_end -= cb;
}

1. 最简单的情况，是当前_MemBlock还有足够的自由内存(free memory)，即：
m_end – m_begin >= cb
此时，只需要将m_end前移cb字节就可以了。我们画个示意图如下：

图 3　

2. 在当前的_MemBlock的自由内存（free memory）不足的情况下，我们就需要申请一个新的_MemBlock以供使用[5]。申请新的_MemBlock，我们又会遇到两种情况：

a) 申请的字节数（即cb）小于一个_MemBlock所能够提供的内存（即BlockSize）。
这种情况下，我们只需要将该_MemBlock作为新的当前_MemBlock挂到链表中，剩下的工作就和情形1完全类似。示意图如下：

图 4

b) 而在内存申请的字节数（即cb）大于或等于一个Block的字节数时，我们需要申请可使用内存超过正常长度（BlockSize）的_MemBlock。这个新生成的_MemBlock全部内存被用户申请。故此，我们只需要修改_ChainHeader的pPrev指针，改为指向这一块新申请的_MemBlock即可。m_begin、m_end保持不变（当前的_MemBlock还是当前的_MemBlock）。如图：

图 5

★ 下面我们考虑内存释放（Clear）过程。这个过程就是遍历_MemBlock释放所有的_MemBlock的过程，非常简单。代码如下：

void AutoFreeAlloc::Clear()
{
    _MemBlock* pHeader = _ChainHeader();
    while (pHeader)
    {
        _MemBlock* pTemp = pHeader->pPrev;
        free(pHeader);
        pHeader = pTemp;
    }
    m_begin = m_end = (char*)HeaderSize;
}

自动析构过程

我们知道，C++以及其他面向对象语言为对象引入了构造、析构过程。这是一个了不起的发明。因为只有这样，才能够保证对象从一开始产生以来（刚new出来），到对象销毁这整个过程，它的数据都处于完备状态，是自洽的。

由于垃圾回收器负责对象的回收，它自然不止需要关注对象申请的内存的释放，同时也需要保证，在对象销毁之前它的析构过程被调用。上文我们为了关注内存管理过程，把自动析构过程需要的代码均去除了。为了支持自动析构，AutoFreeAlloc类增加了以下成员：

class AutoFreeAlloc
{
    struct _DestroyNode
{
        _DestroyNode* pPrev;
        FnDestructor fnDestroy;
    };
    _DestroyNode* m_destroyChain;
};

如果一个类存在析构，则它需要在Alloc内存的同时指定析构函数。代码如下：

void* AutoFreeAlloc::Alloc(size_t cb, FnDestructor fn)
{
    _DestroyNode* pNode = (_DestroyNode*)Alloc(sizeof(_DestroyNode) + cb);
    pNode->fnDestroy = fn;
    pNode->pPrev = m_destroyChain;
    m_destroyChain = pNode;
    return pNode + 1;
}

只要通过该Alloc函数申请的内存，我们在Clear中就可以调用相应的析构。当然，Clear函数需要补充自动析构相关的代码：

void AutoFreeAlloc::Clear()
{
    while (m_destroyChain)
    {
        m_destroyChain->fnDestroy(m_destroyChain + 1);
        m_destroyChain = m_destroyChain->pPrev;
    }
    // 以下是原先正常的内存释放过程…
}

时间性能分析

void* AutoFreeAlloc::Alloc(size_t cb);

OOP技术带来一个内存上的问题是，对象粒度越来越细了，对象基本上都是小对象。这就对内存管理的性能提出了很高的要求。　

如果我们以对象大小平均为32字节计算的话，每2048/32 = 64操作中，只有一次操作满足m_end – m_begin < cb的条件。也就是说，在通常情况（63/64 = 98.4%的概率）下，Alloc操作只需要一个减法操作就完成内存分配。

我说这是世界上最快速的内存分配算法，也许你对此仍然抱有怀疑态度。但是可以肯定的一点是，要突破它的性能极限我觉得已经很难很难了。　

void AutoFreeAlloc::Clear();

一般内存管理器通常一次内存分配操作就需调用相应的一次Free操作。但是AutoFreeAlloc不针对每一个Alloc进行释放，而是针对每一个_MemBlock。仍假设对象平均大小为32字节的话，也就是相当于把64次Alloc操作合并，为其提供一次相应的Free过程。

★ 结论：AutoFreeAlloc在时间上的性能，大约比普通的malloc/free的快64倍。

空间性能分析

我们知道，一般内存管理器为了将用户申请的内存块管理起来，除了用户需要的cb字节内存外，通常额外还提供一个内存块的头结构，通过这个头结构将内存串连成为一个链表。一般来讲，这个头结构至少有两项（可能还不止），示意如下：

struct MemHeader
{
MemHeader* pPrev;
size_t cb;
};

仍然假设平均Alloc一次的内存为32字节。则一次malloc分配过程，就会浪费8/32 = 25%的内存。并且由于大量的小对象存在，整个内存中的碎片（指那些自由但无法被使用的内存）将特别严重。

而AutoFreeAlloc的Alloc没有如何额外开销。整个AutoFreeAlloc，只有在将_MemBlock串为链表的有一个额外的 pPrev指针，加上_MemBlock是malloc出来的，有额外的8字节开销。总计浪费(4+8)/2048 = 0.6%的内存，几乎可以忽略不计。　

后记

AutoFreeAlloc于2004-5-21开发，只有100行的代码量。但是，这个组件获得了空前的成功，它的应用范围逐步扩大，超过了我最初实现这个组件时的预计。

我渐渐冷静下来，考虑这其中蕴涵的道理。我逐步领会到了，它的成功之处，不是它在时间、空间性能的高效，而是在于它帮助C++程序员解决了最大的难题——内存管理。虽然，这个解决方案并不是完整的。

AutoFreeAlloc是一个切入点，从它身上，让我明白了C++的new/delete的不合理；STL引入的allocator是一个切入点，从它身上，让我明白了内存管理有很强的区域性，在不同的区域（局部过程）中对allocator的需求却又不尽相同。

我们前文也提到了一个例子：一个文档打开，编辑，直到文档被最终关闭，这个完成算不算局部过程呢？在AutoFreeAlloc解决的问题域来看，显然我们无法认为它是一个局部过程。但是，从其他allocator角度来讲，是否就有可能把它作为一个局部过程了呢？

正是考虑到AutoFreeAlloc的缺陷，我们需要一个功能更强的垃圾回收器。这就是我们下一次需要讨论的组件了。

最后，仍然需要明确的一点时。我们很难也不需要实现一个象Java、C#那样的垃圾回收器。提供一个具备特定的内存管理能力的allocator才是正道。

[1] 请参考boost官方网站http://www./。

[2] mempool技术是一个很成熟的内存管理技术，被sgi-stl、boost等C++库实现者采用。

[3] 真正是否要把一个过程定义为局部过程，完全取决于设计者本身。例如，一个文档打开，编辑，直到文档被最终关闭，这个完成算不算局部过程呢？在大部分情况下我们认为它不是一个局部过程，但是下回我们将专门讨论是否有可能，以及应该如何将它作为一个局部过程。

[4] 那些提供了垃圾回收器的语言的使用者，显然也有应用了垃圾回收器的烦恼。例如C#在调用非管制代码（如调用Win32 api）时，这些问题变得突出，一个疏忽就留下潜在隐患。这与C/C++程序员遗憾语言没有垃圾回收器的感觉类似。

[5] 当前的_MemBlock的自由内存很可能还是有的，但是不足cb字节。此时我们说这里有内存碎片（memory piece）：这些碎片尽管没有人使用，但是我们把它弃而不用。

附加说明：

本文所描述的AutoFreeAlloc组件，完整代码可在WINX库中找到。你也可以通过以下链接在线浏览：

AutoFreeAlloc完整源代码

另外，这篇文章写的时间较早，其规格虽然与现在的AutoFreeAlloc一样，但成员函数名改了：

Alloc -> allocate
Clear -> clear

之所以这样，是因为AutoFreeAlloc被纳入stdext库（这个库可独立于winx界面库，是winx界面库的基础）。stdext库的命名风格尽量与STL的命名习惯一致。

相关文章：《C++内存管理变革》

C++内存管理变革(3)：另类内存管理

最简单的C++/Java程序

最简单的Java程序:

class Program
{
   public static void main()
   {
       new int;
   }
}

对应的C++程序:

void main()
{
new int;
}

我想没有一个Java程序员会认为上面的Java代码存在问题。但是所有严谨的C++程序员则马上指出：上面这个C++程序有问题，它存在内存泄漏。但是我今天想和大家交流的一个观念是：这个C++程序没有什么问题。

DocX程序的内存管理

DocX是我开发的一个文档撰写工具。这里有关于它的一些介绍。在这一小节里，我要谈谈我在DocX中尝试的另类内存管理方法。

DocX的总体流程是：

读入一个C++源代码（或头）文件（.h/.c/.hpp/.cpp等），分析其中的注释，提取并生成xml文档。
通过xslt变换，将xml文档转换为htm。
分析源代码中的所有include指令，取得相应的头文件路径，如果某个头文件没有分析过，跳到1反复这些步骤。
最后所有生成的htm打包生成chm文件。

一开始，我象Java/C#程序员做的那样，我的代码中所有的new均不考虑delete。当然，它一直运作得很好，直到有一天我的文档累计到了一定程度后。正如我们预见的那样，DocX程序运行崩溃了。

那么，怎么办呢？找到所有需要delete的地方，补上delete？

这其实并不需要。在前面，我给大家介绍了AutoFreeAlloc（参见《C++内存管理变革(2)：最袖珍的垃圾回收器》），也许有人在嘀咕，这样一个内存分配器到底有何作用。——那么，现在你马上可以看到它的典型用法之一了：

对于我们的DocX崩溃后，我只是做了以下改动：

加一个全局变量：std::AutoFreeAlloc alloc;
所有的new Type(arg1, arg2, …, argn)，改为STD_NEW(alloc, Type)(arg1, arg2, …, argn);
所有的new Type[n]，改为STD_NEW_ARRAY(alloc, Type, n);
每处理完一个源代码文件时，调用一次alloc.clear();

搞定，自此之后，DocX再也没有内存泄漏，也不再有遇到内存不足而崩溃的情形。

只读DOM模型（或允许少量修改）的建立

在《文本分析的三种典型设计模式》一文中我推荐大家使用DOM模型去进行文件操作。并且通常情况下，这个DOM模型是只读DOM模型（或允许少量修改）。

对于只读DOM模型，使用AutoFreeAlloc是极其方便的。整个DOM树涉及的内存统一由同一个AutoFreeAlloc实例进行分配。大体如下：

class Document;
class ObjectA
{
private:
    Document* m_doc;
    SubObject* m_c;

public:
    ObjectA(Document* doc) : m_doc(doc) {
        m_c = STD_NEW(doc->alloc, SubObject);
    }

    SubObject* getC() {
        return m_c;
    }
};

class Document
{
public:
    AutoFreeAlloc alloc;

private:
    ObjectA* m_a;
    ObjectB* m_b;

public:
    ObjectA* getA() {
        if (m_a == NULL)
            m_a = STD_NEW(alloc, ObjectA)(this);
        return m_a;
    }
};

通过这种方式创建的DOM模型，只要你删除了Document对象，整个DOM树自然就被删除了。你根本不需要担心其中有任何内存泄漏的可能。

另类内存管理的观念

通过以上内容，我试图向大家阐述的一个观点是：

有了AutoFreeAlloc后，C++程序员也可以象GC语言的程序员一样大胆new而不需要顾忌什么时候delete。

展开来讲，可以有以下结论：

如果你程序的空间复杂度为O(1)，那么只new不delete是没有问题的。
如果你程序的空间复杂度为O(n)，并且是简单的n*O(1)，那么可以用AutoFreeAlloc简化内存管理。
如果你程序的空间复杂度为O(t)，其中t是程序运行时间，并且你不能确定程序执行的总时间，那么AutoFreeAlloc并不直接适合你。比较典型的例子是Word、Excel等文档编辑类的程序。

用AutoFreeAlloc实现通用型的GC

AutoFreeAlloc对内存管理的环境进行了简化，这种简化环境是常见的。在此环境下，C++程序员获得了无可比拟的性能优势。当然，在一般情形下，AutoFreeAlloc并不适用。

那么，一个通用的半自动GC环境在C++是否可能？《C++内存管理变革》系列的核心就是要告诉你：当然可以。并且，我们推荐C++程序员使用半自动的GC，而不是Java/C# 中的那种GC。

通用的半自动GC环境可以有很多种建立方式。这里我们简单聊一下如何使用AutoFreeAlloc去建立。

我们知道，使用AutoFreeAlloc，将导致程序随着时间推移，逐步地吃掉可用的内存。假设现在已经到达我们设置的临界点，我们需要开始 gc。整个过程和Java等语言的gc其实完全类似：通过一个根对象（Object* root），获得所有活动着的对象（Active Objects），将它们复制到一个新的AutoFreeAlloc中：

Object* gc(AutoFreeAlloc& oldAlloc, Object* root, AutoFreeAlloc& newAlloc)
{
    Object* root2 = root->clone(newAlloc);
    oldAlloc.clear();
    return root2;
}

如果C++象Java/C#那样有足够丰富的元信息，那么Object::clone过程就可以象Java/C# 等语言那样自动完成。这些元信息对于GC过程的用处无非在于，我们可以遍历整个活动对象的集合，然后把这些活动对象复制一份。没有复制过来的对象自然而然就被丢弃了。

GC的原理就是这么简单。没有元信息也没关系，只要我们要求每个由GC托管的对象支持clone函数，一切就ok了。对于一个复杂程序，要求每个对象提供clone函数不见得是什么过分的要求，clone函数也不只有gc过程才需要，很多对象在设计上天然就需要clone。

补充说明

关于全局AutoFreeAlloc变量

我个人非常不推荐使用全局变量（除非是常量：不一定用const修饰，指的是经过一定初始化步骤后就不在修改的变量）。上面只是对于小型的单线程程序偷懒才这样做。

关于用AutoFreeAlloc实现通用型的GC

请注意我没有讨论过于细节的东西。如果你决定选择这种做法，请仔细推敲细节。可以预见的一些细节有：

AutoFreeAlloc与线程模型（ThreadModel）。AutoFreeAlloc关注点在于快，它通常不涉及跨线程问题。但是如果要作为通用型的GC，这一点不能不考虑。为了性能，推荐每个线程独立管理内存，而不要使用互斥体。
性能优化。可以考虑象Java的GC那样，使用两个AutoFreeAlloc，把对象划分为年轻代和年老代。

C++内存管理变革(4): boost::object_pool

许式伟 (版权声明)
2007-4-21

这篇文章拖的有点久了。NeutralEvil 在3个月之前就在催促我继续写了。只是出于WinxGui完整性的考虑，我一直在刻意优先去补充其它方面的文章，而不是让人去误会WinxGui是一个内存管理库了。:)

言归正传。我们在内存池(MemPool)技术详解已经介绍了boost::pool组件。从内存管理观念的变革来看，这是是一个传统的MemPool组件，尽管也有一定的改进（但只是性能上的改进）。但boost::object_pool不同，它与我在C++内存管理变革强调的观念非常吻合。可以认为，boost::object_pool是一种不通用的gc allocator组件。

我已经多次提出gc allocator的概念。这里仍然需要强调一下，所谓gc allocator，是指具垃圾回收能力的allocator。C++内存管理变革(1) 中我们引入了这个概念，但是没有明确gc allocator一词。

boost::object_pool内存管理观念

boost::object_pool的了不起之处在于，这是C++从库的层次上头一次承认，程序员在内存管理上是会犯错误的，由程序员来确保内存不泄漏是困难的。boost::object_pool允许你忘记释放内存。我们来看一个例子：

    class X { … };

    void func()
    {
        boost::object_pool<X> alloc;

        X* obj1 = alloc.construct();
        X* obj2 = alloc.construct();
        alloc.destroy(obj2);
    }

如果boost::object_pool只是一个普通的allocator，那么这段代码显然存在问题，因为obj1的析构函数没有执行，申请的内存也没有释放。

但是这段代码是完全正常的。是的，obj1的析构确实执行了，所申请内存也被释放了。这就是说，boost::object_pool既支持你手工释放内存（通过主动调用object_pool::destroy），也支持内存的自动回收（通过object_pool::~object_pool析构的执行）。这正符合gc allocator的规格。

注：内存管理更好的说法是对象管理。内存的申请和释放更确切的说是对象的创建和销毁。但是这里我们不刻意区分这两者的差异。

boost::object_pool与AutoFreeAlloc

我们知道，AutoFreeAlloc不支持手工释放，而只能等到AutoFreeAlloc对象析构的时候一次性全部释放内存。那么，是否可以认为boost::object_pool是否比AutoFreeAlloc更加完备呢？

其实不然。boost::object_pool与AutoFreeAlloc都不是完整意义上的gc allocator。AutoFreeAlloc因为它只能一次性释放，故此仅仅适用特定的用况。然而尽管AutoFreeAlloc不是普适的，但它是通用型的gc allocator。而boost::object_pool只能管理一种对象，并不是通用型的allocator，局限性其实更强。

boost::object_pool的实现细节

大家对boost::object_pool应该已经有了一个总体的把握。现在，让我们深入到object_pool的实现细节中去。

在内存池(MemPool)技术详解中，我们介绍boost::pool组件时，特意提醒大家留意pool::ordered_malloc/ordered_free函数。事实上，boost::object_pool的malloc/construct, free/destroy函数调用了pool::ordered_malloc, ordered_free函数，而不是pool::malloc, free函数。

让我们解释下为什么。

其实这其中的关键，在于object_pool要支持手工释放内存和自动回收内存（并自动执行析构函数）两种模式。如果没有自动析构，那么普通的MemPool就足够了，也就不需要ordered_free。既然有自动回收，同时又存在手工释放，那么就需要区分内存块（MemBlock）中哪些结点（Node）是自由内存结点（FreeNode），哪些结点是已经使用的。对于哪些已经是自由内存的结点，显然不能再调用对象的析构函数。

我们来看看object_pool::~object_pool函数的实现：

template <typename T, typename UserAllocator>
object_pool<T, UserAllocator>::~object_pool()
{
  // handle trivial case
  if (!this->list.valid())
    return;

  details::PODptr<size_type> iter = this->list;
  details::PODptr<size_type> next = iter;

  // Start ’freed_iter’ at beginning of free list
  void * freed_iter = this->first;

  const size_type partition_size = this->alloc_size();

  do
  {
    // increment next
    next = next.next();

    // delete all contained objects that aren’t freed

    // Iterate ’i‘ through all chunks in the memory block
    for (char * i = iter.begin(); i != iter.end(); i += partition_size)
    {
      // If this chunk is free
      if (i == freed_iter)
      {
        // Increment freed_iter to point to next in free list
        freed_iter = nextof(freed_iter);

        // Continue searching chunks in the memory block
        continue;
      }

      // This chunk is not free (allocated), so call its destructor
      static_cast<T *>(static_cast<void *>(i))->~T();
      // and continue searching chunks in the memory block
    }

    // free storage
    UserAllocator::free(iter.begin());

    // increment iter
    iter = next;
  } while (iter.valid());

  // Make the block list empty so that the inherited destructor doesn’t try to
  //  free it again.
  this->list.invalidate();
}

这段代码不难理解，object_pool遍历所有申请的内存块（MemBlock），并遍历其中所有结点（Node），如果该结点不出现在自由内存结点（FreeNode）的列表（FreeNodeList）中，那么，它就是用户未主动释放的结点，需要进行相应的析构操作。

现在你明白了，ordered_malloc是为了让MemBlockList中的MemBlock有序，ordered_free是为了让FreeNodeList中的所有FreeNode有序。而MemBlockList, FreeNodeList有序，是为了更快地检测Node是自由的还是被使用的（这实际上是一个集合求交的流程，建议你看看std:: set_intersection，它定义在STL的<algorithm>中）。