用了《Modern C++ Design》上的那个Chunk,在Chunk查找Block的时间是O(1),但是在MemPool的ChunkList里面查找某内存地址却需要O(n)的时间复杂度,因为我的算法只是线性的便利ChunkLisk的链表,所以但内存池里面同时存在大量小对象时候,效果不是很好,比普通的new还差,但是如果内存池内同时存在的小对象的数目较小的时候,可以获得不错的性能,计划version2.0要改进算法,但是尝试加Map做O(logn)的查找,效果很不好,常数太大了,如果加hash又耗太多内存,暂时没什么想法,估计要改数据结构了,+个freelist可以实现new操作O(1)但是free操作很难搞,怎样快速定位某个内存属于哪个Chunk呢?有点难度,再看看书,再想想。
Chunk.h
#ifndef CHUNK_H
#define CHUNK_H
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <cassert>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Chunk
{
//初始化一个Chunk
void init(size_t blockSize, unsigned char blocks);
//分配一个block
void* allocate(size_t blockSize);
//回收一个block
void deallocate(void* p, size_t blockSize);
//Chunk的起始地址
unsigned char* pData_;
//第一个可用的block
unsigned char firstAvailableBlock_;
//block的块数
unsigned char blocksAvailable_;
//析构函数释放内存
~Chunk();
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Chunk::init(size_t blockSize, unsigned char blocks)
{
//从操作系统申请一个Chunk的内存
pData_ = new unsigned char[blockSize * blocks];
firstAvailableBlock_ = 0;
blocksAvailable_ = blocks;
unsigned char *p = pData_;
//每个可用的block存放它下一个可用的block的编号
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (unsigned char i = 1; i < blocks; i++, p += blockSize)
{
*p = i;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void* Chunk::allocate(size_t blockSize)
{
if (blocksAvailable_ == 0) return 0;
unsigned char* pRet = pData_ + (firstAvailableBlock_ * blockSize);
//更新第一个可用的block
firstAvailableBlock_ = *pRet;
blocksAvailable_--;
return pRet;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void Chunk::deallocate(void* p, size_t blockSize)
{
//判断回收的地址是否合法
assert(p >= pData_);
unsigned char* toRel = static_cast<unsigned char*>(p);
//判断是否合法
assert((toRel - pData_) % blockSize == 0);
*toRel = firstAvailableBlock_;
firstAvailableBlock_ = static_cast<unsigned char>((toRel - pData_) / blockSize);
//判断是否产生精度误差
assert(firstAvailableBlock_ == ((toRel - pData_) / blockSize));
blocksAvailable_++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
Chunk::~Chunk()
{
delete[] pData_;
}
#endif
MemPool.h
#ifndef MEMPOOL_H
#define MEMPOOL_H
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include "Chunk.h"
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct ChunkList
{
Chunk* valChunk_;
ChunkList* next_;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
ChunkList() : valChunk_(new Chunk), next_(0)
{}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
~ChunkList()
{delete valChunk_;}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class MemPool
{
public :
MemPool(size_t blockSize);
~MemPool();
void* alloc(size_t size);
void free(void* p, size_t size);
private :
//新分配一个Chunk
ChunkList* allocChunk();
//释放一个Chunk
void freeChunk(ChunkList* pChunkList);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//一个Chunk所拥有的Block数
static const int BLOCKS;
//free的Chunk
ChunkList* headOfChunkList_;
size_t blockSize_;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MemPool::BLOCKS = 255;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
MemPool::MemPool(size_t blockSize) : blockSize_(blockSize), headOfChunkList_(0)
{};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
MemPool::~MemPool()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (headOfChunkList_)
{
freeChunk(headOfChunkList_);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void* MemPool::alloc(size_t size)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (size != blockSize_)
{
return ::operator new(size);
}
//查找可用的Block
ChunkList* p = headOfChunkList_;
while (p && !p->valChunk_->blocksAvailable_) p = p->next_;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (!p) p = allocChunk();
void* pRet = p->valChunk_->allocate(blockSize_);
return pRet;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MemPool::free(void* p, size_t size)
{
if (!p) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (size != blockSize_)
{
::operator delete(p);
return ;
}
//查找p所属的Chunk
ChunkList* pTmp = headOfChunkList_;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (pTmp)
{
if (p >= pTmp->valChunk_->pData_ && p < pTmp->valChunk_->pData_ + (blockSize_ * BLOCKS)) break;
pTmp = pTmp->next_;
}
if (!pTmp) return ;
pTmp->valChunk_->deallocate(p, blockSize_);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
ChunkList* MemPool::allocChunk()
{
ChunkList* pTmpChunkList = new ChunkList;
//新建一个Chunk
pTmpChunkList->valChunk_->init(blockSize_, BLOCKS);
//把这个Chunk加入到ChunkList的链表头
pTmpChunkList->next_ = headOfChunkList_;
headOfChunkList_ = pTmpChunkList;
return pTmpChunkList;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void MemPool::freeChunk(ChunkList* pChunkList)
{
//在链表中查找
if (!pChunkList) return ;
ChunkList* p, * q;
p = headOfChunkList_;
q = p->next_;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (p == pChunkList)
{
//在表头
headOfChunkList_ = p->next_;
delete pChunkList;
return ;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (q && q != pChunkList)
{
p = q;
q = q->next_;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (q)
{
//查找成功
p->next_ = q->next_;
delete pChunkList;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#endif
test.cpp
#include <iostream>
#include "MemPool.h"
#include "time.h"
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class TestClassA
{
public :
int a;
static void* operator new(size_t size);
static void operator delete(void *p, size_t size);
static MemPool memPool;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline void* TestClassA::operator new(size_t size)
{
return memPool.alloc(size);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline void TestClassA::operator delete(void* p, size_t size)
{
memPool.free(p, size);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
MemPool TestClassA::memPool(sizeof(TestClassA));
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class TestClassB
{
public :
int b;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int CTIMES = 100000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
TestClassA* pa[CTIMES];
TestClassB* pb[CTIMES];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
//测试新建100000个SmallObjet所需要的时间
int i;
clock_t begB = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
pb[i] = new TestClassB;
}
clock_t endB = clock();
printf("Not Used MemPool Time For New = %d ms\n", endB - begB);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
clock_t begA = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
pa[i] = new TestClassA;
}
clock_t endA = clock();
printf("Used MemPool Time For New = %d ms\n", endA - begA);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
begB = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
delete pb[i];
}
endB = clock();
printf("Not Used MemPool Time For Delete = %d ms\n", endB - begB);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
begA = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
delete pa[i];
}
endA = clock();
printf("Used MemPool Time For Delete = %d ms\n", endA - begA);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
begB = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
pb[i] = new TestClassB;
delete pb[i];
}
endB = clock();
printf("Not Used MemPool Time For New/Delete = %d ms\n", endB - begB);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
begA = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
pa[i] = new TestClassA;
delete pa[i];
}
endA = clock();
printf("Used MemPool Time For New/Delete = %d ms\n", endA - begA);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
运行结果:
Not Used MemPool Time For New = 46 ms
Used MemPool Time For New = 16 ms
Not Used MemPool Time For Delete = 47 ms
Used MemPool Time For Delete = 266 ms
Not Used MemPool Time For New/Delete = 93 ms
Used MemPool Time For New/Delete = 16 ms
Press any key to continue
可以看到明显当内存池有大量小对象同时存在的时候,回收的时间很慢,其余时候效果还是不错的。
posted on 2008-04-20 17:53
豪 阅读(649)
评论(0) 编辑 收藏 引用