使用boost::object_pool<RatinalClassTest>来创建对象（见上一篇文章），速度慢了好几个数量级，看了看pool的代码，能知道一些细节了。
先看看boost pool文档中的描述：
An ordered pool maintains it's free list in order of the address of each free block - this is the most efficient way if you're likely to allocate arrays of objects. However, freeing an object can be O(N) in the number of currently free blocks which can be prohibitively expensive in some situations.
An unordered pool does not maintain it's free list in any particular order, as a result allocation and freeing single objects is very fast, but allocating arrays may be slow (and in particular the pool may not be aware that it contains enough free memory for the allocation request, and unnecessarily allocate more memory).
原因就是object_pool内部使用了ordered pool来分配内存，而这个释放过程的复杂度有可能是O(N)，这对于频繁申请释放内存来说太耗时了！
下面详细讲讲pool的实现(基于boost_1_48_0版本)。基本上所有的内存池思想都是类似的，这里的pool实现的是定长的内存池，更简单一些。
首先pool申请一大段内存（block），然后划分成多个chunk，chunks之间使用list串起来。如果当前block中的chunks使用完毕了，会新申请block，重复前面一样的过程。申请的多个blocks之间也是使用list串起来的。
再看pool 构造函数：
1 explicit pool(const size_type nrequested_size,
2 const size_type nnext_size = 32,
3 const size_type nmax_size = 0)
第一个参数是申请chunk的大小，第二个参数首次申请chunk的个数，下次申请数量翻倍，第三个参数一个block中最多的chunk数目，第二个参数不能大于它，如果为0，就没有限制了。
其中pool还有个很重要的成员
details::PODptr<size_type> list; 就是上面讲的block list。pool析构时候遍历此list释放所有申请的内存（或者手动释放空闲内存）。
block和chunks之间的关系图
block在划分成chunk时候，每个chunk块开头都存放了下一个chunk块的地址，分配内存很简单，直接取一块chunk即可。在申请block块计算内存大小的时候，考虑到了另外两个数据结构next_list,next_size，放在block数据块的末尾位置，多个blocks之间通过next_list指针串联起来，这里就不画图了。
再来看一个很重要的指针：simple_segregated_storage类成员变量first。如果没有分配内存，或者block中的chunk用完了，那么first指针为0，如果有空闲内存，first指针指向block中的某一块chunk。
分配内存函数
malloc
ordered_malloc
如果存在free chunks，那么逻辑很简单,分配first指针指向的内存，然后将first指向next即可。如果不存在free chunks，那么就新申请一个block，再将block放入 pool::list 的头部即可。ordered_malloc 逻辑稍微复杂一些，需要比较block内存地址排序放入到pool::list中。分配内存函数两者的时间复杂度基本相同O(1)。
释放函数
free
ordered_free
对于unordered非常简单，直接放入到first链表的头部，时间复杂度是O(1)。但是ordered_free需要找到正确的位置插入到list，就有可能要遍历所有的free chunks，最坏时间复杂度是O(n)。
总结：
1. boost pool内存组织结构精简，非常节省内存，几乎没有内存浪费。
2. unodered pool内存申请释放效率都非常高，适合用来申请单个内存，不适合用来申请数组。
3. ordered pool内存申请效率高，但是释放非常差，object_pool也使用了ordered pool，严重不推荐使用。
posted on 2014-06-18 13:01
pizzx 阅读(5272)
评论(0) 编辑 收藏 引用 所属分类:
c++/boost