CppExplore

一切像雾像雨又像风

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  29 随笔 :: 0 文章 :: 280 评论 :: 0 Trackbacks

作者: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是一个非常不错的小巧的内存池。

posted on 2008-02-19 17:30 cppexplore 阅读(5473) 评论(6)  编辑 收藏 引用

评论

# re: 【原创】系统设计之 内存管理(二) 2008-02-20 07:46 Enoch
这么多人看也不回一个。顶。
期待lz续。  回复  更多评论
  

# re: 【原创】系统设计之 内存管理(二) 2008-02-20 08:43 cppexplore
@Enoch
呵呵,借用一句流行话:您的回帖是我继续的最大动力。
谢谢  回复  更多评论
  

# re: 【原创】系统设计之 内存管理(二) 2008-02-20 12:24 aa
分析的很好,待仔细研究!  回复  更多评论
  

# re: 【原创】系统设计之 内存管理(二) 2008-02-21 08:31 沣竹谦信
牛人,顶一把  回复  更多评论
  

# re: 【原创】系统设计之 内存管理(二)[未登录] 2008-03-03 11:33 vcommon
写的详细,谢谢  回复  更多评论
  

# re: 【原创】技术系列之 内存管理(二) 2009-12-20 20:02 houapple
顶啊!  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理