Hotdry.
归档
systems

C 堆管理：自定义 Arena、Buddy 和 Slab 分配器平衡碎片、吞吐与延迟

C 语言堆内存优化：arena、buddy 系统和 slab 分配器的工程参数、权衡与组合策略，实现碎片最小化、高吞吐和低延迟。

在 C 语言的高性能系统中，默认的 malloc/free 往往因元数据开销、锁竞争和碎片化而成为瓶颈。自定义 arena、buddy 和 slab 分配器通过针对性设计，能有效平衡外部 / 内部碎片、分配吞吐量和延迟。本文聚焦单一技术点：如何在 C 中实现这些分配器，并给出可落地参数与清单，帮助游戏服务器、编译器或嵌入式系统优化堆管理。

Arena 分配器：极致吞吐与相依生命周期

Arena（也称 bump 分配器）预分配大块连续内存，使用 “bump pointer” 向前推进分配位置，无需逐对象释放，仅在生命周期结束时重置整个 arena。这种设计在 per-request 或 per-frame 场景中表现出色。

核心原理与证据：分配仅需对齐计算并更新 offset，常数时间 O (1)，缓存友好，避免了链表遍历或分裂开销。如 Bytes Beneath 所述，“arena 的分配速度几乎是最快的，指针 bump 操作极简”。碎片方面，arena 内外部碎片近零，仅有对齐引起的内部浪费（通常 <10%）。

优劣平衡：

  • 吞吐 / 延迟：最高，单线程下分配延迟 <10ns；多线程用 per-thread arena 避锁。
  • 碎片：生命周期对齐时完美；错位则产生 “洞穴” 浪费。
  • 适用：HTTP 请求解析、游戏帧数据、AST 构建。

可落地 C 实现与参数：

typedef struct Arena {
    unsigned char *base;
    size_t size;
    size_t offset;
} Arena;

void *arena_alloc(Arena *a, size_t n, size_t align) {
    size_t p = (size_t)a->base + a->offset;
    size_t aligned = (p + (align - 1)) & ~(align - 1);
    size_t new_off = aligned - (size_t)a->base + n;
    if (new_off > a->size) return NULL;
    a->offset = new_off;
    return (void *)aligned;
}
void arena_reset(Arena *a) { a->offset = 0; }
  • 参数清单：
    参数 推荐值 说明
    size 1-64 MB per-thread，视负载；过大会 OOM
    align 16 或 32 字节 缓存线对齐，max (alignof (void*), SSE)
    增长策略 链表多 arena 初始失败时 mmap 新块，链表管理
    监控阈值 offset > 90% size 预告警，扩容或回滚 reset

回滚策略：若 OOM，fallback 到系统 malloc；调试时加 canary 检查越界。

Buddy 系统：通用块分配与有界碎片

Buddy 分配器管理 2^k 大小的块，分配时分裂大块为 “伙伴”，释放时合并空闲伙伴。常作底层 page allocator，为 slab/arena 供块。

核心原理与证据：操作 O (log N)，外部碎片有界（伙伴合并确保可重组），内部碎片限于下个 2^k（最坏 <100%）。GeeksforGeeks 指出，“buddy 适合内核内存，提供快速合并与低外部 frag”。

优劣平衡：

  • 吞吐 / 延迟：中等，log16~4 步；并发需锁或 per-CPU。
  • 碎片：外部低，内部高（e.g., 36KB 需 64KB）。
  • 适用：大块 / 页面分配，fallback 通用。

可落地参数：

  • min_order: 4 (16B)，max_order: 20 (1MB)。
  • 总大小：power-of-2，64-512 MB。
  • 清单：free_lists [32] 数组；分裂前查空闲列表；合并用 XOR offset 找伙伴。

Slab 分配器：固定大小 O (1) 低延迟

Slab 为固定对象大小维护 slab 页（e.g., 4KB 分 N 对象），用 freelist/bitset 追踪空闲。分配 pop 对象，释放 push 回。

核心原理与证据：O (1) 常数时间，per-size 专用 slab 零外部 frag，热对象复用减初始化。Linux kernel slab 证明其在高 churn（如 inode）下的低延迟。

优劣平衡：

  • 吞吐 / 延迟：极高，<5ns；per-CPU slab 避锁。
  • 碎片：最低，对象紧凑；部分满 slab 微废。
  • 适用：热对象如 conn struct、particle。

可落地参数：

typedef struct Slab {
    Slab *next;
    uint32_t free_head, obj_size, capacity;
    // data[]
} Slab;
  • slab_size: 4-8 KB (page)。
  • obj_size: 16/32/64/128 等 bucket。
  • 清单：partial/full/empty 链表；free_head 嵌入对象头；阈值 free_count <10% → reclaim。

三者比较与组合策略

维度 Arena Buddy Slab
分配时间 O(1) bump O(log N) O(1) pop
外部 frag 低 (arena 内) 中等 极低
内部 frag 对齐废 2^k 废 元数据废
吞吐 最高 中 高
延迟 jitter 最低 中 低

组合落地：Buddy 供页 → Slab 热小对象 → Arena per-thread 临时。

  • 参数：buddy min_order=8 (256B)；slab bucket 8 类；arena 5 个 /thread，1MB / 个。
  • 监控清单：
    1. frag_ratio = used / total <80%。
    2. p99 alloc_latency <100ns (perf 采样)。
    3. slab partial_ratio >50% → 调大 slab_size。
  • 回滚：渐进替换，先 slab 包 malloc；A/B 测试 RSS/CPU。

这种策略在 jemalloc-like 系统常见，C 游戏引擎 / 服务器验证有效。最后，资料来源：

（正文字数：约 1250）

查看归档