内存池(MemPool)技术详解收藏

本文已经迁移到：http://cpp.winxgui.com/cn:dive-into-memory-pool

概述

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

经典的内存池技术

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

{

private:

constintm_nMemBlockSize;

constintm_nItemSize;



struct_FreeNode {

_FreeNodepPrev;BYTE data[m_nItemSize - sizeof(_FreeNode)];

};



struct_MemBlock {

_MemBlockpPrev;

_FreeNode data[m_nMemBlockSize/m_nItemSize];

};



_MemBlockm_pMemBlockHeader;

_FreeNode*m_pFreeNodeHeader;



public:

MemPool(intnItemSize,intnMemBlockSize=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个内存结点刚开始全部是自由的，他们被串成链表。我们看看申请/释放内存过程，就很容易明白这样做的目的。

申请内存过程

代码如下：voidMemPool::malloc()//没有参数

{

if(m_pFreeNodeHeader==NULL)

{

constintnCount=m_nMemBlockSize/m_nItemSize;

_MemBlockpNewBlock=new_MemBlock;

pNewBlock->data[0].pPrev=NULL;

for(inti=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;

returnpFreeNode;

}内存申请过程分为两种情况：
* 在自由内存结点链表（FreeNodeList）非空。

在此情况下，Alloc过程只是从链表中摘下一个结点的过程。


* 否则，意味着需要一个新的内存块(MemBlock)。

这个过程需要将新申请的MemBlock切割成多个Node，并把它们串起来。

MemPool技术的开销主要在这。

释放内存过程

代码如下：voidMemPool::free(voidp)

{

_FreeNodepNode=(_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_nItemSize32，第2次申请时m_nItemSize64，第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编译通不过），并且去除了出错处理。

发表于 @ 2006年11月22日 00:44:00 |评论(17)|举报|收藏

旧一篇:【基础】如何建立第一个winx程序 | 新一篇:垃圾收集机制(Garbage Collection)批判

[查看最新精华文章 请访问博客首页](http://blog.csdn.net/)相关文章

[内存池(MemPool)技术详解](http://blog.csdn.net/Jayky/archive/2006/11/22/1403790.aspx)

[内存池(MemPool)技术详解](http://blog.csdn.net/i_like_cpp/archive/2007/06/28/1670075.aspx)

[C程序单链表面试题详解](http://blog.csdn.net/menuconfig/archive/2007/10/10/1817928.aspx)

[堆内存和栈内存详解（转载）](http://blog.csdn.net/c0ffee1982/archive/2007/11/19/1892632.aspx)

[堆内存和栈内存详解（转载）](http://blog.csdn.net/yusongwhu/archive/2008/12/03/3428247.aspx)

[内存池技术详解](http://blog.csdn.net/xxq123321/archive/2009/04/03/4005817.aspx)

[内存池&经典的内存池技术](http://blog.csdn.net/hairetz/archive/2009/08/28/4490542.aspx)

[链表的创建代码详解](http://blog.csdn.net/liukehua123/archive/2010/03/06/5350168.aspx)

[xushiwei](http://hi.csdn.net/xushiwei) 发表于Wed Nov 22 2006 09:58:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiwei URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


以上代码属于伪代码（struct _FreeNode编译通不过），并且去除了出错处理。另外，代码是写文章的时候敲的，重点在表意，不排除有细节问题（我将尽量避免）。

[Crazyazreal](http://hi.csdn.net/Crazyazreal) 发表于Wed Nov 22 2006 12:33:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:Crazyazreal URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


想请教一吓，这个内存池里没有释放内存的代码，那么随着程序的运行，申请的内存会越来越多，是不是应该在系统空闲时，delete掉空闲链表里的内存？

在网上搜了一吓，用多个内存池来解决，每个内存池对应不同的生存期。除了这个方法还有别的吗？

[xushiwei](http://hi.csdn.net/xushiwei) 发表于Wed Nov 22 2006 12:44:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiwei URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


是的，内存池(MemPool)除了clear操作（上面没有提供）外，没有真正delete内存的过程。sgi-stl更加夸张，连MemPool析构时都不delete，直接程序退出时由操作系统回收。

[xushiwei](http://hi.csdn.net/xushiwei) 发表于Wed Nov 22 2006 12:49:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiwei URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


我曾经写过一个可回收版本，但是实际上并不理想。细究起来，其实我们这种担心纯属多余。



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

[xushiwei](http://hi.csdn.net/xushiwei) 发表于Wed Nov 22 2006 14:20:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiwei URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


不好意思，我的话误导你了：一般的MemPool析构会delete内存的。是sgi-stl的allocator没有这样做。

[kkkk](http://hi.csdn.net/kkkk) 发表于Wed Nov 22 2006 14:07:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:kkkk URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


既然内存池析构时不回收内存,那是不是应该保存一个句柄之类的东西以备将来重新使用,而不是无止尽的向系统要内存吧??如果是这样请问是如何实现的?

[kkkk](http://hi.csdn.net/kkkk) 发表于Wed Nov 22 2006 18:16:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:kkkk URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


我胡思乱想的,这样一个专分配小内存的的内存池,由程序员决定是否分配到这个内存池,使用注册或代理，分配发生异常时进行内存整理，同时作一些改变东西（这个不知道怎么说，反正就是使指针不失效吧），可以吗，不行的话难点在哪？

[肉骨头](http://hi.csdn.net/肉骨头) 发表于Sun Nov 26 2006 23:42:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:肉骨头 URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


与其将内存池当一项技术，不如作为一种内存使用策略。

对不同的需求，使用不同的内存池，采用不同的策略。软件初期使用的策略和后期可能截然不同。离开需求设计泛用型内存池可不是个好主意。

[xushiwei](http://hi.csdn.net/xushiwei) 发表于Sun Nov 26 2006 23:55:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiwei URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


to 肉骨头: 感觉到了你是有感而发，但是恕我愚钝，不太明白你的意思。

[肉骨头](http://hi.csdn.net/肉骨头) 发表于Mon Nov 27 2006 18:53:00 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:肉骨头 URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


to xushiwei：

Sorry，可能有些不太切合本文的题目。看到关于“性能”的讨论时，突然冒出了这些想法。

内存分配后如何使用，什么时候释放，什么时候归还，处于一种基于需求的考虑，所以我比较倾向于将内存池作为策略来看待。

“泛用型内存池”指的是满足大多数需求的内存池实现。这种内存池考虑了大多数应用的共通特性而舍弃特殊性。C++的标准new就是一种泛用型的，只不过它是向操作系统申请。

《Modern C++ Design》有一章专门用来描述了一种小型对象分配器，其实就是一种内存分配策略。标准new针对大块内存的分配做了专门的优化，而对小到几十个字节的对象使用new的话效率太低。为了解决为大量小型（几十个字节）对象分配内存造成的性能问题，书中采用针对小型对象设计的内存池满足了“大量小型对象分配“对效率的需求。

所以，才有了前边的那些发言。SORRY，我的语文水平不高，见谅。:P

[20040216](http://hi.csdn.net/20040216) 发表于Wed Dec 06 2006 09:41:46 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:20040216 URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


我以为作者有什么创新，结果什么都没有，还不如《Modern C++ Design》中设计的，在《Modern C++ Design》的设计上修改一下它的缓存设计和释放chunk的查找机制性能还是不错的 sgi的stl内存管理根本不释放内存，对于某些程序是不可取的 肉骨头说的很对，不同需求用不同的

[xushiweizh](http://hi.csdn.net/xushiweizh) 发表于Wed Dec 06 2006 10:05:46 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiweizh URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


呵呵，我题目介绍的就是经典的内存池，当然不会有什么自己的东西。bosst、sgi-stl是因为与内存池有关，所以一并介绍。我本来不打算写的，通常转一篇，可惜没找到合适的。

[NeutralEvil](http://hi.csdn.net/NeutralEvil) 发表于Fri Jan 19 2007 22:50:27 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:NeutralEvil URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


看到boost::pool的接口，一直没想通ordered_free到底有什么用，特别是object_pool的free还非得强制调ordered_free。许老大怎么不继续写了？

[NeutralEvil](http://hi.csdn.net/NeutralEvil) 发表于Fri Jan 19 2007 22:50:27 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:NeutralEvil URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


看到boost::pool的接口，一直没想通ordered_free到底有什么用，特别是object_pool的free还非得强制调ordered_free。许老大怎么不继续写了？

[xushiweizh](http://hi.csdn.net/xushiweizh) 发表于Sat Jan 20 2007 14:40:54 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:xushiweizh URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


会写的。C++内存管理变革(3)本来已经打算开始介绍object_pool，但是考虑到很多人对AutoFreeAlloc仍有疑虑，故此额外加了一篇。到年关了，大家都很忙，blog更新得不太勤快了。呵呵。

[dmgactive](http://hi.csdn.net/dmgactive) 发表于Wed Dec 19 2007 10:07:34 GMT+0800 (China Standard Time) [举报](mailto:webmaster@csdn.net?subject=Comment Report!!!&body=Author:dmgactive URL:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx)[回复](回复)


你好：nMemBlockSize = 2048这一项2048B?

做一个简单数据库，以块为单位，申请一个8kb的怎么来做

原文链接: https://www.cnblogs.com/blockcipher/archive/2010/09/04/2913017.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍