C 语言中的 Arena 分配器

# C 语言中的 Arena 分配器 来源：https://eliasebner.com/blog/guides/arena-allocators-in-c/ --- 众所周知，C 是一门非常底层的语言。它允许你（甚至可以说强迫你）自己管理所使用的内存。这也是人们在日常编程中转向其他语言的原因之一（可能还有许多其他原因）。在这篇文章中，我将向你展示一种内存管理范式，它不仅性能极高，而且非常灵活。它能显著简化任务，并大幅降低内存泄漏的可能性。也许你已经了解过它，也许没有——无论如何，我说的就是 **arena 分配器**（竞技场分配器）。我会介绍它的实现，但在此之前，先简要介绍一下 arena 分配器的概念。 ## 什么是 Arena 分配器？ 人们通常管理内存的方式是：每次需要内存时，用 `malloc` 从堆中分配一小块恰好够用的内存。如果后来发现需要的内存比原计划更多，就使用 `realloc` 来扩大已分配内存的大小。用完内存后，调用 `free` 告诉操作系统这块内存不再需要，可以被其他任务使用。 这很好，但存在几个问题： **1.** 程序员必须记住在使用完内存后释放它。如果分配发生在循环中——比如在游戏里——这就尤其危险，因为操作系统会不断分配越来越多的内存，但这些内存永远不会被释放。内存作为一种资源并不是无限的。迟早，你的电脑会耗尽内存，程序会被操作系统终止（即崩溃）。 **2.** 分配和释放大量小块内存是*很慢*的。 **3.** 如果你有这样一个函数： ``` i32 *create_array(usize len) { i32 *elements = (i32 *)malloc(sizeof(int)); return elements; } ``` 现在告诉我：调用这个函数的程序员如何知道该函数执行了内存分配？在这种情况下，可以通过查看函数名并思考函数可能在做什么来推断出来，但这并不总是那么显而易见。记住，这很重要，因为程序员需要知道何时释放内存。程序员需要意识到释放内存是他的责任。 可能还有一些我没想到的其他问题，但这些是我能立刻想到的主要问题。 **解决方案。** *arena 分配器* 应运而生。大多数生命周期（即某块内存在被释放之前使用的时间长度）可以归入少数几类： 1. 内存在整个程序运行期间存活 2. 内存存活到某个任务完成（例如游戏中的一帧或处理一个 HTTP 请求） 3. 内存活于函数的作用域内 这通常已经是足够的分类了，但根据你如何定义分类，可能还会有更多。无论如何，我们可以一次性分配一大块内存，用来存放生命周期相似（即可以一起释放）的数据。这样我们就有了大量可供使用的内存。每次我们使用其中一部分内存时，就推进一个指针，记录已使用内存到哪里为止以及空闲内存从哪里开始。当你看到实现后，这会变得更加清楚。 当我们不再需要那一大块内存中的数据时，可以一次性全部释放（或者——如果想复用这块内存——将内存竞技场重新初始化到初始状态，从头开始重新分配）。这样省去了单独的内存分配（记住，那很慢），也让我们不必过多担心内存管理，因为我们只需要关注少数几块"大块"内存，而不是用于各个数组的小碎片。 ## 实现 ### 说明 在开始之前，每当我使用 C 语言时，我几乎总是会在代码顶部包含这个文件。它只是对一些内置类型进行 `typedef`，并包含一些常用的实用工具。我直接包含 `.c` 文件，因为我使用 unity build 来加快编译速度。如果你更喜欢这样做，也可以轻松地为它编写头文件。 ``` // types.c #ifndef TYPES_C #define TYPES_C #include <stdint.h> #include <stddef.h> typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef float f32; typedef double f64; typedef size_t usize; #define KiB(x) x * 1024 #define MiB(x) KiB(x) * 1024 #define GiB(x) MiB(x) * 1024 #define MIN(a, b) a < b ? a : b #define MAX(a, b) a > b ? a : b #endif // TYPES_C ``` ### `arena.c` 这是实际的 arena 实现。我们从 include guard 开始（同样，因为 unity build），然后包含我们将使用的几个 `libc` 头文件： ``` #ifndef ARENA_C #define ARENA_C #include "types.c" #include <stdlib.h> #include <string.h> #include <stdbool.h> // code goes here #endif // ARENA_C ``` 这是 arena 结构体的定义： ``` struct arena { void *data; usize size; usize used; }; ``` 它追踪已使用了多少内存。也可以通过使用一个指向未使用内存区域起始位置的指针来实现这一点。`size` 字段用于判断分配时是否溢出了 arena（如果你使用了太多内存，这很可能发生）。而 `data` 只是指向 arena 的起始位置。 到目前为止一切顺利，但现在我们需要一种方法来创建新的 arena。如下： ``` struct arena_create_out { struct arena arena; bool success; }; [[nodiscard]] struct arena_create_out arena_create(usize size) { struct arena_create_out out = {0}; out.arena.data = malloc(size); if (out.arena.data == NULL) return out; out.arena.size = size; out.arena.used = 0; out.success = true; return out; } ``` 在返回多个值时，我更倾向于返回结构体，而不是使用输出参数——我觉得输出参数令人困惑，而且在我看来这让 API 变得不直观。 然后我们需要一种方法在这个 arena 中分配一些内存。在此之前，先定义这个宏（我把它放在文件顶部，但在这里介绍，因为这才是它变得相关的时刻）： ``` #define ARENA_ALIGN 8 ``` 这将用于对齐数据。出于某种原因，我们的计算机在处理按 8 字节对齐的数据时效率高得多。这意味着每次新分配的起始位置必须是 8 字节的倍数。`malloc` 会帮我们处理这个问题，但由于我们不再使用 `malloc` 分配内存，而只是在一块已分配的内存中预留一些空间，我们必须自己对齐数据以获得更快的访问速度。 这是分配函数： ``` struct arena_alloc_out { void *ptr; bool success; }; [[nodiscard]] struct arena_alloc_out arena_alloc(struct arena *arena, usize size) { struct arena_alloc_out out = {0}; usize alignment = (ARENA_ALIGN - (arena->used % ARENA_ALIGN)) % ARENA_ALIGN; out.ptr = arena->data + arena->used + alignment; if (out.ptr + size > arena->data + arena->size) return out; arena->used += size + alignment; out.success = true; return out; } ``` 在这里，我们计算出需要在分配末尾添加多少"填充"（即 `alignment` 变量），以便下一次分配能够对齐到 8 字节。我在返回类型中使用包含 `success` 字段的模式，出错时直接提前返回（因为返回值使用 `= {0}` 初始化为全零，所以 `success` 会是 `false`）。如果你不喜欢这种方法，迁移 API 到不同的约定应该相当简单。 大部分工作已经完成了，我创建了一个简单的包装器来更改分配的大小。它只是在 arena 末尾用新大小分配一块内存，然后将数据复制过去。旧数据保持不动，因为它会在 arena 被释放时一起释放（记住，我们无法释放单个分配，要么释放整个 arena，要么什么都不释放）。你并不*真的*需要它，但我发现它让我的代码更整洁，所以这里是它： ``` struct arena_realloc_out { void *ptr; bool success; }; [[nodiscard]] struct arena_realloc_out arena_realloc(struct arena *arena, usize new_size, void *src, usize old_size) { struct arena_realloc_out out = {0}; struct arena_alloc_out alloc_out = arena_alloc(arena, new_size); if (!alloc_out.success) return out; out.ptr = memcpy(alloc_out.ptr, src, MIN(old_size, new_size)); out.success = true; return out; } ``` 如果新大小比原大小小，那么数据的末尾部分会被截断。另外，内部的 `realloc` 知道与每个指针关联的每个分配的大小，所以你不需要传递旧大小，只需传递新大小。而由于我们的 arena 实现没有以任何方式追踪分配的大小，我们必须单独将旧大小传递给函数。arena 的使用者需要知道每次分配的大小。这也可以实现，但我想保持简单。 接下来的两个函数是小包装器，它们只是为了方便而存在，但不是必需的： ``` void arena_clear(struct arena *arena) { arena->used = 0; } void arena_free(struct arena *arena) { free(arena->data); } ``` 这就是我的实现了。 ## 使用示例 我有一个为自己使用场景实现的简单字符串库。它有两个概念：字符串视图（string view）和拥有所有权的字符串（owned string）。 拥有所有权的字符串以 NUL 结尾，并且*拥有*其数据（即它需要被分配和释放）。这也意味着你可以直接修改拥有所有权的字符串。 字符串视图只是*查看*数据，所以你不能直接修改它，因为可能存在多个字符串视图查看同一块数据，修改它会导致其他字符串出现意外变化。另一方面，对于任何给定的数据区域，只应存在一个拥有所有权的字符串。 重要的是，我需要一种将字符串视图转换为拥有所有权的字符串的方法。为此，我们必须创建一个新的拥有所有权的字符串（这意味着为它分配内存），并将数据复制过去。同样，这是为了确保对这个拥有所有权的字符串的修改不会影响其他可能查看它的字符串视图。我们还在拥有所有权的字符串末尾添加一个 NUL 终止符（以使其与其他遗留的 C API 兼容）。为此，我们将一个 arena 分配器传递给函数，并在该 arena 上进行分配： ``` struct str_view { const u8 *data; usize len; }; struct str_owned { u8 *data; usize len; }; struct str_view_to_str_owned_out { struct str_owned str; bool success; }; [[nodiscard]] struct str_view_to_str_owned_out str_view_to_str_owned( struct arena *arena, struct str_view s ) { struct str_view_to_str_owned_out out = {0}; struct arena_alloc_out alloc_out = arena_alloc(arena, s.len + 1); if (!alloc_out.success) return out; out.str.data = alloc_out.ptr; memcpy(out.str.data, s.data, s.len); out.str.len = s.len; out.str.data[out.str.len] = 0; out.success = true; return out; } ``` 这做了两件事： 1. 调用者立即知道该函数会分配内存（因为它的第一个参数是 arena 指针） 2. 调用者可以决定在哪里（即以哪种生命周期）分配内存。 关于第 2 点，由于调用者通过传递相关的 arena 来决定内存的生命周期，他们不必担心直接释放内存——内存只需在生命周期结束、arena 被丢弃（或清除）时自动释放即可。这可以在程序结束时发生（在这种情况下释放内存是不必要的，因为操作系统会为我们处理），也可以在函数结束时发生，或者在他们确定不再需要内存的任何时候。 ## 结论 我最近开始将 arena 纳入我的编程习惯中，我必须说我已经非常满意了。我已经将我的字符串库迁移到使用 arena，我认为你也会从使用 arena 中获益良多。有时开发体验的提升比其他情况下更大，但我会说，作为一个程序员掌握这个工具绝对是净收益。 我并不声称自己是专家，这个实现只是我为个人使用而构建的。它可能不是完美的，但应该是一个不错的入门介绍，帮助你开始使用。 感谢阅读，希望你觉得这篇文章对你有帮助！一如既往，如有任何问题、反馈或见解，欢迎通过电子邮件联系我：[[email protected]](mailto:[email protected])