3. 内存分配策略：首次适应（First Fit）与最佳适应（Best Fit）算法
好，咱们继续。上一章我们把显存池的骨架搭好了——一个连续的大块内存，加上空闲链表来管理。但链表有了，怎么从里面挑一块合适的出来？这就是分配策略要解决的问题。
说白了，分配策略就是回答一个问题：当用户要一块 N 字节的内存时，我该从哪个空闲块下手？
我刚开始写显存池时，觉得这还不简单？从头遍历，找到第一个够大的就给它。后来发现，事情远没那么单纯。不同的选择策略，会直接影响内存碎片的多寡和分配效率。今天我们就来掰扯掰扯两种最经典的策略：首次适应（First Fit）和最佳适应（Best Fit）。
3.1 首次适应（First Fit）
首次适应的逻辑非常直白：从链表头开始，找到第一个大小 >= 请求大小的空闲块，就分配出去。
你想想看，这就像你去停车场找车位，看到第一个空位就停进去，不管它是在入口还是深处。简单粗暴，效率高。
3.1.1 算法流程
- 从空闲链表头部开始遍历
- 对每个空闲块，检查其大小是否 >= 请求大小
- 如果找到，从该块中切出所需大小，剩余部分作为新空闲块插回链表
- 如果遍历完都没找到，返回分配失败
3.1.2 代码实现
// 首次适应分配
void* first_fit_alloc(MemoryPool* pool, size_t size) {
// 对齐到8字节（GPU内存通常要求对齐）
size = align_up(size, 8);
FreeBlock* curr = pool->free_list;
FreeBlock* prev = NULL;
while (curr != NULL) {
if (curr->size >= size) {
// 找到了！从当前块切分
if (curr->size > size + sizeof(FreeBlock)) {
// 剩余空间足够形成一个新的空闲块
FreeBlock* new_block = (FreeBlock*)((char*)curr + sizeof(FreeBlock) + size);
new_block->size = curr->size - size - sizeof(FreeBlock);
new_block->next = curr->next;
// 更新当前块大小（只分配需要的部分）
curr->size = size;
// 将新空闲块插入链表
if (prev == NULL) {
pool->free_list = new_block;
} else {
prev->next = new_block;
}
} else {
// 剩余空间太小，整块分配出去
if (prev == NULL) {
pool->free_list = curr->next;
} else {
prev->next = curr->next;
}
}
// 标记为已分配
curr->next = NULL;
return (void*)((char*)curr + sizeof(FreeBlock));
}
prev = curr;
curr = curr->next;
}
// 没找到合适的块
return NULL;
}
个人经验：我第一次实现时忘了处理「剩余空间太小」的情况。结果分配 64 字节时，一个 128 字节的块被切成了 64+64，但剩下的 64 字节因为不够放一个 FreeBlock 头（16 字节），导致链表指针错乱。嗯，后来我加了个阈值判断：剩余空间必须大于 sizeof(FreeBlock) + 最小分配单元，才允许切分。
3.1.3 优缺点分析
| 维度 | 评价 |
|---|---|
| 分配速度 | 快。通常很快就能找到合适的块，尤其是前面有小块时 |
| 内存利用率 | 一般。容易在链表头部产生大量小碎片 |
| 实现复杂度 | 低。逻辑简单，代码量少 |
| 适用场景 | 小块分配多、对延迟敏感的场景 |
3.2 最佳适应（Best Fit）
最佳适应就讲究多了。它的策略是：遍历整个空闲链表，找到大小 >= 请求大小，且最接近请求大小的那个块。
说白了，就是「量体裁衣」——找一块刚好够用的，尽量减少浪费。我早期做嵌入式系统时，内存只有 64KB，那时候最佳适应几乎是标配，因为每一字节都金贵。
3.2.1 算法流程
- 遍历整个空闲链表
- 记录所有大小 >= 请求大小的块
- 从中选出大小最小的那个（即最接近请求大小的）
- 从该块中切出所需大小，剩余部分插回链表
3.2.2 代码实现
// 最佳适应分配
void* best_fit_alloc(MemoryPool* pool, size_t size) {
size = align_up(size, 8);
FreeBlock* curr = pool->free_list;
FreeBlock* best = NULL;
FreeBlock* best_prev = NULL;
FreeBlock* prev = NULL;
size_t best_size = SIZE_MAX; // 初始化为最大可能值
// 第一遍：遍历找到最佳块
while (curr != NULL) {
if (curr->size >= size && curr->size < best_size) {
best = curr;
best_prev = prev;
best_size = curr->size;
// 如果找到完全匹配的，直接退出（不可能更好了）
if (curr->size == size) {
break;
}
}
prev = curr;
curr = curr->next;
}
if (best == NULL) {
return NULL; // 没找到合适的块
}
// 第二遍：从最佳块中切分（逻辑同首次适应）
if (best->size > size + sizeof(FreeBlock)) {
FreeBlock* new_block = (FreeBlock*)((char*)best + sizeof(FreeBlock) + size);
new_block->size = best->size - size - sizeof(FreeBlock);
new_block->next = best->next;
best->size = size;
if (best_prev == NULL) {
pool->free_list = new_block;
} else {
best_prev->next = new_block;
}
} else {
if (best_prev == NULL) {
pool->free_list = best->next;
} else {
best_prev->next = best->next;
}
}
best->next = NULL;
return (void*)((char*)best + sizeof(FreeBlock));
}
注意：最佳适应需要遍历整个链表，时间复杂度是 O(n)。如果空闲块数量很大（比如几千个），每次分配都遍历一次，性能会急剧下降。我曾经在一个项目里，显存池的空闲块数量到了 5000+，最佳适应的分配延迟从微秒级飙升到毫秒级，直接导致帧率掉了一半。后来我换成了首次适应 + 定期整理，才把性能救回来。
3.2.3 优缺点分析
| 维度 | 评价 |
|---|---|
| 分配速度 | 慢。必须遍历整个链表 |
| 内存利用率 | 高。碎片更少，浪费更小 |
| 实现复杂度 | 中。需要记录最佳候选 |
| 适用场景 | 内存紧张、分配次数少的场景 |
3.3 两种策略的对比
为了让你更直观地理解，我画了一张图：
3.4 如何选择？我的建议
说实话，没有银弹。两种策略各有千秋，我一般根据这几个因素来选：
- 内存是否紧张？ 如果显存只有 2GB，但应用要跑大模型，选最佳适应，省着点用。
- 分配频率高不高？ 如果每帧要分配/释放几百次，选首次适应，别让遍历拖垮性能。
- 分配大小是否规律？ 如果每次分配的大小都差不多（比如纹理、缓冲区大小固定），最佳适应反而容易产生碎片——因为每次都会留下一个很小的剩余块，久而久之全是小碎片。
我的经验法则：首次适应适合 80% 的场景。只有在内存极度紧张（比如嵌入式 GPU、老显卡）或者分配次数很少时，我才考虑最佳适应。而且，不管用哪种策略，定期整理碎片才是王道——这个我们后面会专门讲。
3.5 避坑指南
最后分享几个我踩过的坑：
- 对齐问题：GPU 内存通常要求 256 字节或 512 字节对齐。我一开始没做对齐，结果分配出来的地址不对，驱动直接报错。记得在分配前做对齐处理。
- 链表遍历性能：如果空闲块数量超过 1000，每次分配都遍历链表会非常慢。可以考虑用「伙伴系统」或者「分级空闲链表」来优化——这个我们后面章节会讲。
- 并发安全：多线程分配时，别忘了加锁。我见过一个项目，两个线程同时分配，结果链表指针被改乱了，内存池直接崩了。最简单的做法是用互斥锁保护整个分配过程。
好了，分配策略就聊到这里。记住：首次适应求快，最佳适应求省。选哪个，取决于你的场景。下一章我们聊聊释放和合并——嗯，这部分其实比分配更有意思。