动态分配算法：伙伴系统、Slab分配器与TLSF

显存管理，说白了就是怎么把有限的显存空间安排得明明白白。我做了这么多年GPU开发，见过太多因为显存分配不当导致的性能灾难。今天咱们聊聊三种经典的动态分配算法——伙伴系统、Slab分配器和TLSF。

这三种算法各有各的脾气。有的适合大块内存，有的擅长小对象，有的追求极致实时性。你想想看，如果你的程序需要频繁分配释放小块显存，用伙伴系统就有点大炮打蚊子了。

伙伴系统（Buddy System）

伙伴系统的思路很朴素：把内存不断对半切。我刚开始学这个算法时觉得它有点笨，后来才发现它其实很优雅。

它的核心规则就两条：

• 每次分配时，找到大小刚好够用的块，切到不能再切为止
• 释放时，检查相邻的"伙伴"是否空闲，是就合并回去

举个例子，假设你有1MB的显存块：

// 分配256KB
1MB → 512KB + 512KB
512KB → 256KB + 256KB  // 取走一个256KB

// 释放256KB，检查伙伴是否空闲
// 如果伙伴空闲，合并成512KB
256KB + 256KB → 512KB

我在项目中遇到过一个问题：频繁分配释放导致大量碎片。伙伴系统虽然能合并，但只限于伙伴之间。如果分配模式不规整，碎片率会很高。

Slab分配器

Slab分配器是专门为小对象设计的。我记得第一次在GPU驱动里看到它时，心想：这不就是对象池吗？

它的思路是这样的：

• 为每种大小的对象维护一个缓存（cache）
• 每个缓存包含多个slab（连续内存页）
• 每个slab被划分为固定大小的对象槽

分配和释放都很快，因为不需要搜索空闲链表，直接从slab里取一个槽就行。

// Slab分配器伪代码
struct slab_cache {
    size_t object_size;    // 对象大小
    int objects_per_slab;  // 每个slab的对象数
    struct list_head slabs_full;     // 已满的slab
    struct list_head slabs_partial;  // 部分空闲的slab
    struct list_head slabs_free;     // 完全空闲的slab
};

// 分配对象
void *slab_alloc(struct slab_cache *cache) {
    // 先从部分空闲的slab里找
    // 没有的话从完全空闲的slab里找
    // 都没有就分配新的slab
}

Slab分配器在Linux内核里用得很多，GPU驱动里也常见。说白了，它就是为那些频繁创建销毁的小对象量身定做的。

TLSF（Two-Level Segregated Fit）算法

TLSF是我个人比较喜欢的一个算法。它解决了伙伴系统的碎片问题和Slab分配器的灵活性不足。

它的核心思想是两级分离适配：

• 第一级：按大小范围分桶（比如2^0~2^1, 2^1~2^2, ...）
• 第二级：在每个桶内按精确大小分桶
• 使用位图快速定位合适的空闲块

这样做的好处是分配时间复杂度是O(1)，而且碎片率很低。

// TLSF的分配过程
void *tlsf_malloc(size_t size) {
    // 1. 计算size对应的第一级索引
    int fl = fls(size);  // 找到最高位
    
    // 2. 计算第二级索引
    int sl = (size >> (fl - SL_INDEX_COUNT_LOG2)) & (SL_INDEX_COUNT - 1);
    
    // 3. 在位图中查找空闲块
    // 4. 如果找到，分割并返回
    // 5. 如果没找到，去更大的桶里找
}

我曾经在一个实时渲染项目里用TLSF管理显存。场景需要频繁分配释放各种大小的纹理和缓冲区，TLSF的表现非常稳定，延迟抖动很小。

三种算法对比

特性	伙伴系统	Slab分配器	TLSF
时间复杂度	O(log N)	O(1)	O(1)
内部碎片	高（2的幂次对齐）	中（对象对齐）	低
外部碎片	中	低	低
适用场景	大块内存，规整分配	小对象，频繁分配释放	通用，实时性要求高
实现复杂度	低	中	高

实际选型建议

嗯，这里要注意，没有银弹。选哪种算法得看你的具体场景：

• 如果你的显存分配模式很规整，比如都是固定大小的纹理，用Slab分配器最合适
• 如果分配大小变化很大，但实时性要求不高，伙伴系统够用了
• 如果既要灵活性又要实时性，TLSF是首选

你想想看，显存分配这件事，说白了就是在时间效率和空间效率之间找平衡。没有完美的算法，只有最适合你场景的方案。

这三种算法各有千秋。我个人觉得，作为GPU开发者，至少要把TLSF搞明白。因为现在的GPU应用越来越复杂，显存分配的需求也越来越多样化。TLSF的O(1)分配和低碎片特性，让它成为很多现代显存管理器的首选。

好了，这一章就聊到这里。记住，显存分配没有银弹，理解每种算法的优缺点，才能做出最适合的选择。