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操作（上一篇中已经简单介绍实现了），大体如下：

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]

 

使用样例：

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();

 

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;

}

 

---