4. 显存池数据结构：空闲链表、哈希表索引、伙伴系统
好，咱们今天聊聊显存池里最核心的三个数据结构。说实话，我刚接触这块时也觉得头大，什么链表、哈希表、伙伴系统，听着就吓人。但后来我发现，搞懂了它们，显存管理那点事儿基本就通了八成。
4.1 空闲链表（FreeList）—— 最朴素的管理方式
空闲链表，说白了就是把所有空闲的显存块串成一个链表。每次要分配，就从链表头取一块；释放了，再挂回去。
我在项目中遇到过一种情况：某个模型训练时频繁申请释放小显存块，结果空闲链表越变越长，分配速度越来越慢。嗯，这就是典型的「碎片化」问题。
核心要点：
- 每个节点记录：起始地址 + 块大小
- 分配策略：First Fit（首次适应）、Best Fit（最佳适应）、Worst Fit（最差适应）
- 释放操作：O(1) 插入链表头，但合并相邻空闲块需要遍历
你想想看，如果只用空闲链表，大模型训练时频繁分配 4KB、8KB 的小块，很快就会出现「有空间但没连续块」的尴尬。这时候就需要更高级的数据结构了。
4.2 哈希表索引 —— 让查找飞起来
空闲链表的痛点在于查找慢。尤其是当你需要找一块「刚好 256KB」的显存时，得从头遍历到尾。哈希表就是来解决这个问题的。
我个人习惯用「大小哈希」的方式：以块大小为 key，把相同大小的空闲块挂到同一个桶里。这样查找特定大小的块，时间复杂度直接降到 O(1)。
// 伪代码示例：哈希表索引结构
struct FreeListHash {
void* blocks[1024]; // 按大小分桶
int block_count[1024]; // 每个桶的块数
};
// 分配 256KB 显存
void* alloc_256k() {
int bucket = 256; // 直接定位到 256KB 的桶
if (hash->block_count[bucket] > 0) {
return pop_block(hash, bucket);
}
// 没找到，走伙伴系统或更大块分裂
return split_larger_block(hash, 256);
}我的经验：哈希表桶的数量不要设太细。比如 1KB、2KB、4KB... 这样指数增长，通常 20-30 个桶就够用了。太细了反而浪费内存，而且命中率提升有限。
4.3 伙伴系统（Buddy System）—— 显存管理的王牌
终于聊到伙伴系统了。说实话，这是我最喜欢的数据结构，没有之一。它优雅地解决了碎片化问题，而且效率极高。
核心思想：把显存不断对半切分，形成 2 的幂次大小的块。释放时，如果相邻的「伙伴块」也是空闲的，就合并成更大的块。
举个例子：你要分配 64KB，系统从 1MB 的大块开始切：
- 1MB → 两个 512KB（伙伴对）
- 512KB → 两个 256KB
- 256KB → 两个 128KB
- 128KB → 两个 64KB（分配一个，另一个空闲）
释放时，检查它的伙伴（另一个 64KB）是否空闲。如果是，合并成 128KB；再检查 128KB 的伙伴... 一直往上合并。
我曾经踩过的坑：伙伴系统要求所有分配大小都是 2 的幂次。如果你要分配 100KB，实际会给你 128KB，浪费了 28KB。这就是所谓的「内部碎片」。所以实际工程中，我们通常把请求大小向上取整到 2 的幂次。
4.4 三种数据结构的对比
| 特性 | 空闲链表 | 哈希表索引 | 伙伴系统 |
|---|---|---|---|
| 分配时间复杂度 | O(n) | O(1) ~ O(k) | O(log N) |
| 释放时间复杂度 | O(1) 或 O(n) | O(1) | O(log N) |
| 外部碎片 | 严重 | 中等 | 几乎无 |
| 内部碎片 | 无 | 无 | 最多 50% |
| 实现复杂度 | 低 | 中 | 高 |
实际工程中，没人只用一种数据结构。我参与过的项目里，通常是「伙伴系统 + 哈希表」的组合拳：伙伴系统负责大块内存的拆分合并，哈希表负责缓存常用大小的块，减少拆分合并的开销。
4.5 核心逻辑流程图
下面这张图展示了三种数据结构在显存分配和释放时的协作关系：
这张图展示了完整的分配流程：用户请求进来，先查哈希表看有没有常用大小的块；没有就走伙伴系统去切分；切分出来的块由空闲链表管理。释放时，伙伴系统会检查能否合并，合并后更新哈希表和空闲链表。
我的建议：刚开始实现时，别一上来就搞完整的伙伴系统。先写个简单的空闲链表跑通流程，再逐步加上哈希表索引，最后引入伙伴系统。这样出了问题也好定位。我当年就是这么干的，少走了不少弯路。
好了，三种数据结构都聊完了。你可能会问：「实际项目中到底用哪种？」我的答案是：看场景。小模型用空闲链表就够了，大模型训练必须上伙伴系统，而哈希表索引几乎是标配——它带来的性能提升太明显了。
记住一句话：没有银弹。好的显存池设计，是根据业务场景灵活组合这些数据结构。