加载中…
个人资料
南冠彤
南冠彤
  • 博客等级:
  • 博客积分:0
  • 博客访问:414,747
  • 关注人气:59
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

内存池(MemPool)技术详解

(2011-05-27 18:06:27)
标签:

杂谈

分类: CPP/C

内存池(MemPool)技术备受推崇。我用google搜索了下,没有找到比较详细的原理性的文章,故此补充一个。另外,补充了boost::pool组件与经典MemPool的差异。同时也描述了MemPool在sgi-stl/stlport中的运用。

经典的内存池技术
 
 
经典的内存池(MemPool)技术,是一种用于分配大量大小相同的小对象的技术。通过该技术可以极大加快内存分配/释放过程。下面我们详细解释其中的奥妙。
 
经典的内存池只涉及两个常量:MemBlockSize、ItemSize(小对象的大小,但不能小于指针的大小,在32位平台也就是不能小于4字节),以及两个指针变量MemBlockHeader、FreeNodeHeader。开始,这两个指针均为空。
 
class MemPool
{
private:
    const int m_nMemBlockSize;
    const int m_nItemSize;

    struct _FreeNode {
        _FreeNode* pPrev;
        BYTE data[m_nItemSize - sizeof(_FreeNode*)];
    };

    struct _MemBlock {
        _MemBlock* pPrev;
        _FreeNode data[m_nMemBlockSize/m_nItemSize];
    };
 
    _MemBlock* m_pMemBlockHeader;
    _FreeNode* m_pFreeNodeHeader;
 
public:
   MemPool(int nItemSize, int nMemBlockSize = 2048)
       : m_nItemSize(nItemSize), m_nMemBlockSize(nMemBlockSize),
         m_pMemBlockHeader(NULL), m_pFreeNodeHeader(NULL)
   {
   }
};
 
 
其中指针变量MemBlockHeader是把所有申请的内存块(MemBlock)串成一个链表,以便通过它可以释放所有申请的内存。FreeNodeHeader变量则是把所有自由内存结点(FreeNode)串成一个链。
 
这段话涉及两个关键概念:内存块(MemBlock)和自由内存结点(FreeNode)。内存块大小一般固定为MemBlockSize字节(除去用以建立链表的指针外)。内存块在申请之初就被划分为多个内存结点(Node),每个Node大小为ItemSize(小对象的大小),计MemBlockSize/ItemSize个。这MemBlockSize/ItemSize个内存结点刚开始全部是自由的,他们被串成链表。我们看看申请/释放内存过程,就很容易明白这样做的目的。
 
申请内存过程
代码如下:
 
void* MemPool::malloc()    // 没有参数
{
    if (m_pFreeNodeHeader == NULL)
    {
       const int nCount = m_nMemBlockSize/m_nItemSize;
        _MemBlock* pNewBlock = new _MemBlock;
        pNewBlock->data[0].pPrev = NULL;
        for (int i = 1; i < nCount; ++i)
            pNewBlock->data[i].pPrev = &pNewBlock->data[i-1];
        m_pFreeNodeHeader = &pNewBlock->data[nCount-1];
        pNewBlock->pPrev = m_pMemBlock;
        m_pMemBlock = pNewBlock;
    }
    void* pFreeNode = m_pFreeNodeHeader;
    m_pFreeNodeHeader = m_pFreeNodeHeader->pPrev;
    return pFreeNode;
}
 
内存申请过程分为两种情况:
在自由内存结点链表(FreeNodeList)非空。
在此情况下,Alloc过程只是从链表中摘下一个结点的过程。
 
否则,意味着需要一个新的内存块(MemBlock)。
这个过程需要将新申请的MemBlock切割成多个Node,并把它们串起来。
MemPool技术的开销主要在这。
 
释放内存过程
 代码如下:
void MemPool::free(void* p)
{
    _FreeNode* pNode = (_FreeNode*)p;
    pNode->pPrev = m_pFreeNodeHeader;
    m_pFreeNodeHeader = pNode;
}
释放过程极其简单,只是把要释放的结点挂到自由内存链表(FreeNodeList)的开头即可。
 
 
 
性能分析
MemPool技术申请内存/释放内存均极其快(比AutoFreeAlloc慢)。其内存分配过程多数情况下复杂度为O(1),主要开销在FreeNodeList为空需要生成新的MemBlock时。内存释放过程复杂度为O(1)。
 
 
 
 
boost::pool
boost::pool是内存池技术的变种。主要的变化如下:

MemBlock改为非固定长度(MemBlockSize),而是:第1次申请时m_nItemSize*32,第2次申请时m_nItemSize*64,第3次申请时m_nItemSize*128,以此类推。不采用固定的MemBlockSize,而采用这种做法预测模型(是的,这是一种用户内存需求的预测模型,其实std::vector的内存增长亦采用了该模型),是一个细节上的改良。
 
增加了ordered_free(void* p) 函数。

ordered_free区别于free的是,free把要释放的结点挂到自由内存链表(FreeNodeList)的开头,ordered_free则假设FreeNodeList是有序的,因此会遍历FreeNodeList把要释放的结点插入到合适的位置。

我们已经看到,free的复杂度是O(1),非常快。但请注意ordered_free是比较费的操作,其复杂度是O(N)。这里N是FreeNodeList的大小。对于一个频繁释放/申请的系统,这个N很可能是个大数。这个boost描述得很清楚:http://www.boost.org/libs/pool/doc/interfaces/pool.html
注意:不要认为boost提供ordered_free是多此一举。后文我们会在讨论boost::object_pool时解释这一点。

 
基于内存池技术的通用内存分配组件
 
sgi-stl把内存池(MemPool)技术进行发扬光大,用它来实现其最根本的allocator。
 
 
其大体的思想是,建立16个MemPool,<=8字节的内存申请由0号MemPool分配,<=16字节的内存申请由1号MemPool分配,<=24字节的内存有2号MemPool分配,以此类推。最后,>128字节的内存申请由普通的malloc分配。

 

注意


以上代码属于伪代码(struct _FreeNode、_MemBlock编译通不过),并且去除了出错处理。

 

 

Crazyazreal 发表于2006年11月22日 12:33:00  IP:举报回复删除
想请教一吓,这个内存池里没有释放内存的代码,那么随着程序的运行,申请的内存会越来越多,是不是应该在系统空闲时,delete掉空闲链表里的内存?
在网上搜了一吓,用多个内存池来解决,每个内存池对应不同的生存期。除了这个方法还有别的吗?

 

xushiwei 发表于2006年11月22日 12:44:00  IP:举报回复删除
是的,内存池(MemPool)除了clear操作(上面没有提供)外,没有真正delete内存的过程。sgi-stl更加夸张,连MemPool析构时都不delete,直接程序退出时由操作系统回收。

 

xushiwei 发表于2006年11月22日 12:49:00  IP:举报回复删除
我曾经写过一个可回收版本,但是实际上并不理想。细究起来,其实我们这种担心纯属多余。

你想,如果程序某个时刻到达了一个内存使用高峰,那么意味着它接下来很有可能有另一个高峰,如果我们辛辛苦苦把内存回收了,马上有要重新申请,其实不值得。细究boost::pool的实现,它采用了非固定长度的MemBlock,来预测的用户内存需求,其实是同样的道理。

 

xushiwei 发表于2006年11月22日 14:20:00  IP:举报回复删除
不好意思,我的话误导你了:一般的MemPool析构会delete内存的。是sgi-stl的allocator没有这样做。

 

kkkk 发表于2006年11月22日 14:07:00  IP:举报回复删除
既然内存池析构时不回收内存,那是不是应该保存一个句柄之类的东西以备将来重新使用,而不是无止尽的向系统要内存吧??如果是这样请问是如何实现的?kkkk  发表于2006年11月22日 18:16:00  IP:举报回复删除
我胡思乱想的,这样一个专分配小内存的的内存池,由程序员决定是否分配到这个内存池,使用注册或代理,分配发生异常时进行内存整理,同时作一些改变东西(这个不知道怎么说,反正就是使指针不失效吧),可以吗,不行的话难点在哪?

 

肉骨头 发表于2006年11月26日 23:42:00  IP:举报回复删除
与其将内存池当一项技术,不如作为一种内存使用策略。
对不同的需求,使用不同的内存池,采用不同的策略。软件初期使用的策略和后期可能截然不同。离开需求设计泛用型内存池可不是个好主意。

 

xushiwei 发表于2006年11月26日 23:55:00  IP:举报回复删除
to 肉骨头: 感觉到了你是有感而发,但是恕我愚钝,不太明白你的意思。

 

肉骨头 发表于2006年11月27日 18:53:00  IP:举报回复删除
to xushiwei:
Sorry,可能有些不太切合本文的题目。看到关于“性能”的讨论时,突然冒出了这些想法。
内存分配后如何使用,什么时候释放,什么时候归还,处于一种基于需求的考虑,所以我比较倾向于将内存池作为策略来看待。
“泛用型内存池”指的是满足大多数需求的内存池实现。这种内存池考虑了大多数应用的共通特性而舍弃特殊性。C++的标准new就是一种泛用型的,只不过它是向操作系统申请。
《Modern C++ Design》有一章专门用来描述了一种小型对象分配器,其实就是一种内存分配策略。标准new针对大块内存的分配做了专门的优化,而对小到几十个字节的对象使用new的话效率太低。为了解决为大量小型(几十个字节)对象分配内存造成的性能问题,书中采用针对小型对象设计的内存池满足了“大量小型对象分配“对效率的需求。
所以,才有了前边的那些发言。SORRY,我的语文水平不高,见谅。:

 

P20040216 发表于2006年12月6日 9:41:46  IP:举报回复删除
我以为作者有什么创新,结果什么都没有,还不如《Modern C++ Design》中设计的,在《Modern C++ Design》的设计上修改一下它的缓存设计和释放chunk的查找机制性能还是不错的 sgi的stl内存管理根本不释放内存,对于某些程序是不可取的 肉骨头说的很对,不同需求用不同的

 

xushiweizh 发表于2006年12月6日 10:05:46  IP:举报回复删除
呵呵,我题目介绍的就是经典的内存池,当然不会有什么自己的东西。bosst、sgi-stl是因为与内存池有关,所以一并介绍。我本来不打算写的,通常转一篇,可惜没找到合适的。

 

NeutralEvil 发表于2007年1月19日 22:50:27  IP:举报回复删除
看到boost::pool的接口,一直没想通ordered_free到底有什么用,特别是object_pool的free还非得强制调ordered_free。许老大怎么不继续写了?

 

NeutralEvil 发表于2007年1月19日 22:50:27  IP:举报回复删除
看到boost::pool的接口,一直没想通ordered_free到底有什么用,特别是object_pool的free还非得强制调ordered_free。许老大怎么不继续写了?

 

xushiweizh 发表于2007年1月20日 14:40:54  IP:举报回复删除
会写的。C++内存管理变革(3)本来已经打算开始介绍object_pool,但是考虑到很多人对AutoFreeAlloc仍有疑虑,故此额外加了一篇。到年关了,大家都很忙,blog更新得不太勤快了。呵呵。

 

dmgactive 发表于2007年12月19日 10:07:34  IP:举报回复删除
你好:nMemBlockSize = 2048这一项2048B?
做一个简单数据库,以块为单位,申请一个8kb的怎么来做

 


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有