http://blog.csdn.net/hairetz/article/details/4490542 2009 网上有一关于内存池的文章,拿来分享一下:
内存池(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; }
释放内存过程
代码如下:
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::poolboost::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./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编译通不过),并且去除了出错处理。
文章出处:http://www./course/3_program/c++/cppsl/200855/113039_2.html
|