再参考了《Modern C++ Design》的FixedAllocator的设计,并且优化了一下算法,虽然最坏时间复杂度还是O(N)的,但是在通常情况下,new/delete的使用已经获得了比较好的性能了。
Chunk.h和version1.0的差不多,只是去掉了析构函数,让Chunk直接被FixedAlloctor操作
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_;
};
![](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/None.gif)
#endif
FixedAllocator.h
毕竟工程还是工程,很多极端数据都是很难用到的,这个与用户使用习惯有关,对于常用的使用new的习惯(连续new,连续delete,连续new/delete)该FixedAllocator都有比较好的性能。
#ifndef FIXEDALLOCATOR_H
#define FIXEDALLOCATOR_H
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include "Chunk.h"
#include <vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class FixedAllocator
{
public :
FixedAllocator(size_t blockSize);
~FixedAllocator();
//分配内存
void* allocate();
//回收内存
void deallocate(void* p);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
private :
//每个Chunk所含的Block数
static const int BLOCKS;
//block大小
size_t blockSize_;
//该FixedAllocator所含的Chunks
vector<Chunk> chunks_;
//最后一个被用于分配空间的Chunk
Chunk* lastAllocChunk_;
//最后一个被用于释放空间的Chunk
Chunk* lastDeallocChunk_;
//被使用过的Chunks的数
int numOfUsedChunk_;
//判断p是否属于某个chunk
bool isPtrInChunk(void* p, Chunk* chunk);
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int FixedAllocator::BLOCKS = 255;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
FixedAllocator::FixedAllocator(size_t blockSize)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
: blockSize_(blockSize), lastAllocChunk_(0), lastDeallocChunk_(0), numOfUsedChunk_(0)
{}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
FixedAllocator::~FixedAllocator()
{
vector<Chunk>::iterator it = chunks_.begin();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; it != chunks_.end(); it++)
{
delete[] it->pData_;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void* FixedAllocator::allocate()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (!lastAllocChunk_ || !lastAllocChunk_->blocksAvailable_)
{
//该Chunk不可用,需要搜索新的Chunk,deallocate保证只有vector中的最后一个块为全空
bool noBlock = true;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (numOfUsedChunk_ < chunks_.size())
{
vector<Chunk>::reverse_iterator it = chunks_.rbegin();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; it != chunks_.rend(); it++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (it->blocksAvailable_ > 0)
{
lastAllocChunk_ = &*it;
noBlock = false;
break;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (noBlock)
{
//没有可用Chunk,必须新增一个块
numOfUsedChunk_++;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (chunks_.size()+1 > chunks_.capacity())
{
chunks_.reserve(chunks_.capacity() + 1000);
}
Chunk newChunk;
newChunk.init(blockSize_, BLOCKS);
chunks_.push_back(newChunk);
lastAllocChunk_ = &chunks_.back();
lastDeallocChunk_ = &chunks_.back();
}
}
assert(lastAllocChunk_ != 0);
assert(lastAllocChunk_->blocksAvailable_ > 0);
return lastAllocChunk_->allocate(blockSize_);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline bool FixedAllocator::isPtrInChunk(void* p, Chunk* chunk)
{
return (p >= chunk->pData_) && (p < chunk->pData_ + (blockSize_ * BLOCKS));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void FixedAllocator::deallocate(void* p)
{
vector<Chunk>::iterator pChunkToRelease;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (!isPtrInChunk(p, lastDeallocChunk_))
{
//要释放的空间不在lastDeallocChunk中
//从lastDeallocChunk开始up和down方向查找
vector<Chunk>::iterator up = lastDeallocChunk_+1;
vector<Chunk>::iterator down = lastDeallocChunk_;
vector<Chunk>::iterator begVec = chunks_.begin();
vector<Chunk>::iterator endVec = chunks_.end();
int t = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (down != begVec || up != endVec)
{
t ^= 1;
if (up == endVec) t = 0;
if (down == begVec) t = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (t)
{
//up方向
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (up != endVec)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (isPtrInChunk(p, up))
{
pChunkToRelease = up;
break;
}
up++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
//down方向
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (down != begVec)
{
down--;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (isPtrInChunk(p, down))
{
pChunkToRelease = down;
break;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
pChunkToRelease = lastDeallocChunk_;
}
assert(&*pChunkToRelease != 0);
pChunkToRelease->deallocate(p, blockSize_);
lastDeallocChunk_ = pChunkToRelease;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (pChunkToRelease->blocksAvailable_ == BLOCKS)
{
//该块已经空
numOfUsedChunk_--;
Chunk* it = &chunks_.back();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (it->blocksAvailable_ == BLOCKS)
{
//若vector末尾的chunk已是空块,直接把pChunkToRelease删除
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (it != pChunkToRelease)
{
delete[] pChunkToRelease->pData_;
chunks_.erase(pChunkToRelease);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
//若vector末尾的chunk非空,把pChunkToRelease移到vector末尾
Chunk tmp(*pChunkToRelease);
chunks_.erase(pChunkToRelease);
chunks_.push_back(tmp);
}
lastDeallocChunk_ = &chunks_.front();
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#endif
MemPool.h
比起1.0少了很多代码,这个是当然的,因为很多细节都被封装在FixedAllocator里面,而且还用了STL的vector,代码又减少了许多,但是测试时候发现vector貌似比自己写的list慢了点,估计原因是那个erase在list里面是O(1)但是vector是O(n)的。
#ifndef MEMPOOL_H
#define MEMPOOL_H
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include "FixedAllocator.h"
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class MemPool
{
public :
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
MemPool(size_t blockSize) : blockSize_(blockSize), allocator_(new FixedAllocator(blockSize))
{}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
~MemPool()
{
delete allocator_;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void* alloc(size_t size)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (size != blockSize_)
{
return ::operator new(size);
}
return allocator_->allocate();
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void free(void* p, size_t size)
{
if (!p) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (size != blockSize_)
{
::operator delete(p);
}
allocator_->deallocate(p);
}
private :
FixedAllocator* allocator_;
size_t blockSize_;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#endif
test.cpp
#include <iostream>
#include "FixedAllocator.h"
#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 = 1000000;
![](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()
{
//测试新建1000000个SmallObjet所需要的时间
int i;
clock_t begA, begB, endA, endB;
begB = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0; i<CTIMES; i++)
{
pb[i] = new TestClassB;
}
endB = clock();
printf("Not Used MemPool Time For New = %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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
endA = clock();
printf("Used MemPool Time For New = %d ms\n", endA - begA);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
begB = clock();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=CTIMES-1; i>=0; 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);
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)
![](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)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
测试结果如下:
Not Used MemPool Time For New = 360 ms
Used MemPool Time For New = 156 ms
Not Used MemPool Time For Delete = 531 ms
Used MemPool Time For Delete = 266 ms
Not Used MemPool Time For New/Delete = 906 ms
Used MemPool Time For New/Delete = 344 ms
Press any key to continue
明显比version1.0好很多,接着准备写versiong1.2,希望获得更好的封装,同时优化再优化FixedAllocator的算法。还有推荐大家看《Modern C++ Design》这本书,真的很好。
posted on 2008-04-21 16:15
豪 阅读(3248)
评论(3) 编辑 收藏 引用 所属分类:
C++之梦