CppExplore

作者：CppExplore 地址：http://www.cppblog.com/CppExplore/
2、定长内存池。典型的实现有LOKI、BOOST。特点是为不同类型的数据结构分别创建内存池，需要内存的时候从相应的内存池中申请内存，优点是可以在使用完毕立即把内存归还池中，可以更为细粒度的控制内存块。
    与变长的相比，这种类型的内存池更加通用，另一方面对于大量不同的数据类型环境中，会浪费不少内存。但一般系统主要的数据结构都不会很多，并且都是重复申请释放使用，这种情况下，定长内存池的这点小缺点可以忽略了。
(1)Loki::SmallObject。Andrei Alexandrescu的《Modern C++ Design》第四章节已经进行了详细的描述，尽管和当前的loki版本实现有出入，还是了解Loki::SmallObject的最佳文字讲解，结合最新的loki源码，足够了。这里我再罗唆一下。先举例看下使用：

#include "loki/SmallObj.h"
class Small:public  Loki::SmallObject<>//继承SmallObject即可，所有都使用默认策略
{
public:
 Small(int data):data_(data){}
private:
 int data_;
};
int main()
{
 Small *obj=new Small(8);
 delete obj;
}

使用valgrind执行可以证实new一个obj和多new几次，申请的内存都是4192。可以看出loki在使用层面非常简单。
    loki的内存池分4层,从低向上依次是chunk、FixedAllocator、SmallObjAllocator、SmallObject。
1）chunk：每个chunk管理一定数量（最大255，char型保存）的block，每个chunk中block的申请和释放，时间复杂度都是o(1)，非常快，实现算法非常精巧，boost::pool中也是采用的相同算法。
    这里简单说下这个算法：首次申请一块连续内存，pdata_指向该内存基址，依据block大小，划分成多个连续的block，每个block开头的第一个字节保存该block的顺序号，第一个是1，第二个是2，依次类推。另有一字节变量firstAvailableBlock_存储上次分配出的block序号，开始是0。
    分配block：返回pdata_ +firstAvailableBlock_*blocksize，同时firstAvailableBlock_赋值为该块的序列号。
    回收block：block指针假设为pblock，该块序列号赋值为firstAvailableBlock_，firstAvailableBlock_赋值为（pblock-pdata_ ）/blocksize即可。
2）FixedAllocator：chunk中的block上限是255，不具有通用性，因此封装了一层，称为FixedAllocator，它保存了一个vector<chunk>，消除了单个chunk中block数目的上限限制。
   FixedAllocator中的block申请：FixedAllocator中保存活动的chunk（上次有空闲空间的chunk），申请block的时候如果活动chunk有空闲快，直接申请，否则扫描vector，时间复杂度o(N),同时更新活动chunk。
   FixedAllocator中的回收block：简单想，给定block回收到FixedAllocator，自然要扫描vector，以确认block属于哪个chunk，以便chunk回收。实际实现的时候，Loki针对应用场景进行了优化，一般使用都是批量使用，回收一般和申请顺序相同或者相反，因此FixedAllocator保存上次回收block的chunk指针，每次回收优先匹配这个chunk，匹配不上则以该chunk为中心，向两侧chunk顺序检测。
   FixedAllocator带来的优点：上文提到的消除了block的上限限制。另一方面，可以以chunk为单位，把内存归还给操作系统。实际实现中防止刚释放的内存立即又被申请，是存在两个空闲chunk的时候才回收一个。这个特点，这里暂时归结为优点吧。实际使用中，回收多余内存个人认为是个缺点，意义并不是很大。
   FixedAllocator带来的缺点：很明显，就是申请回收block的时间复杂度。
3）SmallObjAllocator：截至到FixedAllocator层面blocksize都是定长。因此封装一层适用于任意长度的内存申请。SmallObjAllocator保存了一个FixedAllocator的数组pool_，存储拥有不同block长度的FixedAllocator。《Modern C++ Design》中描述该数组下标和存储的FixedAllocator的block长度无直接关系，从SmallObjAllocator申请以及回收block的时候二分查找找到对应的FixedAllocator再调用相应FixedAllocator的申请或者回收。当前最新版本的loki，已经抛弃了这种做法。当前SmallObjAllocator的构造函数有3个参数：chunksize，maxblocksize，alignsize。数组元素个数取maxblocksize除以alignsize的向上取整。每个FixedAllocator中实际的blocksize是（下标＋1）*alignsize。
     SmallObjAllocator中block申请：依据block和alignsize的商直接取到数组pool_下标，使用相应的FixedAllocator申请。
     SmallObjAllocator中回收block：根据block和alignsize的商直接找到相应的FixedAllocator回收。
     优点：差异化各种长度的对象申请，增强了易用性。
     缺点：《Modern C++ Design》中描述增加扫描的时间复杂度，当前版本的loki浪费内存。这也是进一步封装，屏蔽定长申请的细节，带来的负面效应。
4）SmallObject。暴露给外部使用的一层。该层面秉承了《Modern C++ Design》开始引入的以设计策略类为最终目的，让用户在编译期选择设计策略，而不是提供框架限制用户的设计。这也是引入模版的一个层面。当前版本SmallObject有6个模版参数，第一个是线程策略，紧接着的三个正好是SmallObjAllocator层面的三个构造参数，下面的一个生存期策略，最后的是锁方式。
    这里说下SmallObjAllocator层面的三个默认参数值，分别是4096，256，4。意味着SmallObjAllocator层面有数组（256+4-1)/4=64个，数组存储的FixedAllocator中的chunksize一般都是4096（当4096<=blocksize*255时候）字节（第一个chunk的申请推迟到首次使用的时候），各FixedAllocator中的chunk的blocksize依次是4、8......256，大于256字节的内存申请交给系统的malooc/new管理，数组中FixedAllocator中单个chunk中的blocknum依次是4096/4=824>255取255、255......4096/256=16。如果这不能满足需求，请调用的时候显式赋值。
    当前loki提供了三种线程策略：

SingleThreaded	单线程
ObjectLevelLockable	对象级别，一个对象一个锁
ClassLevelLockable	类级别，一个类一个锁，该类的所有对象共用该锁

目前只提供了一种锁机制：Mutex
它的基类SmallObjectBase复写了new/delete操作子，因此直接继承SmallObject就可以象普通的类一样new/delete，并且从内存池分配内存。
    SmalObject中block申请和释放都从一个全局的SmallObjAllocator单例进行。
评价：chunk层面限制了上限个数，导致了FixedAllocator层面出现，造成申请回收时间复杂度的提高，而以chunk为单位回收内存，在内存池的使用场景下意义并不是很大。SmallObjAllocator为了差异化变长内存的申请，对FixedAllocator进一步封装，引入了内存的浪费，不如去掉这个层面，直接提供给用户层面定长的接口。另一方面，loki已经进行了不少优化，尽可能让block申请释放的时间复杂度在绝大多数情况下都是O(1),而SmallObjAllocator中内存的浪费可以根据alignsize调整，即便是极端情况下，loki将chunk归还给系统又被申请出来，根据chunk中block的最大值看，也比不使用内存池的情况动态申请释放内存的次数减少了1/255。因此，loki是一个非常不错的小巧的内存池。