C Academy · 课时

简单的碰撞分配器

Q: 「简单的碰撞分配器」这节课中我会学到什么？

按线性方式分配内存。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

按线性方式分配内存。

简单的碰撞分配器 是 CoddyKit 上的免费 C Academy 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

bump 分配器的概念

bump（也称 arena）分配器是最简单的设计。您保留一个大缓冲区和一个偏移量。每次分配只需返回当前偏移位置，然后根据请求的大小将偏移量向前“推进”。

它没有每个内存块的元数据，也不需要搜索。分配本质上只是一次指针加法，因此速度极快。

静态后备缓冲区

为了构建一个自包含的示例，我们使用静态数组为分配器提供内存，而不是使用 OS 堆。它无需 sbrk 或 mmap，可以在任何地方编译和运行。

这个数组为我们提供了一个固定的字节池，可以从中切分内存。

#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

核心 bump 函数

分配时会检查是否还剩足够空间，记录起始位置，推进偏移量，然后返回起始指针。如果请求会超出内存池范围，则返回 NULL。

溢出检查是 bump 分配器提供的唯一安全保障。

void *bump_alloc(size_t size) {
    if (offset + size > POOL_SIZE)
        return NULL;            /* out of pool */
    void *p = &pool[offset];
    offset += size;
    return p;
}

完整可运行的 bump 分配器

下面是一个完整程序。它从内存池中分配两个整数和一个短字符串，并将它们输出，以证明分配器可以正常工作。

请注意，与真正的 malloc 相比，它所需的代码少得多。

#include <stdio.h>
#include <stddef.h>
#include <string.h>

#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

void *bump_alloc(size_t size) {
    if (offset + size > POOL_SIZE) return NULL;
    void *p = &pool[offset];
    offset += size;
    return p;
}

int main(void) {
    int *a = bump_alloc(sizeof(int));
    int *b = bump_alloc(sizeof(int));
    char *s = bump_alloc(6);
    *a = 10; *b = 32;
    strcpy(s, "hi");
    printf("%d %d %s\n", *a, *b, s);
    printf("used = %zu\n", offset);
    return 0;
}

无法单独释放

问题在于：bump 分配器无法释放单个分配结果。由于没有元数据，它不知道某个内存块在哪里结束、下一个内存块在哪里开始，因此无法重复利用。

您只能通过将偏移量重新设置为零，一次性重置整个 arena。

void bump_reset(void) {
    offset = 0;   /* frees everything at once */
}

为什么重置很有用

这种全有或全无的模型非常适合分阶段工作：在一次请求或一帧期间分配许多对象，阶段结束时再重置 arena。

游戏引擎和编译器大量使用 arena，因为重置的复杂度为 O(1)，并且不需要跟踪成千上万个单独的释放操作。

/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
    void *tmp = bump_alloc(128);
    /* ... use tmp this frame ... */
    bump_reset();   /* reclaim instantly */
}

跟踪剩余空间

了解还剩多少空间会很有用。这就是内存池大小减去当前偏移量。

调用方可以利用这个值，在请求更多空间之前决定是刷新还是扩容。

size_t bump_remaining(void) {
    return POOL_SIZE - offset;
}

一个可运行的重置演示

该程序填充内存池的一部分，打印使用情况，执行重置，并显示偏移量回到零，从而说明这部分空间可以重新使用。

#include <stdio.h>
#include <stddef.h>

#define POOL_SIZE 256
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

void *bump_alloc(size_t s){ if(offset+s>POOL_SIZE) return NULL; void *p=&pool[offset]; offset+=s; return p; }
void bump_reset(void){ offset = 0; }

int main(void) {
    bump_alloc(100);
    printf("after alloc: used=%zu\n", offset);
    bump_reset();
    printf("after reset: used=%zu\n", offset);
    return 0;
}

微调分配器中的对齐

逐字节进行原始微调可能会返回未对齐的指针。为确保安全，应在返回指针之前，将偏移量向上取整到对齐边界。

稍后我们会详细讲解相关数学原理，但对微调分配器来说，对齐尤其重要，因为否则不会有填充空间。

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);   /* a must be power of 2 */
}

一个对齐的微调分配器

将各个部分组合起来后，我们会在每次分配之前对齐偏移量。这样可以保证返回的每个指针都适用于任何常见类型。

代价是填充字节会造成少量内部碎片。

#define ALIGN 16
void *bump_aligned(size_t size) {
    offset = align_up(offset, ALIGN);
    if (offset + size > POOL_SIZE) return NULL;
    void *p = &pool[offset];
    offset += size;
    return p;
}

优势与局限

微调分配器速度极快，而且非常简单，每个对象没有任何额外开销。当对象具有相同的生命周期时，它们非常理想。

它的弱点是无法进行细粒度释放。当生命周期不同时，您需要使用下一课介绍的空闲链表设计。

快速检查

思考微调分配器如何回收内存。

回顾

微调分配器通过在缓冲区中推进一个偏移量来分配内存，使分配的成本低到类似于执行一次指针加法。

它以速度和简洁性为代价，放弃了逐个释放，只能通过完整重置来回收内存。请对齐偏移量，以确保返回的指针对所有类型都有效。

常见问题解答

「简单的碰撞分配器」课时是免费的吗？

是的 — 「简单的碰撞分配器」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「简单的碰撞分配器」这节课中我会学到什么？

按线性方式分配内存。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「简单的碰撞分配器」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy