块管理算法：空闲块链表、最佳适应、首次适应与伙伴系统
聊完了显存池的整体架构，咱们得深入看看最核心的部分——块管理算法。
说白了，显存池就像一个大仓库。你往里存数据（分配），往外取数据（释放）。但仓库里的空间有大有小，怎么高效地管理这些碎片化的空间，就是块管理算法要解决的问题。
我这些年调过不少框架的显存分配器，从PyTorch的缓存分配器到TensorFlow的BFC Allocator，底层用的算法其实就那几种。今天咱们把这四种经典算法掰开揉碎了讲清楚。
1. 空闲块链表：最朴素的管理方式
先看最简单的。空闲块链表，就是把所有空闲的内存块串成一个链表。
每次分配时，遍历链表，找到一块足够大的空间。释放时，把块插回链表，顺便检查能不能和前后合并。
嗯，这里要注意：合并操作是性能关键。我早期做嵌入式开发时，就吃过不合并的亏——分配几次再释放，链表越来越长，最后分配一个128字节的小块都要遍历几百个节点。
核心数据结构：
struct FreeBlock {
void* addr; // 起始地址
size_t size; // 块大小
FreeBlock* next; // 指向下一个空闲块
FreeBlock* prev; // 指向前一个空闲块（双向链表）
};优点很明显：实现简单，逻辑直观。缺点也很致命：分配速度不稳定。最坏情况下要遍历整个链表，时间复杂度O(n)。
我在项目中遇到过这种情况：训练一个超大模型时，显存池里的空闲块被切得七零八落，链表长度飙到上千。每次分配都要卡一下，训练速度肉眼可见地下降。
2. 首次适应算法：快，但不一定最优
首次适应算法，名字就说明了策略——找到第一个能用的块就分配。
它和空闲块链表是搭档。分配时从头开始遍历，遇到大小足够的块就直接用。如果块比需求大很多，就切一块出来，剩下的放回链表。
我个人习惯在小规模分配场景下用这个算法。为什么？因为它快啊！不需要找最优解，第一个能用的就上。
但有个坑：容易产生碎片。你想想看，每次都从链表头部切，前面的块越切越小，最后全是小碎片。大块需求来了，得跑到链表尾部才能找到合适的。
我的经验：首次适应算法适合分配大小比较均匀的场景。如果分配大小差异很大，建议别用这个。
3. 最佳适应算法：追求极致，但代价不小
最佳适应算法，顾名思义——找最合适的，不是第一个。
它会遍历整个空闲链表，找到一块大小刚好大于等于需求的最小块。这样切完后剩下的碎片最小，理论上能减少浪费。
听起来很完美对吧？但实际用起来，我劝你慎重。
为什么？因为遍历开销太大了。每次分配都要扫描整个链表，时间复杂度O(n)。而且，它会产生大量极小碎片——每次切完剩一点点，这些小块几乎没法再利用。
我记得有一次优化一个推理引擎的显存分配器，用了最佳适应算法。结果呢？分配延迟从微秒级飙到毫秒级，模型推理的P99延迟直接炸了。后来换回首次适应，问题解决。
避坑指南：我曾经在实时性要求高的场景里用最佳适应算法，结果被坑得很惨。如果你对延迟敏感，建议用首次适应或者伙伴系统。
4. 伙伴系统：工业界的首选
终于聊到重点了。伙伴系统，这是目前深度学习框架里用得最多的块管理算法。PyTorch的CachingAllocator、TensorFlow的BFC Allocator，底层都基于伙伴系统的思想。
它的核心思想很简单：把内存按2的幂次划分。比如2KB、4KB、8KB、16KB……每个大小级别维护一个空闲链表。
分配时，找到大于等于需求的最小2的幂次块。如果没有，就向上找更大的块，然后不断对半切，直到切出合适的大小。
释放时，检查它的伙伴（和它大小相同、地址相邻的块）是否空闲。如果是，就合并成一个更大的块，再检查上一级的伙伴……一直合并到不能合并为止。
伙伴系统的核心操作：
// 分配：从2^k大小的空闲链表中取块
// 如果没有，从2^(k+1)的链表中取一块，切成两个2^k的块
// 一个返回给用户，另一个插入2^k的空闲链表
// 释放：检查伙伴是否空闲
// 伙伴地址 = 当前地址 XOR (1 << k) * 块大小
// 如果伙伴空闲，合并，然后继续向上检查我为什么说它是工业界首选？三个原因：
- 分配和释放都是O(1)或O(logN)，性能稳定
- 碎片少，因为块大小都是2的幂次，天然对齐
- 合并效率高，通过伙伴地址公式直接计算，不需要遍历链表
当然，它也有缺点：内部碎片。比如你申请一个3KB的块，系统会给你4KB的块，浪费了1KB。但相比其他算法的外部碎片问题，这点浪费是可以接受的。
四种算法对比
我整理了一张表，方便你对比：
| 算法 | 分配复杂度 | 释放复杂度 | 碎片程度 | 适用场景 |
|---|---|---|---|---|
| 空闲块链表 | O(n) | O(1)~O(n) | 高 | 简单场景、嵌入式 |
| 首次适应 | O(n) | O(1)~O(n) | 中 | 分配大小均匀的场景 |
| 最佳适应 | O(n) | O(1)~O(n) | 低（但极小碎片多） | 对内存利用率要求极高 |
| 伙伴系统 | O(logN) | O(logN) | 低（内部碎片） | 深度学习框架、通用场景 |
知识体系总览
下面这张图，把四种算法的关系和核心逻辑串起来了：
实际框架中的选择
你可能会问：这些算法在真实框架里是怎么用的？
我直接告诉你答案：没有哪个框架只用一种算法。
PyTorch的CachingAllocator，底层是伙伴系统管理大块内存，但每个大小级别内部用空闲块链表串起来。分配时先查伙伴系统，如果找不到合适的块，再向CUDA申请新的显存。
TensorFlow的BFC Allocator，本质上是伙伴系统的变种。它把内存分成多个Bin（类似伙伴系统的大小级别），但Bin的大小不是严格的2的幂次，而是根据实际分配模式动态调整的。
我个人建议：如果你自己实现显存池，优先考虑伙伴系统。它虽然不是最完美的，但综合性能最好，坑也最少。
嗯，今天就聊到这儿。这些算法看着简单，但真正调优起来门道很多。下次咱们可以聊聊碎片整理和跨设备显存池的话题。
想要更多资料，联系可可