内存池

　　前几天完善网络模块，把网络IO层接收到的数据转到主逻辑线程，自然用到消息队列+内存池。

　　那会便想实现一个分级内存池，用以适配不同的消息大小，节省内存占用。

　　今天抽空写完、测试，顺带纠出个内存池的手残Bug，爆池复用才会触发，自己的小玩意没严格测试，一直没碰到("▔□▔)

　　加上今天这个，总共有四种内存池了，总结下：

　　1、分页内存池

　　最简单，逻辑清晰，易用：先申请一大块内存，从头指针起始，间隔固定大小跳跃，每次步进得到的新指针存入队列，直至内存块覆盖完毕。

　　队列里存下的，便是每个小页的头指针，供外部使用、回收。队列指针用完，再申请同样的大块内存，按上述方式再次分页。

　　数据结构图如下：

　　2、多级内存池

　　对分页内存池的扩展，实际上是数个不同大小的分页内存池组合，如页大小分别是“32字节、64字节、128字节”的组合。

　　可根据用户需要，从合适的内存池取指针，提高内存使用效率。

　　设计上新增的内容就一个：低级别内存池不够用了，向高级别的索要，迭代至最高级别内存池，仍无可用空间，才会向系统申请新的内存。

　　高级别内存池若有剩余，会将自己一半空间分割成合适大小，丢入低级内存池中。

　　意外的，如若用户所需大小，超过最高级池子的页大小，就直接调系统接口，malloc一块出去；回收时检查大小，free即可。

　　数据结构图如下：

　　3、索引对象池

　　适用于需要随时定位查询的数据集合，最常用的——Npc数据存储，npcId实为内存索引，方便同各个模块的交互。

　　说起索引，自然联系到数组啦。上面两种池子，用的都是队列来存指针，这里用的是数组，索引即数组下标。

　　也有个队列，不过队列里存的是空闲下标。

　　抛出内存块时，将空闲下标一并抛出，并当做对象ID。如此，通过ID便能在数组中快速定位到对象指针。

　　内存耗尽时的扩展方式，通上两个一样，只多了步重建指针数组，像vector翻倍那般，保证其线性结构。

　　数据结构图：

　　这种对象池有个弊端：外界保存了对象ID，但该对象可能已经发生销毁、再利用的过程。

　　比如，某任务保存了npcId，随之该Npc死亡回收，它的内存块又恰巧被新的Npc使用了，任务再通过npcId找到的指针，就不是它以为的那只了。

　　目前没想到好的方法搞定这问题，只能减少触发概率。

　　给对象一个自增ID，创建时连同内存池索引，和并成唯一ID用（封个简单联合体）。如此同个内存索引被两次定位的概率就相当小了。

　　4、动态内存池

　　本质上是个蹩脚的malloc实现，思路跟上面三个截然不同。

　　先介绍下管理节点——很简单的结构体，仅含两个数据：标记所指内存块是否空闲、该内存块大小。

　　申请一块够大的内存，记录头尾指针，插入首个管理节点，大小为整块。

　　在用户所需内存块前插入一个管理节点（实际我们抛给他的内存块就要大那么一点点咯）。

　　从头指针开启，沿管理节点所指大小跳跃，遍历整块内存。

　　若当然迭代到的内存块，空闲且大于用户所需（加管理节点之后的大小），即将前部且给用户，并在余下部分插入管理更新大小。

　　用户归还内存时，只需将管理节点内的空闲标记置true。

　　当遍历整块内存都没有合适大小可用时，触发整合逻辑：合并相邻空闲内存块，得到更大的空闲内存。

　　若仍无合适内存可用，才向系统申请新的内存块。

　　数据结构图如下：

　　这东西里面，可玩的技巧就非常多了。

　　首先，管理节点怎样变小。见过有变态拿指针的前半部存的，因为堆是地址低位向高位生长，前半部都是零 ( ¯ □ ¯ )

　　再者，合并的逻辑，一定要等到某个时刻统一做吗？能不能在归还指针时就合并？

　　还有，用户申请、整合，两地方都用了遍历，好挫有没有，咋加速呐(⊙o⊙)?

　　最后，觉得这个动态内存池，实际项目里用处不大。碎片化、不定大小的内存，现代malloc够高效。而那些会复用的内存，分级池子也能很好的处理。不过作为技术视野的拓展，了解玩玩还是很有好处滴(~￣▽￣~)

源码地址：