C++ 内存池什么的 - 某Z的博客

最近因为某些原因鼓捣了好久内存池, 姑且记录一下

之前对内存池的了解只停留在表面, 咋看一下好像没啥, 做起来各种头疼, 总结一下大概有几种实现方式:

只分配, 不释放, 而是在内存池销毁时全部释放, 元素定长或不定长均可

这种最简单了, rapidxml 中用的类似方法, 适合于有明确作用域的情形, 而且通常仅适用于 POD 类型,
因为不需要保存额外信息, 所以效率非常好 (当然局限性也很大)
定长 POD 内存池

这种也比较简单, 由于 POD 类型所以没有指针的多态变化, 地址查找算法也比较简单高效, 找到所属 buffer, 除法算出内存块索引即可
不定长 POD 或对象内存池

这个就很复杂了, 主要问题在于 poolDelete 时如何高效率的查找到所属的内存块, 具体实现方式还没深究, 大体都是用双向链表

扯皮完了目前了解到的皮毛, 尝试着自己实现了一份, 大概设计思路:

内存池维护一个 "已分配" 和 "未分配" 的 buffer 队列
buffer 本身不定长, 分别包含 32, 64, 128, 256, … 字节的内存块序列, 序列中使用双向链表保存数据
每个对象占用一个内存块
创建对象时直接 malloc (内存块大小 + 头信息 * 2) (乘2 用于内存对齐, 下文提到), 然后链接到 "已分配" 列表中
销毁对象时, 使用特殊的查找算法 (下文提到) 找到所属内存块, 删除对象后将该内存块缓存回 "未分配" 中

数据结构:

class ObjectData {
    byte *basePtr; // malloc 得到的内存
    byte *objectPtr; // 扣除 header 以及内存对齐后的对象地址
    ObjectTypeEnum objectType; // POD 或者 Object 等类型
    int headerVerify; // 关键的校验位, 下文提到
    ObjectDeleteCallback objectDeleteCallback; // Object 需要销毁回调
    ObjectData *prevData; // 双向链表
    ObjectData *nextData;
};
class MemPool {
    // 分别包含 32, 64, 128, 256, ... 字节的内存块,
    // 比如 used[0] 保存大小不超过 32 字节的对象, 等等
    ObjectData used[BLOCK_COUNT];
    ObjectData unused[BLOCK_COUNT];
};

其他没啥好说的, 简单的双向链表插入和删除等等, 最关键的问题在于, 给一个 void * 指针, 如何找到所属的内存块

解释做法之前, 先说明下这点的蛋疼之处, 先看看代码:

    ChildType *child = new ChildType();
    BaseType *base = child;

大家都很熟的 C++ 多态, 不过似乎很少人注意过 base 指针到底做了啥事, 以 %p 或者 %08X 打印一下指针就知道了,
base 指针相对于 child 会有一定的偏移量, 具体原因扯到 C++ 内存布局相关的, 就不解释了

当这一机制挪到内存池中, 杯具就来了, 比如, 当这个偏移量大于你的内存块单位大小时, 你的任何高效的寻址算法就歇菜了,
当然你可以额外添加很多头信息或处理方式来解决这一问题, 但是, 效率又下去了

好了, 现在来说明下脑洞大开的实现方式, 玄妙在于 malloc 时的内存对齐以及用作校验的 headerVerify:

通常内存池中内存块的内存布局为 (头信息 + 对象内存), 但这里新增一条要求, 即头信息的起始地址必须与 sizeof(ObjectData) 对齐

大体算法是: (为清晰明了, 部分强制转换代码未写)
```
byte *basePtr = malloc(sizeof(ObjectData) * 2 + object_size);
ObjectData *objectData = basePtr + sizeof(ObjectData) - (basePtr % sizeof(ObjectData));
```

有了上述保证, 给定一个指针, 即可快速找到所属内存块:

byte *checkingPtr = p - (p % sizeof(ObjectData));
while(!isObjectDataValid(checkingPtr)) {
    checkingPtr -= sizeof(ObjectData);
}

怎样判断 checkingPtr 是否是要找的内存块呢? 这时就要用到之前提到的 headerVerify 来校验这段内存是否是有效的内存块头信息了

这个做法就很多了, 为了效率, 将 basePtr, objectPtr 等与内存地址有关且不会变动的内容,
用与运算和或运算做校验, 理论上不容易出现冲突的情况

差不多就这么回事, 比起传统意义上的内存池, 倒是更像 cache 或对象池

简单测试性能提升大约只有 1.5 倍左右, 极端情况下可能比不用内存池性能还差 2 倍左右 (比如一直创建不销毁)

总结一下:

优点什么的就是使用灵活, 任意类型任意长度通吃且不用担心对象析构的问题, 做些小技巧甚至能支持 protected/private 构造函数的对象
缺点什么的也蛮多: 内存浪费略严重 (每个内存块要额外占用 (头信息*2) 字节的大小), 对内存碎片也没啥太大帮助,
而且当 delete 一个无效指针的时候, 可能因为头信息校验过程中的非法内存访问而直接造成死机, 连输出警告的机会都没有
总的来说, 个人还是建议使用定长/固定类型的内存池, 没有必要去弄这么复杂的不定长/不定类型的内存池, 复杂度太高, 性能提升却并不明显

转载请注明来自: http://zsaber.com/blog/p/52

既然都来了, 有啥想法顺便留个言呗? (无奈小广告太多, 需审核, 见谅)

发表回复 取消回复

发表回复取消回复