显存池核心数据结构：空闲链表、哈希表、伙伴系统

聊到显存池优化，很多人第一反应是「不就是个内存分配器吗？」
嗯，这话对了一半。显存池确实借鉴了传统内存管理的思路，但GPU的硬件特性决定了它没那么简单。

我个人习惯把显存池的核心数据结构分成三类：空闲链表、哈希表、伙伴系统。
这三样东西，说白了就是显存池的「三驾马车」。你搞懂了它们，显存池的骨架就搭起来了。

1. 空闲链表：最朴素，也最实用

空闲链表，顾名思义，就是把所有空闲的显存块串成一个链表。
每个节点记录着：块起始地址、块大小、下一个空闲块的指针。

我在项目中遇到过一种情况：模型训练时频繁申请释放小张量，空闲链表被切得七零八落。
这就是碎片化问题。你想想看，每次分配都要遍历链表找合适大小的块，效率能高吗？

  核心要点：
  分配策略：First Fit（首次适应）、Best Fit（最佳适应）、Next Fit（下次适应）
释放策略：合并相邻空闲块，减少碎片
适用场景：小规模、低频次的显存分配

我的经验： 如果你做推理部署，空闲链表其实够用。但做训练，尤其是动态图训练，千万别只用它。

2. 哈希表：加速查找，解决「找块慢」的问题

空闲链表最大的痛点是什么？
查找慢。每次分配都要O(n)遍历。

哈希表就是来救场的。我们把「块大小」作为key，把「相同大小的空闲块链表」作为value。
这样一来，分配时直接根据大小哈希到对应的桶，拿第一个块就行。时间复杂度降到O(1)。

// 伪代码示例
struct FreeBlock {
    void* addr;
    size_t size;
    FreeBlock* next;
};

// 哈希表：size -> 空闲块链表
unordered_map<size_t, FreeBlock*> free_map;

// 分配：直接查表
FreeBlock* alloc(size_t size) {
    auto it = free_map.find(size);
    if (it != free_map.end()) {
        FreeBlock* block = it->second;
        free_map[size] = block->next;
        return block;
    }
    // 没找到，走后备分配路径
    return nullptr;
}

我曾经踩过一个坑：哈希表桶的数量设置不合理，导致哈希冲突严重，性能反而比链表还差。
后来我学乖了，桶数一般取2的幂次，比如1024或4096，具体看你的显存分配粒度。

注意： 哈希表只适合「固定大小」的分配场景。如果你的模型里张量大小千奇百怪，哈希表会退化成链表。

3. 伙伴系统：解决碎片化的利器

伙伴系统，这个名字听起来有点玄乎。其实核心思想很简单：
把显存按2的幂次划分成块。分配时，找最小的能满足需求的2的幂次块。释放时，检查它的「伙伴」是否空闲，是的话就合并。

举个例子：
你要申请3MB显存。伙伴系统会给你分配4MB的块（2^2 MB）。
释放时，如果它的伙伴（也是4MB）也空闲，就合并成8MB的块。

  伙伴系统的核心数据结构：
  一个数组，每个元素对应一个2的幂次大小
每个元素是一个空闲块链表
释放时递归合并伙伴

// 伙伴系统核心逻辑
class BuddyAllocator {
    // free_area[i] 管理大小为 2^i 的空闲块
    list<Block> free_area[MAX_ORDER];
    
    Block* alloc(size_t size) {
        int order = ceil(log2(size));
        // 从 order 开始向上找空闲块
        for (int i = order; i < MAX_ORDER; i++) {
            if (!free_area[i].empty()) {
                Block* block = free_area[i].pop_front();
                // 如果块太大，分裂
                while (i > order) {
                    i--;
                    Block* buddy = split(block, i);
                    free_area[i].push_back(buddy);
                }
                return block;
            }
        }
        return nullptr; // 分配失败
    }
    
    void free(Block* block) {
        int order = block->order;
        // 尝试合并伙伴
        while (order < MAX_ORDER) {
            Block* buddy = get_buddy(block, order);
            if (buddy && buddy->is_free) {
                free_area[order].remove(buddy);
                block = merge(block, buddy);
                order++;
            } else {
                break;
            }
        }
        free_area[order].push_back(block);
    }
};

避坑指南： 我曾经在8卡A100上跑大模型训练，用了伙伴系统后显存碎片率从15%降到了3%以下。但要注意，伙伴系统内部碎片（internal fragmentation）是硬伤——你申请3MB，它给你4MB，那1MB就浪费了。

4. 三种数据结构的对比

特性	空闲链表	哈希表	伙伴系统
分配时间复杂度	O(n)	O(1) 平均	O(log n)
释放时间复杂度	O(1) 或 O(n)	O(1)	O(log n)
外部碎片	高	中	低
内部碎片	无	无	有（最多50%）
实现复杂度	低	中	高
适用场景	小规模、低频	固定大小分配	大规模、高频

5. 实际工程中的组合使用

说实话，没有哪个系统只用一种数据结构。
我参与过的几个工业级显存池，基本都是「三合一」的混合方案：

小块分配（< 1MB）：用哈希表，直接命中，快
中块分配（1MB ~ 128MB）：用伙伴系统，平衡碎片和性能
大块分配（> 128MB）：用空闲链表，因为大块数量少，遍历成本低

重要提醒： 千万别照搬操作系统的内存管理代码。GPU显存和CPU内存有本质区别——GPU的分配和释放开销更大，而且显存带宽是瓶颈。我见过有人把Linux内核的buddy allocator直接搬过来用，结果性能惨不忍睹。

6. 知识体系总览

下面这张图，是我自己画的一个显存池核心数据结构的逻辑关系图。你看一眼，基本就明白这三者怎么配合了。

嗯，这张图基本把今天的内容串起来了。
你从上往下看：显存池在最顶层，下面挂着三种核心数据结构，每种都有它的脾气和适用场景。最底下是实际工程中的组合策略——说白了就是「看菜下饭」，不同大小的分配走不同的路。

我的建议： 如果你刚开始做显存池，先从空闲链表入手。跑通了，再上哈希表。最后才是伙伴系统。一步到位搞伙伴系统，调试起来会让你怀疑人生。

好了，这一章就到这里。数据结构是显存池的骨架，下一章我们会往骨架上填肉——聊聊分配策略和回收策略的具体实现。

📚 课程目录

显存池核心数据结构：空闲链表、哈希表、伙伴系统

1. 空闲链表：最朴素，也最实用

2. 哈希表：加速查找，解决「找块慢」的问题

3. 伙伴系统：解决碎片化的利器

4. 三种数据结构的对比

5. 实际工程中的组合使用

6. 知识体系总览