3. 动态分配算法：Best-Fit、First-Fit、Buddy System 在显存池中的应用
动态显存分配，说白了就是「谁来管这块地」。显存池建好了，但每次申请释放时，怎么找一块合适的空闲块？这就是分配算法的事。
我最早做 GPU 推理框架时，直接用了 malloc/free 的简单封装。结果呢？跑几个模型就碎成渣了——显存碎片化严重，大块连续内存死活申请不到。后来才老老实实研究这些经典算法。
今天咱们就聊聊三种最常见的：Best-Fit、First-Fit、Buddy System。它们各有脾气，也各有坑。
核心观点：没有完美的算法，只有适合场景的算法。显存分配尤其看重「碎片控制」和「分配速度」。
3.1 First-Fit：简单粗暴，但容易「头重脚轻」
First-Fit 的思路很简单：从空闲链表头开始，找到第一个大小足够的块就分配。
优点很明显——快。O(n) 的查找，但实际中往往很快命中。我在早期原型里用过它，写起来也就几十行代码。
但问题也来了：头部区域会被频繁切碎。小分配总是从头部拿，大块被切得越来越小。时间一长，头部全是小碎片，尾部还留着大块。这叫「外碎片」问题。
// 伪代码：First-Fit 分配
void* first_fit_alloc(size_t size) {
FreeBlock* curr = free_list_head;
while (curr) {
if (curr->size >= size) {
// 切分或直接分配
if (curr->size - size > MIN_BLOCK_SIZE) {
split_block(curr, size);
}
remove_from_free_list(curr);
return curr->addr;
}
curr = curr->next;
}
return NULL; // 分配失败
}
我的经验：First-Fit 适合「分配大小比较均匀」的场景。如果模型 tensor 大小差异很大，别用它，碎片会让你崩溃。
3.2 Best-Fit：追求「刚刚好」，但代价不小
Best-Fit 的理念是：遍历所有空闲块，找到「大小最接近但又不小于申请量」的那一块。
听起来很完美对吧？理论上它产生的碎片最小。但实际上，它有两个硬伤：
- 遍历成本高：每次都要扫整个链表，O(n) 是跑不掉的。显存池里块数一多，分配延迟就上去了。
- 产生大量「微碎片」：因为总是找最接近的，切出来的剩余块往往非常小。这些小到没法用的块，慢慢就堆积成山。
我曾经在一个图像处理管线里试过 Best-Fit。分配 4KB、8KB 这种小块时，效果还行。但一旦混入 1MB 以上的大块，微碎片数量暴涨，最后连 2MB 的连续空间都凑不出来。
// 伪代码：Best-Fit 分配
void* best_fit_alloc(size_t size) {
FreeBlock* best = NULL;
FreeBlock* curr = free_list_head;
size_t min_waste = SIZE_MAX;
while (curr) {
if (curr->size >= size) {
size_t waste = curr->size - size;
if (waste < min_waste) {
min_waste = waste;
best = curr;
}
}
curr = curr->next;
}
if (best) {
if (best->size - size > MIN_BLOCK_SIZE) {
split_block(best, size);
}
remove_from_free_list(best);
return best->addr;
}
return NULL;
}
避坑指南：我曾经在 Best-Fit 里加了个「最小剩余块阈值」，小于 64 字节就不切了，直接整块分配。这能有效减少微碎片，但会浪费一点空间。算是个 trade-off。
3.3 Buddy System：用「二分法」解决碎片问题
Buddy System 是我个人最喜欢的方案。它的核心思想是：把内存不断对半切，直到大小合适。
举个例子：你有一个 1MB 的块。申请 128KB 时，1MB → 512KB → 256KB → 128KB。释放时，如果它的「伙伴」（另一半）也是空闲的，就合并回去。
这样做的好处很明显：
- 分配和释放都是 O(log N)，比线性扫描快得多
- 碎片可控：所有块大小都是 2 的幂，合并时天然对齐
- 实现简单：用数组维护不同 size class 的链表就行
但缺点也有：内部碎片。你申请 100KB，它给你 128KB 的块，浪费了 28KB。如果申请大小很随机，浪费率可能到 30%-40%。
// 伪代码：Buddy System 分配
#define MAX_ORDER 20 // 最大 2^20 = 1MB
typedef struct {
void* addr;
int order; // 2^order 大小
} Block;
Block* buddy_alloc(int order) {
// 从当前 order 链表找
if (!free_lists[order].empty()) {
return free_lists[order].pop();
}
// 向上找更大的块，分裂
int current = order + 1;
while (current <= MAX_ORDER) {
if (!free_lists[current].empty()) {
Block* block = free_lists[current].pop();
// 分裂：一分为二
while (current > order) {
current--;
Block* buddy = split(block, current);
free_lists[current].push(buddy);
}
return block;
}
current++;
}
return NULL; // 没有足够内存
}
关键点：Buddy System 的「伙伴」地址计算很简单——buddy_addr = block_addr ^ (1 << order)。异或一下就行，硬件友好。
3.4 三种算法对比：选哪个？
我整理了一张表，方便你对比：
| 算法 | 分配速度 | 外碎片 | 内碎片 | 适用场景 |
|---|---|---|---|---|
| First-Fit | 快（O(n) 但常命中头部） | 高（头部碎片严重） | 低 | 大小均匀的分配 |
| Best-Fit | 慢（全遍历 O(n)） | 中（微碎片多） | 低 | 追求空间利用率 |
| Buddy System | 很快（O(log N)） | 低（合并机制好） | 高（2 的幂对齐） | 实时系统、GPU 显存 |
我个人在显存池里，首选 Buddy System。原因很简单：GPU 显存分配要求速度快、碎片少。Buddy 的 O(log N) 时间在毫秒级分配场景下很稳。至于内部碎片？显存通常够大，浪费一点可以接受。
一个小技巧：如果申请大小集中在几个固定值（比如 1MB、4MB、16MB），可以给每个 size 单独开一个 Buddy 池。这样内部碎片几乎为零，分配也更快。
3.5 显存池中的实战选择
实际项目中，我见过几种混合方案：
- 大块用 Buddy，小块用 slab：大于 1MB 的走 Buddy，小于 1MB 的走固定大小 slab 分配器。这样兼顾了大块连续和小块高效。
- First-Fit + 定期整理：有些框架用 First-Fit，但后台跑一个整理线程，把碎片合并。代价是 CPU 开销和暂停时间。
- 纯 Buddy：NVIDIA 的 cuMem 底层其实就类似 Buddy。简单、可靠、够用。
我记得有一次调优，发现 Buddy 的合并逻辑在频繁分配释放时成了瓶颈。后来加了「延迟合并」——释放时不立即合并，等空闲块数量超过阈值再批量合并。性能提升了 20%。
注意：Buddy System 的合并操作如果太频繁，会引入额外延迟。尤其是多线程场景下，合并时加锁会影响并发。建议用无锁队列或分桶策略来优化。
3.6 核心逻辑流程图
下面这张图展示了三种算法在显存池中的决策路径：
嗯，看到这里你应该明白了：没有银弹。选哪种算法，取决于你的显存使用模式。如果分配大小很随机，Buddy 是稳妥的选择。如果追求极致空间利用率，Best-Fit 配合碎片整理也能用。如果图省事，First-Fit 加个「从尾部开始扫描」的优化，也能应付不少场景。
我个人建议：从 Buddy System 起步。它实现简单、性能稳定、碎片可控。等遇到性能瓶颈了，再针对性地优化或混合其他算法。别一开始就搞太复杂，容易把自己绕进去。
最后一个小提醒：不管用哪种算法，记得加「分配失败回退」机制。比如 Buddy 分配失败时，尝试触发一次全局合并，再试一次。这能显著提高分配成功率。
好了，动态分配算法就聊到这儿。下一节咱们会深入 Buddy System 的实现细节，包括伙伴地址计算、合并时机、多线程安全等实战问题。