设计/图形架构高级中级 Visual Studio C++

Arena 分配器、析构函数注册和嵌入式预分配缓冲区

Mamasha Knows

5.00/5 (13投票s)

2009年11月25日

CPOL

8分钟阅读

39843

380

Arena 式内存管理、在 Arena 中嵌入分配、析构函数注册、上下文思考

下载源代码 - 6.87 KB

引言

内存分配方案是开发高效基础设施时一个非常重要的问题。通常，我们从堆或栈中消耗内存。堆灵活但速度慢，栈速度快但有限，例如数组大小必须在编译时确定。目标是结合堆的灵活性和栈的速度。

Arena 分配器是一种广为人知的技术。在执行的某个点预分配一个任意大小的内存块。一个指针被用来跟踪块内的下一个分配位置。后续的分配只需将该指针移动到下一个分配位置。整个块一次性释放，无需单独释放。

动机

考虑以下用例：您有一个复杂的数据结构，只需要构建一次，并且之后不会修改，除了删除它。
鉴于此用例，所需的 Arena 功能是：

一个 Arena 可以服务于整个数据结构中的所有对象。这提供了高局部性并且没有管理开销。
对象不持有分配器（Arena 的引用）。它们只需要构建一次。
Arena 不会位于全局/静态存储中。
对象仍将调用它们的析构函数。

……正如在 Boost 邮件列表中讨论的。

（我无意编写符合 Boost 标准的代码。我只是喜欢这里的动机表达方式。）

为什么又一个分配器

C++ 区域的内存分配方面有许多出色的贡献。

我对 C++ operator new 的咆哮 by David Mazie`res
- 对相关 C++ 问题的深入技术讲解
- 全局 new 和 delete 操作符的重载以及为什么危险
C++ 内存管理创新：GC 分配器
- 作用域和 Arena 分配方案的概念
- 令人印象深刻的基准测试表明，当效率至关重要时，new/delete 并不那么好
陷阱 #62：替换全局 new 和 delete

我花了一段时间才最终决定发布这篇文章。很明显，我的方法只是对上述文章中找到的思想和概念的不同实现。但它仍然有三个值得注意的设计决策：

在 Arena 中嵌入预分配缓冲区
放弃析构函数自动调用
任何大小分配的相同接口（无限分配空间）

平台和可移植性

我的 Arena 分配器是在 VS2008 下开发和测试的。我不期望在其他 VS 编译器下有任何意外。然而，正如 David Mazie`res 在他的文章中解释的那样，这里提出的方法存在可移植性问题。据我理解，主要问题在于特定编译器如何实现 operator new[]。

让我们看看 Visual Studio 的文档

似乎在 Visual Studio 中，operator new 和 operator new[] 是相同的。如果只重载了 operator new，它将被用于两种类型的分配。

Thing* thing  = new (arena) Thing;
Thing* things = new (arena) Thing [10];

所以，我的实现只是默默地忽略了 operator new[] 的存在。

测试和可靠性

虽然我的 Arena 实现已经通过了各种单元测试，但代码仍然很新，未经实战检验。因此，请将源代码视为 Arena 分配器概念的演示。

设计细节

嵌入对象

显然，Arena 用于快速的小型分配。如果第一次分配不需要任何堆操作，那将是一个非常强大的特性。

Arena 应该有一个分配缓冲区作为其成员。

MyArena<256> arena;

这行代码的意思是 MyArena 内部缓冲区为 256 字节。

sizeof(MyArena<256>) == sizeof(Arena) + 256

template<int INIT_CAPACITY>
class MyArena : public Arena
{
    char	storage_[INIT_CAPACITY];
};

在“Arena 已消失”时刻调用析构函数

析构函数调用的自动化带来了实现的复杂性。更糟的是，operator new 的语法迫使实现者引入像 NEW 和 NEW_ARRAY 这样的宏，如这里所述。

这种自动化对专业程序员有帮助吗？我相信，如果一个人意识到了不同分配方案的需要，他就不再是初学者了。他肯定可以自己决定是否需要调用析构函数。他无法做到的是同步析构函数调用与“Arena 已消失”时刻。

Arena 应该提供一个“析构函数注册”机制，而不是自动调用析构函数。

Thing* things = new (arena) Thing [3];      // allocate array of things
arena.DTOR(things, 3);                      // call DTORs when arena-is-gone

无限分配空间

确实，Arena 针对小内存分配进行了优化。但是，有时您就是不知道预分配缓冲区的确切大小。此外，在极少数情况下，您可能故意需要一个大的分配。而且，Arena 是一个基础设施类，我们永远不知道确切的使用曲线。

当预分配缓冲区空间不足时，Arena 应该增长。

double* arr = new (arena) double [10000];    // allocation is propagated to default new

按用例划分的接口

构造 Arena

// create arena with internal buffer of 256 bytes
MyArena<256> arena;

// create arena with preallocated buffer of 256 bytes
char* buf = new char[256];
Arena arena(buf, sizeof(buf));      // arena will not free the buffer

// create arena with preallocated heap buffer of 256 bytes
Arena arena(256);

// create arena with no preallocated buffer
Arena arena;

分配对象

// allocate and construct a Thing
MyArena<256> arena;
Thing* thing = new (arena) Thing;

// allocate dynamic array of integers
MyArena<256> arena;
int* arr = new (arena) int [n];

// allocate big dynamic array
MyArena<256> arena;
double* arr = new (arena) double [1024*1024]; // Arena propagates this allocation to heap

销毁对象

// register Thing's DTOR
MyArena<256> arena;
Thing* thing = new (arena) Thing;
arena.DTOR(thing);          // DTOR will be called when arena goes out of scope

// register array of DTORs
MyArena<256> arena;
Thing* imgs = new (arena) Thing [n];
arena.DTOR(imgs, n);        // DTORs will be called when arena goes out of scope

实现细节

重载 operator new

是的，我们必须重载它……

快速回顾一下 operator new 重载语法

Thing* thing = new Thing;

在这行代码中，实际上发生了两件事。分配了一个类 Thing 的内存，然后调用了 Thing 的构造函数。通过重载 operator new，我们可以显式控制第一步——内存分配。

我们定义了两个 operator new 的重载。

void* operator new (size_t size, Arena& arena);
void* operator new (size_t size, Arena* arena);

因此，以下示例将按预期工作：

Arena arena;                        // arena is object
Thing* thing = new (arena) Thing;   // allocate Thing using arena

Arena* arena = new Arena;           // arena is pointer
Thing* thing = new (arena) Thing;   // allocate Thing using arena

本文的主题是 Arena 分配器而不是 operator new 重载。因此，我将不再深入研究语法。您可以随时在文档或这里刷新详细信息。

类层次结构

Arena 类实现了所有功能。MyArena<N> 只是“预分配”缓冲区的容器。
Arena 从 cur_ 内存块分配内存。当 cur_ 块已满时，它被压入已满内存块列表的前面。
Arena 将“预分配”缓冲区存储在 init_ 成员中。该块永远不会被 Arena 释放，因为它是在 Arena 之外创建的。
当注册析构函数时，会实例化一个模板化的析构函数回调。一个新的 DtorRec 被压入析构函数记录列表的前面。

已分配内存的布局

MyArena<256> arena;
int* iarr    = new (arena) int  [10];
char* msg    = new (arena) char [32];
Thing* thing = new (arena) Thing;
arena.DTOR(thing);

这些代码行导致内存布局如下：

更复杂的分配场景可能导致以下内存布局：

内存分配的消息序列图

注意，有一个 MAX_SMALL_ALLOC 常量。如果内存分配请求超过此限制，分配将传播到默认的 operator new——堆。一个块头被放在已分配内存的前面，以维护已分配块的链表。

Boost 用法

使用了两个 Boost 库：

内置单向链表
Boost 断言

使用 arena_allocator.h

Arena 完全实现在“arena_allocator.h”中。一组用例实现在“arena_allocator.cpp”中。您无需链接它即可使用 Arena 分配器。

分享的思考

我花了几年时间才得出这里呈现的 Arena 实现。我编写了 STL 分配器、对象池、对象池的池等。我所做的每个实现都让我感觉好像总是遗漏了什么。然后我意识到一个简单的事情：内存分配和对象生命周期是两个正交的问题。是的，这很明显，而且在所有关于内存分配技术的书中都有记载。尽管如此，遗憾的是，这种知识很长一段时间以来都是形式化的，与我真实的编程无关。

生命周期管理和内存上下文

Thing* thing = new Thing;   // allocate memory and construct Thing
...                         // do some work
delete thing;               // destroy Thing and free memory

再次强调，上面的代码处理两个正交的问题：管理 Thing 的内存和管理 Thing 的生命周期。典型的设计试图分离这些问题：内存管理交给各种分配器，而生命周期管理交给各种智能指针。

就个人而言，我从未使用过 auto_ptr 或任何其他智能指针。 IMHO，大量使用 auto_ptr 意味着该程序存在糟糕的内存管理设计，或者 C++ 不适合该特定程序。

在基础设施方面工作时，我总是处理相同的内存使用模式：对象“生活”在批次中。在一个批次中，对象一个接一个地创建。之后，整个批次被一次性删除。在大多数情况下，这种批次的生命周期由某个“上层”类表示。我的观点是：该类应该有一个 Arena 分配器作为其成员。

因此，程序中所有对象的生命周期构成了一组“上下文”。每个“上下文”都应该有自己的内存分配器——Arena。

作用域分配

作用域只是我上面谈到的上下文的一个特例。它是一个相当简单的上下文，由两个花括号 {} 形成。

void foo()
{
    MyArena<256> arena;
    int* arr = new (arena) int [10];    // allocate array of integers
    Thing* thing = new (arena) Thing;   // allocate some object
}                                       // destroy arena and its memory

TLS 和 Arena 分配器

许多实现者将一个优化的内存分配器作为 TLS（线程本地存储）变量。我也曾经这样做过。然而，为了上下文思考，我意识到，实际应该成为 TLS 值的是一个特定的上下文，而不是分配器本身。如果这样的上下文有自己的分配器，我们就得到了一个隐式的基于 TLS 的分配器。

结论

这里呈现的 Arena 分配器对我来说是一种“赋能技术”类。它既作为内存分配器，又作为生命周期管理器。它有助于区分“协作上下文”——一组相关的对象。最后，Arena 为整个程序提供了统一的内存管理接口。

Arena 让我的编程更容易。我喜欢这样。

历史

2009 年 11 月 25 日：初始发布

Arena 分配器、析构函数注册和嵌入式预分配缓冲区

目录

动机

历史