显存池的分配策略：四种算法的实战对比
大家好，我是你们的老朋友。今天我们来聊聊显存池里最核心的问题——分配策略。
说白了，就是当你的程序要一块显存时，池子该怎么给它？给哪块？给多大？
我当年刚接触显存池时，觉得这玩意儿不就是个malloc吗？后来被坑了几次才明白——分配策略选不对，性能直接腰斩。
今天咱们就掰开揉碎，把四种经典策略讲透：首次适应、最佳适应、最差适应、伙伴系统。
一、先看一张图：四种策略的核心逻辑
我习惯用一张图来理解这四种策略的区别。你看下面这张SVG图，它展示了同一个显存块（64MB）被分配和释放后，四种算法各自的选择路径。
嗯，这张图把四种策略的决策路径画得很清楚。接下来咱们一个一个细说。
二、首次适应算法（First Fit）
核心思想：从显存池的头部开始扫描，找到第一个大小足够的空闲块就分配。
这就像你去停车场找车位，从入口开始，看到第一个空位就停进去。简单粗暴。
优点：
- 速度最快——找到就停，不用遍历所有空闲块
- 实现简单——一个循环就搞定
缺点：
- 容易产生碎片——头部被切得七零八落
- 大块请求可能失败——头部全是小碎片
我在项目中遇到过一个问题：用首次适应跑一个视频处理管线，跑了半小时后，显存池头部全是几KB的小碎片，一个16MB的纹理愣是分配不出来。后来我加了个碎片整理机制才解决。
// 首次适应算法伪代码
void* first_fit(size_t size) {
for (每个空闲块) {
if (空闲块大小 >= size) {
分配该块;
更新空闲链表;
return 块地址;
}
}
return NULL; // 分配失败
}
我的建议：如果你的显存池不大（比如256MB以内），且分配释放频率不高，首次适应完全够用。别过度优化。
三、最佳适应算法（Best Fit）
核心思想：遍历所有空闲块，找到大小最接近请求大小的那个块。
说白了就是「精打细算」——我要6MB，你有个7MB的块，还有个12MB的块，我选7MB那个，因为浪费最少。
优点：
- 碎片最小——每次切割都尽量「刚刚好」
- 大块保留——大块不会被切碎
缺点：
- 速度慢——每次都要遍历所有空闲块
- 产生微小碎片——剩下来的都是几KB的「鸡肋」
我曾经在一个深度学习推理引擎里用过最佳适应。结果发现，每次分配都要遍历几百个空闲块，光分配开销就占了总时间的5%。后来我换成了伙伴系统，分配开销降到了0.1%以下。
// 最佳适应算法伪代码
void* best_fit(size_t size) {
空闲块* best = NULL;
for (每个空闲块) {
if (空闲块大小 >= size) {
if (best == NULL || 空闲块大小 < best->size) {
best = 当前块;
}
}
}
if (best) {
分配best;
更新空闲链表;
return best->地址;
}
return NULL;
}
注意：最佳适应并不「最佳」。它只是碎片最少，但性能可能很差。我见过有人用最佳适应跑实时渲染，结果每帧分配耗时超过1ms，直接掉帧。
四、最差适应算法（Worst Fit）
核心思想：找最大的空闲块来分配。
你想想看，为什么要找最大的？因为切完后剩下的部分还是很大，下次还能用。
这就像你切蛋糕——从最大的那块切，剩下的还能分给别人。
优点：
- 大块保留——最大的块被切后，剩下的仍然是大块
- 适合大块请求——大块不会被小请求切碎
缺点：
- 浪费空间——每次都用最大的，小块永远用不上
- 速度慢——也要遍历所有空闲块
我记得有一次做显存池预分配，我用了最差适应。结果发现，所有大块都被切成了中等块，而小请求却找不到合适的小块。最后我改成混合策略——大请求用最差适应，小请求用最佳适应。
// 最差适应算法伪代码
void* worst_fit(size_t size) {
空闲块* worst = NULL;
for (每个空闲块) {
if (空闲块大小 >= size) {
if (worst == NULL || 空闲块大小 > worst->size) {
worst = 当前块;
}
}
}
if (worst) {
分配worst;
更新空闲链表;
return worst->地址;
}
return NULL;
}
我的经验：最差适应适合请求大小相对均匀的场景。如果请求大小差异很大，别用它。
五、伙伴系统（Buddy System）
核心思想：把显存按2的幂次分割。比如64MB分成两个32MB，32MB再分成两个16MB，以此类推。
分配时，找到最小的2的幂次块（比如请求6MB，就分配8MB的块）。释放时，如果它的「伙伴」（相邻的同大小块）也是空闲的，就合并成一个更大的块。
优点：
- 合并方便——伙伴合并机制天然防碎片
- 分配快——用位图或数组，O(1)或O(logN)
- 实现简单——Linux内核就在用
缺点：
- 内部碎片——请求6MB给8MB，浪费2MB
- 内存膨胀——最坏情况浪费50%
我强烈推荐伙伴系统。为什么？因为它在分配速度和碎片控制之间取得了最好的平衡。
我之前优化一个实时渲染引擎，显存分配从首次适应换成伙伴系统后，帧率从45fps提升到了58fps。分配耗时从2.3ms降到了0.08ms。
// 伙伴系统核心逻辑（简化版）
#define MAX_ORDER 10 // 最大2^10=1024块
typedef struct {
void* addr;
int order; // 2^order 大小
} buddy_block;
void* buddy_alloc(int order) {
// 查找空闲链表
for (int i = order; i <= MAX_ORDER; i++) {
if (free_list[i] != NULL) {
// 如果找到的块比需要的大，不断对半切
while (i > order) {
切一半;
把另一半加入 free_list[i-1];
i--;
}
分配该块;
return 块地址;
}
}
return NULL; // 分配失败
}
void buddy_free(void* addr, int order) {
// 找伙伴
buddy = 伙伴地址;
if (伙伴空闲 && 伙伴order == order) {
合并成更大的块;
buddy_free(合并后的地址, order+1);
} else {
加入 free_list[order];
}
}
注意：伙伴系统的内部碎片问题。如果你频繁分配奇数大小的块（比如3MB、5MB），浪费会很严重。我建议对齐到2的幂次，或者用slab分配器做补充。
六、四种策略对比总结
| 策略 | 分配速度 | 碎片程度 | 实现复杂度 | 适用场景 |
|---|---|---|---|---|
| 首次适应 | 快 | 高 | 低 | 小池子、低频分配 |
| 最佳适应 | 慢 | 低 | 中 | 对碎片敏感的场景 |
| 最差适应 | 慢 | 中 | 中 | 请求大小均匀的场景 |
| 伙伴系统 | 很快 | 中（内部碎片） | 中高 | 通用场景、实时系统 |
我的最终建议：
- 如果你在写通用显存池，首选伙伴系统
- 如果池子很小（<64MB），首次适应就够了
- 如果对碎片零容忍，用最佳适应+定期碎片整理
- 最差适应...嗯，我很少用，除非你有特殊需求
好了，四种分配策略就讲到这里。记住一句话：没有银弹。每种策略都有它的脾气，你得根据实际场景来选。
下一章我们会聊显存池的回收策略——释放时怎么合并？怎么防碎片？到时候见。
想要更多资料，联系可可