高效的C++固定块内存分配器

• 下载 Allocator.zip - 5.5 KB

引言

自定义的定长块内存分配器用于解决至少两种与内存相关的问题。首先，全局堆的分配/释放可能速度较慢且不可预测。你永远不知道内存管理器需要多长时间。其次，消除因堆碎片化引起的内存分配失败的可能性——这是一个合理的担忧，尤其是在任务关键型系统上。

即使系统不被认为是任务关键型的，一些嵌入式系统也被设计成可以运行数周甚至数年而无需重启。根据分配模式和堆的实现，长期使用堆可能导致堆故障。

典型的解决方案是预先静态声明所有对象，完全放弃动态分配。然而，静态分配可能会浪费存储空间，因为即使对象未被积极使用，它们也存在并占用空间。此外，实现一个围绕动态分配的系统可以提供更自然的设计架构，而不是静态声明所有对象。

定长块内存分配器并非新概念。人们长期以来一直在设计各种自定义内存分配器。我在这里介绍的是一个我已成功用于多个项目的简单 C++ 分配器实现。

这里提出的解决方案将：

• 比全局堆更快
• 消除堆碎片化内存故障
• 除了几个字节的静态内存外，无需额外的存储开销
• 易于使用
• 使用最少的代码空间

一个简单的类，可以分配和回收内存，将提供上述所有好处，我将展示这一点。

阅读完本文后，请务必阅读后续文章“使用快速定长块内存分配器替换 malloc/free”，了解 Allocator 如何用于创建非常快速的 malloc() 和 free() CRT 替换。

使用 CMake 创建构建文件。CMake 是免费开源软件。支持 Windows、Linux 和其他工具链。有关更多信息，请参阅 **CMakeLists.txt** 文件。

查看 GitHub 以获取最新源代码

• 高效 C++ 定长块内存分配器 - 作者：David Lafreniere

存储回收

内存管理方案的基本理念是回收在对象分配期间获得的内存。一旦为对象创建了存储，它就永远不会返回给堆。相反，内存被回收，允许相同类型的另一个对象重用该空间。我实现了一个名为 Allocator 的类来表达这种技术。

当应用程序使用 Allocator 删除时，单个对象的内存块将被释放以供再次使用，但实际上不会释放回内存管理器。已释放的块保留在一个称为空闲列表的链表中，以便为相同类型的另一个对象再次分配。每次分配请求时，Allocator 首先检查空闲列表是否有现有的内存块。只有在没有可用时，才会创建一个新的。根据 Allocator 的期望行为，存储来自全局堆或具有三种操作模式之一的 static 内存池：

1. 堆块
2. 堆池
3. 静态池

堆与池

当空闲列表无法提供现有内存块时，Allocator 类能够从堆或内存池创建新的块。如果使用池，则必须预先指定对象的数量。使用总对象数，将创建一个足够大的池来处理最大实例数。另一方面，从堆获取块内存没有这样的数量限制——构造任意数量的新对象，只要存储允许。

堆块模式在需要时从全局堆分配一个用于单个对象的新内存块来满足内存请求。释放操作会将该块放入空闲列表以供以后重用。在空闲列表为空时从堆创建新的块，使您不必设置对象限制。这种方法提供了类似动态分配的操作，因为块的数量可以在运行时扩展。缺点是在块创建期间执行会失去确定性。

堆池模式从全局堆创建一个单独的池来保存所有块。在构造 Allocator 对象时，使用 operator new 创建池。然后，Allocator 在分配期间从池中提供内存块。

静态池模式使用一个内存池，通常位于静态内存中，来保存所有块。静态内存池不是由 Allocator 创建的，而是由类的用户提供的。

堆池和静态池模式提供了持续的分配执行时间，因为内存管理器从未参与获取单个块。这使得新的操作非常快速和确定。

类设计

类的接口非常直接。Allocate() 返回指向内存块的指针，Deallocate() 释放内存块以供再次使用。构造函数负责设置对象大小，并在必要时分配内存池。

传递给类构造函数的参数决定了新块的来源。size 参数控制固定内存块的大小。objects 参数设置允许的块数。0 表示按需从堆中获取新块，而任何其他非零值表示使用池（堆或静态）来处理指定数量的实例。memory 参数是指向可选 static 内存的指针。如果 memory 为 0 且 objects 不为 0，Allocator 将从堆中创建池。静态内存池的大小必须为 size x objects 字节。name 参数可选地为分配器命名，这对于收集分配器使用情况指标很有用。

class Allocator
{
public:
    Allocator(size_t size, UINT objects=0, CHAR* memory=NULL, const CHAR* name=NULL);
...

下面的示例展示了如何通过构造函数参数控制三种操作模式中的每一种。

// Heap blocks mode with unlimited 100 byte blocks
Allocator allocatorHeapBlocks(100);

// Heap pool mode with 20, 100 byte blocks
Allocator allocatorHeapPool(100, 20);

// Static pool mode with 20, 100 byte blocks
char staticMemoryPool[100 * 20];
Allocator allocatorStaticPool(100, 20, staticMemoryPool);

为了在一定程度上简化 static 池方法，使用了简单的 AllocatorPool<> 模板类。第一个模板参数是块类型，第二个参数是块数量。

// Static pool mode with 20 MyClass sized blocks 
AllocatorPool<MyClass, 20> allocatorStaticPool2;

通过调用 Allocate()，将返回一个指向一块大小为一个实例的内存的指针。获取块时，会检查空闲列表以确定是否存在空闲块。如果存在，则只需从空闲列表中解除链接现有块并返回其指针；否则，从池/堆创建一个新的。

void* memory1 = allocatorHeapBlocks.Allocate(100);

Deallocate() 只是将块地址推送到栈上。栈实际上实现为一个单向链表（空闲列表），但类只从头部添加/移除，因此行为与栈相同。使用栈使分配/释放非常快速。无需遍历列表——只需推送或弹出块即可。

allocatorHeapBlocks.Deallocate(memory1);

现在 comes 一个方便的方法，可以在不消耗额外存储空间的情况下将块链接在空闲列表中，无需额外的指针存储。例如，如果我们使用全局 operator new，首先分配存储，然后调用构造函数。销毁过程正好相反；调用析构函数，然后释放内存。在析构函数执行完毕后，在存储被释放回堆之前，内存已不再被对象使用，可以用于其他事物，例如下一个指针。由于 Allocator 类需要保留已删除的块，因此在 operator delete 中，我们将列表的下一个指针放在当前未使用的对象空间中。当块被应用程序重用时，就不再需要该指针，它将被新创建的对象覆盖。这样，就不会产生每个实例的存储开销。

使用已释放的对象空间作为链接块的内存意味着对象必须足够大以容纳指针。构造函数初始化列表中代码确保最小块大小绝不会低于指针大小。

类析构函数通过删除内存池或（如果块是从堆中获取的）通过遍历空闲列表并删除每个块来释放执行期间分配的存储。由于 Allocator 类通常用作类作用域的 static，因此它仅在程序终止时被调用。对于大多数嵌入式设备，当有人拔掉系统电源时，应用程序就会终止。显然，在这种情况下，不需要析构函数。

如果您使用的是堆块方法，则在应用程序终止时无法释放分配的块，除非所有实例都已放入空闲列表中。因此，所有未使用的对象都必须在程序结束前“删除”。否则，您将面临内存泄漏。这引出了一个有趣的问题。Allocator 是否需要跟踪已分配和正在使用的块？简短的回答是否。长答案是，一旦一个块通过指针交给应用程序，那么应用程序就有责任通过调用 Deallocate() 将该指针返回给 Allocator，然后程序才能结束。这样，我们只需要跟踪已释放的块。

Using the Code

我希望 Allocator 极其易于使用，因此我创建了宏来自动化客户端类内的接口。这些宏提供了一个 static Allocator 实例和两个成员函数：operator new 和 operator delete。通过重载 new 和 delete 运算符，Allocator 拦截并处理客户端的所有内存分配任务。

DECLARE_ALLOCATOR 宏提供了头文件接口，应像这样包含在类声明中：

#include "Allocator.h"
class MyClass
{
    DECLARE_ALLOCATOR
    // remaining class definition
};

operator new 函数调用 Allocator 来创建类单个实例的内存。内存分配完成后，根据定义，operator new 会调用类适当的构造函数。重载 new 时只能接管内存分配任务。构造函数调用由语言保证。同样，删除对象时，系统会先为我们调用析构函数，然后执行 operator delete。operator delete 使用 Deallocate() 函数将内存块存储在空闲列表中。

在 C++ 程序员中，当使用基类指针删除类时，析构函数应声明为虚函数，这是相对普遍的知识。这确保了在删除类时，会调用正确的派生类析构函数。然而，不太明显的是，虚析构函数如何改变调用哪个类的重载 operator delete。

尽管未显式声明，operator delete 是一个 static 函数。因此，不能将其声明为虚函数。所以乍一看，人们会认为使用基类指针删除对象无法路由到正确的类。毕竟，使用基类指针调用普通 static 函数会调用基类的版本。然而，如我们所知，调用 operator delete 首先会调用析构函数。对于虚析构函数，调用会被路由到派生类。在类的析构函数执行完毕后，将调用该派生类的 operator delete。所以本质上，通过虚析构函数，重载的 operator delete 被路由到了派生类。因此，如果使用基类指针执行删除操作，则基类析构函数必须声明为虚函数。否则，将调用错误的析构函数和重载的 operator delete。

IMPLEMENT_ALLOCATOR 宏是接口的源文件部分，应放在文件范围内。

IMPLEMENT_ALLOCATOR(MyClass, 0, 0)

宏到位后，调用者可以创建和销毁该类的实例，已删除的对象将被回收。

MyClass* myClass = new MyClass();
delete myClass;

单继承和多继承情况都适用于 Allocator 类。例如，假设类 Derived 继承自类 Base，则以下代码片段是合法的。

Base* base = new Derived;
delete base;

运行时

运行时，Allocator 最初在空闲列表中没有块，因此对 Allocate() 的首次调用将从池或堆中获取一个块。随着执行的进行，任何给定分配器实例的对象需求将波动，并且只有在空闲列表无法提供现有块时才会分配新的存储。最终，系统将稳定在某个峰值实例数，使得每次分配都从现有块而不是池/堆中获取。

与使用内存管理器获取所有块相比，该类节省了大量处理能力。在分配期间，只需从空闲列表中弹出一个指针，这使其非常快速。释放操作只需将块指针推回列表，同样快速。

基准测试

在 Windows PC 上对 Allocator 的性能与全局堆进行基准测试，可以说明该类的速度有多快。通过分配和释放 20000 个 4096 和 2048 字节大小的块，并以某种交错的方式进行基本测试，可以测试速度的提高。有关确切算法，请参阅随附的源代码。

Windows 分配时间（毫秒）

分配器	模式	Run	基准测试时间（毫秒）
全局堆	调试堆	1	1640
全局堆	调试堆	2	1864
全局堆	调试堆	3	1855
全局堆	发布堆	1	55
全局堆	发布堆	2	47
全局堆	发布堆	3	47
分配器	静态池	1	19
分配器	静态池	2	7
分配器	静态池	3	7
分配器	堆块	1	30
分配器	堆块	2	7
分配器	堆块	3	7

Windows 在调试器执行期间使用调试堆。调试堆增加了额外的安全检查，从而降低了性能。发布堆要快得多，因为禁用了检查。可以通过在 **调试 > 环境** 项目选项中设置 **_NO_DEBUG_HEAP=1** 来在 Visual Studio 中禁用调试堆。

调试全局堆的速度最慢，约为 1.8 秒。发布堆要快得多，约 50 毫秒。此基准测试非常简单，更真实的情况（具有变化的块大小和随机的新/删除间隔）可能会产生不同的结果。但是，基本观点得到了很好的说明；内存管理器比分配器慢，并且高度依赖于平台的实现。

以静态池模式运行的 Allocator 不依赖于堆。一旦空闲列表被块填充，其执行时间就非常快，约为 7 毫秒。第一次运行时的 19 毫秒是由于第一次运行时将固定内存池分割成单独的块。

以堆块模式运行的 Allocator 一旦空闲列表被从堆中获取的块填充，速度就一样快。请记住，堆块模式依赖于全局堆来获取新块，然后将它们回收回空闲列表以供以后使用。运行 1 显示了创建内存块的分配命中，耗时 30 毫秒。随后的基准测试显示非常快的 7 毫秒，因为空闲列表已完全填充。

如基准测试所示，Allocator 非常高效，比 Windows 全局发布堆快约七倍。

为了进行比较，我在 ARM STM32F4 CPU 上以 168MHz 运行的 Keil 上运行了相同的测试。由于资源受限，我不得不将最大块数降低到 500，并将块大小降低到 32 和 16 字节。以下是结果。

ARM STM32F4 分配时间（毫秒）

分配器	模式	Run	基准测试时间（毫秒）
全局堆	Release	1	11.6
全局堆	发布	2	11.6
全局堆	发布	3	11.6
分配器	静态池	1	0.85
分配器	静态池	2	0.79
分配器	静态池	3	0.79
分配器	堆块	1	1.19
分配器	堆块	2	0.79
分配器	堆块	3	0.79

ARM 基准测试结果表明，Allocator 类快了约 15 倍，这相当显著。应注意的是，基准测试会加剧 Keil 堆的压力。在该 ARM 的情况下，基准测试分配 500 个 16 字节的块。然后每隔一个 16 字节的块被删除，接着分配 500 个 32 字节的块。最后一组 500 次分配为总计 11.6 毫秒的时间增加了 9.2 毫秒。这意味着当堆变得碎片化时，内存管理器花费的时间可能会更长，时间也不确定。

分配器决策

首先要做的决定是您是否需要分配器。如果您的项目没有执行速度或容错要求，您可能不需要自定义分配器，全局堆就足够了。

另一方面，如果您确实需要速度和/或容错，分配器可以提供帮助，而其操作模式取决于您的项目需求。任务关键型设计的架构师可能禁止所有全局堆的使用。然而，动态分配可能导致更有效或更优雅的设计。在这种情况下，您可以在调试开发期间使用堆块模式来获取内存使用情况指标，然后在发布时切换到 static 池方法来创建静态分配的池，从而消除所有全局堆访问。一些编译时宏可以在模式之间切换。

或者，堆块模式可能适用于该应用程序。它确实利用堆来获取新块，但可以防止堆碎片化故障，并且一旦空闲列表中有足够的块，就可以加快分配速度。

虽然由于本文范围之外的多线程问题未在源代码中实现，但让 Allocator 构造函数维护一个已构造实例的 static 列表很容易。运行系统一段时间，然后在某个点迭代所有分配器，并通过 GetBlockCount() 和 GetName() 函数输出指标（如块计数和名称）。使用情况指标提供了关于为每个分配器调整固定内存池大小的信息，以便在切换到内存池时使用。始终添加比最大测量块数多几个块，以使系统在池用完内存时具有一定的弹性。

调试内存泄漏

调试内存泄漏可能非常困难，主要是因为堆是一个黑盒子，无法了解已分配对象的类型和大小。使用 Allocator，内存泄漏稍微容易找到，因为 Allocator 跟踪总块计数。重复输出（例如到控制台）每个分配器实例的 GetBlockCount() 和 GetName() 并比较差异应该会暴露块计数不断增加的分配器。

错误处理

C++ 中的分配错误通常使用 new-handler 函数来捕获。如果内存管理器在尝试从堆中分配内存时出错，则通过 new-handler 函数指针调用用户的错误处理函数。通过将用户函数的地址分配给 new-handler，内存管理器可以调用自定义错误处理例程。为了使 Allocator 类的错误处理一致，超出池存储容量的分配也会调用 new-handler 指向的函数，从而将所有内存分配错误集中在一个地方。

static void out_of_memory()
{
    // new-handler function called by Allocator when pool is out of memory
    assert(0);
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::set_new_handler(out_of_memory);
...

限制

该类不支持对象数组。重载的 operator new[] 给对象回收方法带来了问题。当调用此函数时，size_t 参数包含所有数组元素所需的总内存。为每个元素创建单独的存储不是一个选项，因为多次调用 new 不能保证块在连续空间中，而数组需要连续空间。由于 Allocator 只处理相同大小的块，因此不允许使用数组。

移植问题

当 static 池存储空间不足时，Allocator 直接调用 new_handler()，这对于某些系统可能不合适。此实现假设 new-handler 函数不会返回（例如，无限循环陷阱或断言），因此如果函数通过压缩堆来解决分配失败，则调用处理程序没有意义。正在使用固定池，任何压缩都无法解决。

参考文章

使用快速定长块内存分配器替换 malloc/free，了解 Allocator 如何用于创建非常快速的 malloc() 和 free() CRT 替换。

历史

• 2016 年 3 月 9 日
  • 首次发布
• 2016 年 3 月 11 日
  •  添加了对“使用快速定长块内存分配器替换 malloc/free”文章的引用
• 2016 年 3 月 13 日
  •  更新了基准测试部分，包括 Windows 调试堆、非调试堆和 Keil ARM STM32F4 时间。
  • 新的源代码 zip 文件。
• 2016 年 3 月 28 日
  • 更新了附件源代码以帮助移植。