3、内存池核心数据结构设计：固定大小块分配器、自由链表(Free List)、内存块元数据管理

好，咱们直接进入正题。内存池这东西，说白了就是提前跟操作系统要一大块内存，然后自己管自己分。为什么要这么干？因为频繁的 malloc/free 在回测系统里是性能杀手。我早年做高频回测时，一次 malloc 可能就让你错过一个 tick 的模拟信号。所以，自己管内存，是回测引擎的必修课。

今天咱们重点聊三个核心设计：固定大小块分配器、自由链表，以及内存块元数据管理。这三样东西组合起来，就是内存池的骨架。

3.1 固定大小块分配器：为什么是“固定大小”？

你想想看，回测系统里最频繁创建和销毁的是什么？是订单、成交记录、K线数据。这些对象的大小是固定的。比如一个订单结构体，就是 64 字节或 128 字节。既然大小固定，那我们就没必要用通用分配器去处理变长请求。

固定大小块分配器的思路很简单：把大块内存切成等长的小块。每个小块大小一致，分配时直接拿一块，释放时直接还回去。没有内存碎片，没有复杂算法。

我在项目中遇到过一个问题：一开始我用了变长分配器，结果回测跑了 10 万笔订单后，内存碎片率高达 30%。后来改成固定大小块，内存利用率直接拉到 95% 以上。嗯，这个教训挺深刻的。

3.2 自由链表：内存池的“快递员”

有了固定大小的块，怎么管理哪些块是空闲的？自由链表（Free List）就是干这个的。

自由链表本质上是一个单向链表，但它不存储数据，只存储空闲块的地址。每个空闲块的前 8 个字节（64 位系统）被当作指针，指向下一个空闲块。这样，我们不需要额外的内存来维护链表结构——空闲块本身就是链表节点。

分配时，从链表头部取一个块，头指针后移。释放时，把块插回链表头部。都是 O(1) 操作。

来看一个简单的实现骨架：

// 自由链表节点（其实就是空闲块的前8字节）
struct FreeNode {
    FreeNode* next;
};

// 固定大小块分配器
class FixedBlockAllocator {
private:
    void*  pool_start;      // 内存池起始地址
    size_t block_size;      // 每个块的大小
    size_t block_count;     // 块的总数
    FreeNode* free_head;    // 自由链表头指针

public:
    FixedBlockAllocator(size_t blk_size, size_t count) {
        block_size = blk_size;
        block_count = count;
        // 一次性申请大块内存
        pool_start = malloc(block_size * block_count);
        
        // 初始化自由链表：把所有块串起来
        free_head = (FreeNode*)pool_start;
        FreeNode* current = free_head;
        for (size_t i = 0; i < block_count - 1; i++) {
            current->next = (FreeNode*)((char*)pool_start + (i+1) * block_size);
            current = current->next;
        }
        current->next = nullptr;  // 最后一个块指向空
    }

    void* allocate() {
        if (free_head == nullptr) return nullptr;  // 内存耗尽
        void* ptr = free_head;
        free_head = free_head->next;
        return ptr;
    }

    void deallocate(void* ptr) {
        // 把释放的块插回链表头部
        ((FreeNode*)ptr)->next = free_head;
        free_head = (FreeNode*)ptr;
    }
};

这段代码看着简单，但效率极高。分配和释放都只有几条指针操作指令。我曾经在单线程回测中，用这个分配器替代 malloc，整体性能提升了 40%。

3.3 内存块元数据管理：别让“元数据”吃掉你的内存

自由链表解决了空闲块的管理，但还有一个问题：我怎么知道一个块属于哪个内存池？ 尤其是在多池场景下（比如订单池、成交池、K线池各一个），释放时得知道把块还给谁。

这就是元数据管理的职责。常见的做法有两种：

1. 隐式元数据： 在块头部或尾部存储池 ID 或大小信息。优点是通用，缺点是每个块多几个字节开销。
2. 显式元数据： 用单独的位图或数组记录每个块的状态。优点是查询快，缺点是需要额外内存。

我个人更倾向于隐式元数据 + 块对齐的方案。具体做法是：

• 每个内存池的起始地址和块大小都是固定的。
• 在块头部预留 8 字节，存储池的指针或 ID。
• 释放时，通过块地址计算出它属于哪个池。

来看一个带元数据的设计：

// 块头部元数据
struct BlockHeader {
    FixedBlockAllocator* pool;  // 指向所属的内存池
    // 可以扩展其他字段，比如校验和、时间戳等
};

// 分配时，返回的是元数据之后的数据区
void* FixedBlockAllocator::allocate() {
    if (free_head == nullptr) return nullptr;
    
    FreeNode* node = free_head;
    free_head = free_head->next;
    
    // 在块头部写入元数据
    BlockHeader* header = (BlockHeader*)node;
    header->pool = this;
    
    // 返回数据区地址（跳过元数据）
    return (char*)node + sizeof(BlockHeader);
}

// 释放时，通过元数据找到所属池
void FixedBlockAllocator::deallocate(void* ptr) {
    // 从数据区回退到块头部
    BlockHeader* header = (BlockHeader*)((char*)ptr - sizeof(BlockHeader));
    
    // 验证元数据（可选）
    if (header->pool != this) {
        // 错误处理：块不属于当前池
        return;
    }
    
    // 把块插回自由链表
    FreeNode* node = (FreeNode*)header;
    node->next = free_head;
    free_head = node;
}

这里有个细节：块大小必须对齐到 8 字节或 16 字节。否则元数据的位置会错乱。我踩过这个坑——有一次块大小设成了 60 字节，结果元数据覆盖了相邻块的数据，回测结果全错了。排查了两天才找到原因。

3.4 整体结构图

说了这么多，咱们用一张图把整个结构串起来。这张图展示了内存池的核心数据布局：

这张图展示了三个层次：最上层是内存池的控制结构，中间是自由链表，最下层是实际的内存块。每个块头部都带有元数据，空闲块通过自由链表串联。分配时从链表头取块，释放时插回链表头——就这么简单。

3.5 避坑指南与经验总结

最后，我把自己踩过的坑和总结的经验列出来，希望能帮你少走弯路：

问题	现象	解决方案
块大小未对齐	元数据覆盖相邻块，数据损坏	块大小对齐到 8 或 16 字节
自由链表指针被覆盖	分配时返回野指针，程序崩溃	确保数据区不覆盖前 8 字节
多线程并发分配	自由链表被破坏，内存泄漏	加锁或使用线程本地缓存
元数据开销过大	内存利用率低于 70%	使用位图代替块头部元数据

我曾经在一个回测项目中，因为块大小没对齐，导致回测结果时对时错。排查了整整两天，最后发现是结构体成员对齐的问题。从那以后，我每次定义块大小时都会加一句 static_assert 检查对齐。

好了，这一章的内容就到这里。固定大小块分配器、自由链表、元数据管理，这三样东西是内存池的基石。理解透了，后面的高级特性（比如线程本地缓存、批量分配）就水到渠成了。

---

公众号:蓝海资料掘金营，微信deep3321