作者:许式伟<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
来源:http://blog.csdn.net/xushiweizh/archive/2006/11/22/1402967.aspx
内存池(MemPool)技术备受推崇。我用google搜索了下,没有找到比较详细的原理性的文章,故此补充一个。另外,补充了boost::pool组件与经典MemPool的差异。同时也描述了MemPool在sgi-stl/stlport中的运用。
经典的内存池(MemPool)技术,是一种用于分配大量大小相同的小对象的技术。通过该技术可以极大加快内存分配/释放过程。下面我们详细解释其中的奥妙。
经典的内存池只涉及两个常量:MemBlockSize、ItemSize(小对象的大小,但不能小于指针的大小,在32位平台也就是不能小于4字节),以及两个指针变量MemBlockHeader、FreeNodeHeader。开始,这两个指针均为空。
-
classMemPool
- {
-
private:
-
constintm_nMemBlockSize;
-
constintm_nItemSize;
-
struct_FreeNode{
- _FreeNode*pPrev;
-
BYTEdata[m_nItemSize-sizeof(_FreeNode*)];
- };
-
struct_MemBlock{
- _MemBlock*pPrev;
- _FreeNodedata[m_nMemBlockSize/m_nItemSize];
- };
- _MemBlock*m_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个内存结点刚开始全部是自由的,他们被串成链表。我们看看申请/释放内存过程,就很容易明白这样做的目的。
申请内存过程
代码如下:
-
void*MemPool::malloc()
- {
-
if(m_pFreeNodeHeader==NULL)
- {
-
constintnCount=m_nMemBlockSize/m_nItemSize;
-
_MemBlock*pNewBlock=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(void*p)
- {
- _FreeNode*pNode=(_FreeNode*)p;
- pNode->pPrev=m_pFreeNodeHeader;
- m_pFreeNodeHeader=pNode;
- }
释放过程极其简单,只是把要释放的结点挂到自由内存链表(FreeNodeList)的开头即可。
性能分析
MemPool技术申请内存/释放内存均极其快(比AutoFreeAlloc慢)。其内存分配过程多数情况下复杂度为O(1),主要开销在FreeNodeList为空需要生成新的MemBlock时。内存释放过程复杂度为O(1)。
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编译通不过),并且去除了出错处理。
分享到:
相关推荐
dpdk内存池mempool的源码实现
按照STL空间配置器的思想实现的一个内存池模块,附带了几个简单测试示例。
是一个windows内存池的源码。基于模板实现,支持多线程操作。
内存池 使用 C++11 的简单内存池实现。 与 Visual Studio 2015、g++4.8 和 clang++3.4 兼容。 一个使用和文档的例子即将到来。
目录记忆池此仅标头的C ++ 17库提供了一种简单的一致的无锁的单个类型元素的内存池的实现。 元素类型作为第一个模板参数传递。细节界面 template < typename xss=removed xss=removed> >class MemoryPool final{...
C语言版简单内存池的实现。 X Memo Pool A memory pool implemented by C. Usage Create Pool At first you should create a pool handler for your data (or structure). xmem_pool_handler xmem_create_pool...
JavaScript真正的内存池解决方案。 mempool.js是强大的解决方案,可用于JavaScript应用程序中的可重用内存管理。 安装 $ npm install mempool.js 构建和测试脚本 $ cd build $ node build.js all $ cd ../test $ ...
这是一个Linux SLAB内存池的简化版,不考虑平台相关性,也没有复杂的数据结构组织,代码简短精炼,程序执行效率高,易于维护。
####m_mempool 基于 nginx(1.8.0) 的内存池
这是一个自己用的内存池初步版本,后续完善后会更新
内存池管理系统,有全部的代码和一个小型程序
#Memory Pool 库使用 EXP-430FR5969(TI Launchpad 板)开发。... 提供具有多种块大小的低开销内存池功能。 如果较小块的池为空,则自动选择较大的块。 去做 添加对内存块的多重引用的支持。 添加简单的诊断支持
编译通过,思路非常好的内存池。可以分配任意内存的字节数,链表实现。有时间可以看一下。
文档: : 特征地址 获取地址Txs Utxo 积木取得封锁获取阻止状态获取块发送获取块Txid 获取块Txid 获取块原始获取块高度获取块获取块提示高度获取块提示哈希费用推荐费用获取费用Mempool块Mempool 获取内存池获取...
见本人博客--单链表、内存池应用-消息抑制表的应用,分析工程下载 用链式队列+内存池,实现消息抑制表的功能
该压缩包中从linux内核提取的mempool实现、从mysql提取的以及从nginx提取的各自的内存池实现。 其中,添加了自己的测试程序。
MemPool。 操作系统支持: Windows
mempool 是一个用 C 语言编写的用于管理内存分配的库。 对于频繁的内存分配,它可以用作 malloc 和 free 的替代品。 内存池在初始时间分配内存块,并使用预定义的内存块大小。
STM32 内存管理分析源码实验。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
内存池 用于 API的R包 内存池功能 Recommendation_fees recommended_fees() -返回当前建议费用水平的数据框。 projected_blocks() -以投影块的形式返回当前内存池。 unconfirmed_transactions_txids() -返回内存池...