要获取本文档的 PDF 格式副本，请单击 此处（或从 Google Code 获取）。HTML 格式的副本也可在 Google Docs 上找到。

引言

大多数 C++ 程序员无法从“垃圾回收”（GC）技术中获益。他们厌倦了需要手动删除对象。有一些 C/C++ 的 GC 实现，但它们复杂且未被广泛使用。

我将介绍一种新的内存管理技术，名为“GC 分配器”。“GC 分配器”不是一种实现，而是一种概念。现在，我们有两种“GC 分配器”的实现，分别名为“AutoFreeAlloc”和“ScopeAlloc”。

本文由三部分组成：

1. 什么是 GC 分配器？
2. GC 分配器实现：ScopeAlloc 和 AutoFreeAlloc
3. 基于 GC 分配器的应用

什么是 GC 分配器？

1. 它是一个用于分配内存的分配器。
2. 一个更好的智能指针。
3. 创建 GC 分配器和分配内存应该非常快。
4. 另一种GC 的方式。

GC 分配器的概念

GC 分配器只是一种概念。以下是 GC 分配器的最小规格。

typedef void (*DestructorType)(void* data);
 
concept GCAllocator
{
    // Allocate memory without given a cleanup function
    void* allocate(size_t cb);
 
    // Allocate memory with a cleanup function
    void* allocate(size_t cb, DestructorType fn);
 
    // Cleanup and deallocate all allocated memory by this GC Allocator
    void clear();

    // Swap two GCAllocator instances
    void swap(GCAllocator& o);
};

当您创建 GC 分配器时，可以使用 _STD_NEW_、_STD_NEW_ARRAY_ 来创建对象。让我们看一个非常简单的例子。

GCAllocator alloc(initArgs); // initArgs depends on implementation
 
int* intObj = STD_NEW(alloc, int);
int* intObjWithArg = STD_NEW(alloc, int)(10);
int* intArray = STD_NEW_ARRAY(alloc, int, count);
 
MyObj* obj = STD_NEW(alloc, MyObj);
MyObj* objWithArg = STD_NEW(alloc, MyObj)(100);
MyObj* objArray = STD_NEW_ARRAY(alloc, MyObj, count);

坦率地说，我不喜欢 _STD_NEW_ 和 _STD_NEW_ARRAY_。我希望能够使用以下语法：

GCAllocator alloc(initArgs);
 
int* intObj = new(alloc) int;
int* intObjWithArg = new(alloc) int(10);
int* intArray = new(alloc) int[count];
 
MyObj* obj = new(alloc) MyObj;
MyObj* objWithArg = new(alloc) MyObj(100);
MyObj* objArray = new(alloc) MyObj[count];

更好的智能指针

C++ 程序员厌倦了手动删除对象。因此，他们发明了一种名为“智能指针”的技术。有很多智能指针的实现。最简单的是 std::auto_ptr。下面是一个例子：

{
    std::auto_ptr<MyObj> obj(new MyObj);
    std::auto_ptr<AnotherObj> obj2(new AnotherObj);
    ... // use obj and obj2 to do something.
}

如果不使用智能指针，您必须编写以下代码：

{
    MyObj* obj = new MyObj;    
    AnotherObj* obj2;
    try
    {
        obj2 = new AnotherObj;
    }
    catch(...}
    {
        delete obj;
        throw;
    }
    try
    {
        ... // use obj and obj2 to do something.
    }
    catch(...)
    {
        delete obj2;
        delete obj;
        throw;
    }
    delete obj2;
    delete obj;
}

当您使用 GC 分配器时，您可以执行与以下相同的操作：

{
    GCAllocator alloc(initArgs); // initArgs depends on implementation
 
    MyObj* obj = STD_NEW(alloc, MyObj);
    AnotherObj* obj2 = STD_NEW(alloc, AnotherObj);
    ... // use obj and obj2 to do something.
}

我认为 GC 分配器是一个更好的智能指针。为什么？

首先，如果您使用智能指针技术，当您需要数组时，您必须为数组对象实现一个新的智能指针类型。以下代码效果不佳：

{
    std::auto_ptr<MyObj> objArray(new MyObj[count]);
    // ---> Error!!! You can't pass an array pointer to the auto_ptr constructor.
 
    ... // use objArray to do something.
}

但当您使用 GC 分配器时，这只是小菜一碟。

{
    GCAllocator alloc(initArgs); // initArgs depends on implementation
 
    MyObj* objArray = STD_NEW_ARRAY(alloc, MyObj, count);
    ... // use objArray to do something.
}

其次，大多数智能指针实现（例如 boost::shared_ptr、ATL::CComPtr 等）都基于“引用计数”技术。当算法需要返回新对象时，“引用计数”是一个常见的解决方案。例如：

boost::shared_ptr<MyObj> algorithm(...)
{
    boost::shared_ptr<MyObj> obj(new MyObj);
    ...
    return obj;
}

但“引用计数”确实不是一个好解决方案。

1. Windows COM（基于“引用计数”）程序员厌倦了无休止的内存泄漏。
2. 事实上，并非所有 C++ 程序员都喜欢智能指针，也并非所有 C++ 程序员都喜欢相同的智能指针。您必须在普通指针和智能指针之间，或在一个智能指针和另一个智能指针之间进行转换。这样事情就会变得复杂且难以控制。
3. 存在循环引用的风险。
4. 当对象具有“引用计数”时，跟踪内存泄漏更加困难。

当您使用 GC 分配器时，如果算法需要返回新对象，GC 分配器实例将被传递给该算法。

template <class AllocT>
MyObj* algorithm(AllocT& alloc, ...)
{
    MyObj* obj = STD_NEW(alloc, MyObj);
    ...
    return obj;
}

注意，分配器实例 _alloc_ 作为模板类 AllocT 传递。在本文开头，我说过 GC 分配器不是实现，而是概念。现在您知道我为什么这么说：大多数算法不需要关心 _alloc_ 实例是什么。

最后，“智能指针”已过时，您所使用的只是普通指针。这非常重要。这使得使用“GC 分配器”的代码能够与不使用“GC 分配器”的代码很好地协同工作。

创建 GC 分配器和分配内存应该非常快。

大多数分配器实现都优化了大量对象的分配。如果一个分配器实例只分配一个对象实例，它们会比普通的 new/delete 分配慢。当我们把 GC 分配器视为智能指针时，即使它只分配一个对象实例，它也应该很快。

让我们看看我们的一个测试结果：

有关比较的详细信息，请参阅“分配器性能比较”。令人兴奋的是，ScopeAlloc 的速度明显快于普通 new/delete 分配，而 AutoFreeAlloc 的速度也接近普通 new/delete 分配。

另一种 GC 的方式

我认为 GC 分配器是 GC 的另一种方式。当然，GC 分配器不像 Java 或 C# 中的 GC 那样工作。事实上，我们 GC 分配器实现的核心源代码只有大约 100 行代码！它不做太多事情，但做最重要的事情。

通常，GC 分配器对算法的抽象如下：

一个算法可能有两个 GC 分配器实例。一个名为“私有 GC 分配器”。另一个名为“共享 GC 分配器”。如果一个对象将被返回，它将被分配给“共享 GC 分配器”。如果一个对象将在算法结束时被销毁，它将被分配给“私有 GC 分配器”。伪代码如下：

ResultDOM* algorithm(GCAllocator& sharedAlloc, InputArgs args)
{
    GCAllocator privateAlloc(sharedAlloc);
    ...
    ResultDOM* result = STD_NEW(sharedAlloc, ResultDOM);
    ResultNode* node = STD_NEW(sharedAlloc, ResultNode);
    result->addNode(node);
    ...
    TempVariable1* temp1 = STD_NEW(privateAlloc, TempVariable1);
    TempVariable2* temp2 = STD_NEW(privateAlloc, TempVariable2);
    ...
    return result;
}

私有 GC 分配器（名为 _privateAlloc_）的工作方式类似于“智能指针”。但与“智能指针”不同的是，一个 GC 分配器实例管理一组对象，而不是一个接一个地管理。

如果私有分配的对象数量很少，则 _privateAlloc_ 是不需要的。此时算法将如下所示：

ResultDOM* algorithm(GCAllocator& alloc, InputArgs args)
{
    ResultDOM* result = STD_NEW(alloc, ResultDOM);
    ResultNode* node = STD_NEW(alloc, ResultNode);
    result->addNode(node);
    ...
    TempVariable1* temp1 = STD_NEW(alloc, TempVariable1);
    TempVariable2* temp2 = STD_NEW(alloc, TempVariable2);
    ...
    return result;
}

在任何情况下，您都不需要手动删除对象。这就是为什么我称 GCAllocator 为“GC 分配器”。

GC 分配器实现：ScopeAlloc 和 AutoFreeAlloc

我们有两种“GC 分配器”实现，分别名为“AutoFreeAlloc”和“ScopeAlloc”。以下是本节的简要总结：

1. 性能：它们比您见过的所有其他分配器都快。
2. ScopeAlloc 和 AutoFreeAlloc 的基础设施。
3. 一个巨大的堆栈。
4. 只有大约 100 行核心代码。
5. 无多线程锁（无需）。
6. 何时使用 AutoFreeAlloc。
7. 开源。

比你见过的所有分配器都快

我们对以下分配器进行了性能比较：

• AutoFreeAlloc
• ScopeAlloc
• APR Pools（Apache Portable Runtime）
• MT Allocator（GNU C++）
• Boost Pool（boost::pool）
• Boost ObjectPool（boost::object_pool）
• NewDelete（new/delete）

在 Linux 平台上，我们得到了以下结果：

在 Windows 平台上，我们得到了以下结果（我删除了 NewDelete 条形图，因为它太慢了）：

有关比较的详细信息，请参阅“分配器性能比较”。

为什么 ScopeAlloc 和 AutoFreeAlloc 如此之快？它们受益于：

1. 其良好的分配算法。
2. 无多线程锁。
3. C++ 內联函数。

ScopeAlloc 和 AutoFreeAlloc 的基础设施

ScopeAlloc 和 AutoFreeAlloc 的基础设施如下：

有三个基本概念：SystemAlloc、BlockPool 和 GCAlloc。

SystemAlloc 是底层系统内存管理服务的抽象。它只是 C 运行时 malloc/free 过程的包装器。

class SystemAlloc
{
public:
    void* allocate(size_t cb) { return malloc(cb); }
    void deallocate(void* p)  { free(p); }
    void swap(SystemAlloc& o) {}
};

BlockPool 是一个内存池。它作为一个缓存池来加速内存分配速度。BlockPool 提供与 SystemAlloc 相同的接口。

class BlockPool
{
public:
    BlockPool(int cacheSize = INT_MAX);
 
    void* allocate(size_t cb);
    void deallocate(void* p);
    void swap(BlockPool& o);
};

为什么 BlockPool 可以加速内存分配速度？不是因为 BlockPool 是内存池（您知道 SystemAlloc 也可能通过使用内存池技术实现），而是因为 BlockPool 不需要多线程锁。

最后一个概念是 GCAlloc。它是 GC 分配器的核心。而且它只有大约 100 行核心代码！

GCAlloc：一个巨大的堆栈

GCAlloc 的实现类名为“GCAllocT”。它提供了以下接口：

template <class _Alloc>
class GCAllocT
{
public:
    GCAllocT();
    explicit GCAllocT(const _Alloc& alloc);
    explicit GCAllocT(GCAllocT& owner);
 
    // Allocate memory without given a cleanup function
    void* allocate(size_t cb);
 
    // Allocate memory with a cleanup function
    void* allocate(size_t cb, DestructorType fn);
 
    // Cleanup and deallocate all allocated memory by this GC Allocator
    void clear();
 
    // Swap two GCAllocator instances
    void swap(GCAllocT& o);
};
 
typedef GCAllocT<SystemAlloc> AutoFreeAlloc;
typedef GCAllocT<ProxyBlockPool> ScopeAlloc;

AutoFreeAlloc 和 ScopeAlloc 都基于 GCAllocT。唯一不同的是，AutoFreeAlloc 基于 SystemAlloc（全局 malloc/free 分配过程），而 ScopeAlloc 基于 BlockPool（一个缓存分配器，用于加速内存分配速度）。

由于这种差异，AutoFreeAlloc 和 ScopeAlloc 具有显著的性能差异。

ScopeAlloc 在任何情况下都具有最佳性能。如果我们分配足够的对象，AutoFreeAlloc 的性能接近 ScopeAlloc。

有关详细信息，请参阅“分配器性能比较”。

您知道，最快的“分配器”是“堆栈”。C/C++ 在“堆栈”上分配自动对象（也称为“堆栈对象”）。但“堆栈”有很多限制：

1. 退出过程时，所有“堆栈对象”都将被销毁。因此，您无法返回“堆栈对象”。
2. 您不能分配太多的“堆栈对象”，因为“堆栈”的大小是有限的。

GCAlloc 的基本思想实现为堆上的“巨大堆栈”。它的性能与“堆栈”相似。我在这里不解释详细实现。如果您想深入了解，请参考源代码。

无多线程锁

为什么 GC 分配器不需要多线程锁？

Memory allocation = System memory block management + Memory management algorithm

底层的系统内存块管理由操作系统提供。它会优化大内存块的分配（支持小对象分配，但不需要优化）。并且它是线程/进程安全的。

内存管理算法由 C/C++ 运行时库或其他库提供。内存管理算法只是算法。大多数算法都设计为线程安全的。

如果我们使用全局 new/delete 或 malloc/free 过程来分配内存，线程安全是必须的（因为所有线程都使用这些过程），而不是可选的。但是如果我们使用分配器实例来管理内存，那么线程安全就变成了可选的。

为什么？不建议在多线程中共享 GC 分配器。这意味着也不建议在线程之间共享内存。如果您真的想共享内存，请使用 new/delete 或其他任何方式。

对于 GC 分配器的用户，我们建议每个线程只使用一个 BlockPool 实例，并且一个线程可以使用多个私有的“ScopeAlloc”实例（取决于您的需求）来分配内存。

这使得 ScopeAlloc 成为最快的分配器！

何时使用 AutoFreeAlloc

您知道，ScopeAlloc 在任何情况下都比 AutoFreeAlloc 快。那么您可能会想，何时使用 AutoFreeAlloc。以下是一些您可以考虑使用 AutoFreeAlloc 的情况：

1. 一个不希望接受 BlockPool 或 ScopeAlloc 参数的算法。如果我们使用 ScopeAlloc，我们需要一个 BlockPool 或 ScopeAlloc 实例来构造一个新的 ScopeAlloc 对象。但在某些情况下，我们不希望用户知道使用 ScopeAlloc 的实现细节。
2. 一个需要大量内存分配的算法。如果我们分配足够的对象，AutoFreeAlloc 的性能接近 ScopeAlloc（请参阅“分配器性能比较”）。
3. 一个将在算法结束时释放所有已分配内存的算法。

开源

是的，ScopeAlloc/AutoFreeAlloc 是开源的，并且在通用公共许可证 (CPL) 下获得许可。您可以在 http://code.google.com/p/stdext/ 上找到更多信息。

以下是 ScopeAlloc/AutoFreeAlloc 源代码的快速链接：

• AutoFreeAlloc.h - class GCAllocT, AutoFreeAlloc
• ScopeAlloc.h - class BlockPool, ScopeAlloc
• SystemAlloc.h - class SystemAlloc

基于 GC 分配器的应用

GC 分配器有用吗？是的。C++ 开发人员的情况发生了变化！我们也可以像 Java 和 C# 一样从 GC 中获益！并且已经有一些应用程序基于它。以下是其中的一部分：

Word 文件编写器

我使用 GC 分配器编写了一个 Word 文件格式编写器。我感到兴奋的是，它是我见过的最快的 Word 文件编写器组件。

对此感兴趣？请参阅最快的 Word 文件编写器。

基于 GC 分配器的 Rope

Rope 是一种复杂的字符串实现，具有可扩展的性能。原始的 rope 实现出现在 SGI STL 中。我基于 GC 分配器重写了 rope 类。代码量大大减少，性能也得到了提升。

对此感兴趣？请参阅基于 GC 分配器的 Rope。

基于 GC 分配器的 STL 容器

不仅是 rope，几乎所有的 STL 容器都可以基于 GC 分配器，包括：

• Deque
• List, Slist
• Map, MultiMap
• Set, MultiSet
• HashMap, HashMultiMap
• HashSet, HashMultiSet

当使用 ScopeAlloc 时，STL 容器的性能有显著提升。这是我们的一项测试结果（单位：毫秒）：

有关比较的详细信息，请参阅“STL 集合上的分配器性能”。

请注意，我们不提供所有基于 GC 分配器的 STL 容器。线性数据结构的 STL 容器（例如 std::vector、std::basic_string/std::string 等）不需要 GC 分配器。

相关主题

• 分配器性能比较
• STL 集合上的分配器性能
• 基于 GC 分配器的 Rope
• 最快的 Word 文件编写器