再参考了《Modern C++ Design》的FixedAllocator的设计,并且优化了一下算法,虽然最坏时间复杂度还是O(N)的,但是在通常情况下,new/delete的使用已经获得了比较好的性能了。
Chunk.h和version1.0的差不多,只是去掉了析构函数,让Chunk直接被FixedAlloctor操作
Chunk.h
#ifndef CHUNK_H
#define CHUNK_H

#include <cassert>


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_;
};


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的编号

for (unsigned char i = 1; i < blocks; i++, p += blockSize)
{
*p = i;
}
}


void* Chunk::allocate(size_t blockSize)
{
if (blocksAvailable_ == 0) return 0;
unsigned char* pRet = pData_ + (firstAvailableBlock_ * blockSize);
//更新第一个可用的block
firstAvailableBlock_ = *pRet;
blocksAvailable_--;
return pRet;
}


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_++;
}


#endif
FixedAllocator.h
毕竟工程还是工程,很多极端数据都是很难用到的,这个与用户使用习惯有关,对于常用的使用new的习惯(连续new,连续delete,连续new/delete)该FixedAllocator都有比较好的性能。
#ifndef FIXEDALLOCATOR_H
#define FIXEDALLOCATOR_H

#include "Chunk.h"
#include <vector>
using namespace std;


class FixedAllocator
{
public :
FixedAllocator(size_t blockSize);
~FixedAllocator();
//分配内存
void* allocate();
//回收内存
void deallocate(void* p);

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);
};

const int FixedAllocator::BLOCKS = 255;

FixedAllocator::FixedAllocator(size_t blockSize)

: blockSize_(blockSize), lastAllocChunk_(0), lastDeallocChunk_(0), numOfUsedChunk_(0)
{}


FixedAllocator::~FixedAllocator()
{
vector<Chunk>::iterator it = chunks_.begin();

for (; it != chunks_.end(); it++)
{
delete[] it->pData_;
}
}


void* FixedAllocator::allocate()
{

if (!lastAllocChunk_ || !lastAllocChunk_->blocksAvailable_)
{
//该Chunk不可用,需要搜索新的Chunk,deallocate保证只有vector中的最后一个块为全空
bool noBlock = true;

if (numOfUsedChunk_ < chunks_.size())
{
vector<Chunk>::reverse_iterator it = chunks_.rbegin();

for (; it != chunks_.rend(); it++)
{

if (it->blocksAvailable_ > 0)
{
lastAllocChunk_ = &*it;
noBlock = false;
break;
}
}
}

if (noBlock)
{
//没有可用Chunk,必须新增一个块
numOfUsedChunk_++;

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_);
}


inline bool FixedAllocator::isPtrInChunk(void* p, Chunk* chunk)
{
return (p >= chunk->pData_) && (p < chunk->pData_ + (blockSize_ * BLOCKS));
}


void FixedAllocator::deallocate(void* p)
{
vector<Chunk>::iterator pChunkToRelease;

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;

while (down != begVec || up != endVec)
{
t ^= 1;
if (up == endVec) t = 0;
if (down == begVec) t = 1;

if (t)
{
//up方向

if (up != endVec)
{

if (isPtrInChunk(p, up))
{
pChunkToRelease = up;
break;
}
up++;
}

} else
{
//down方向

if (down != begVec)
{
down--;

if (isPtrInChunk(p, down))
{
pChunkToRelease = down;
break;
}
}
}
}

} else
{
pChunkToRelease = lastDeallocChunk_;
}
assert(&*pChunkToRelease != 0);
pChunkToRelease->deallocate(p, blockSize_);
lastDeallocChunk_ = pChunkToRelease;


if (pChunkToRelease->blocksAvailable_ == BLOCKS)
{
//该块已经空
numOfUsedChunk_--;
Chunk* it = &chunks_.back();

if (it->blocksAvailable_ == BLOCKS)
{
//若vector末尾的chunk已是空块,直接把pChunkToRelease删除

if (it != pChunkToRelease)
{
delete[] pChunkToRelease->pData_;
chunks_.erase(pChunkToRelease);
}

} else
{
//若vector末尾的chunk非空,把pChunkToRelease移到vector末尾
Chunk tmp(*pChunkToRelease);
chunks_.erase(pChunkToRelease);
chunks_.push_back(tmp);
}
lastDeallocChunk_ = &chunks_.front();
}
}

#endif
MemPool.h
比起1.0少了很多代码,这个是当然的,因为很多细节都被封装在FixedAllocator里面,而且还用了STL的vector,代码又减少了许多,但是测试时候发现vector貌似比自己写的list慢了点,估计原因是那个erase在list里面是O(1)但是vector是O(n)的。
#ifndef MEMPOOL_H
#define MEMPOOL_H

#include "FixedAllocator.h"


class MemPool
{
public :

MemPool(size_t blockSize) : blockSize_(blockSize), allocator_(new FixedAllocator(blockSize))
{}

~MemPool()
{
delete allocator_;
}

void* alloc(size_t size)
{

if (size != blockSize_)
{
return ::operator new(size);
}
return allocator_->allocate();
}

void free(void* p, size_t size)
{
if (!p) return ;

if (size != blockSize_)
{
::operator delete(p);
}
allocator_->deallocate(p);
}
private :
FixedAllocator* allocator_;
size_t blockSize_;
};


#endif
test.cpp
#include <iostream>
#include "FixedAllocator.h"
#include "MemPool.h"
#include "time.h"
using namespace std;


class TestClassA
{
public :
int a;
static void* operator new(size_t size);
static void operator delete(void *p, size_t size);
static MemPool memPool;
};


inline void* TestClassA::operator new(size_t size)
{
return memPool.alloc(size);
}


inline void TestClassA::operator delete(void* p, size_t size)
{
memPool.free(p, size);
}

MemPool TestClassA::memPool(sizeof(TestClassA));


class TestClassB
{
public :
int b;
};

const int CTIMES = 1000000;

TestClassA* pa[CTIMES];
TestClassB* pb[CTIMES];


int main()
{
//测试新建1000000个SmallObjet所需要的时间
int i;
clock_t begA, begB, endA, endB;
begB = clock();

for (i=0; i<CTIMES; i++)
{
pb[i] = new TestClassB;
}
endB = clock();
printf("Not Used MemPool Time For New = %d ms\n", endB - begB);

begA = clock();

for (i=0; i<CTIMES; i++)
{
pa[i] = new TestClassA;
}

endA = clock();
printf("Used MemPool Time For New = %d ms\n", endA - begA);


begB = clock();

for (i=CTIMES-1; i>=0; i--)
{
delete pb[i];
}
endB = clock();
printf("Not Used MemPool Time For Delete = %d ms\n", endB - begB);

begA = clock();

for (i=0; i<CTIMES; i++)
{
delete pa[i];
}
endA = clock();
printf("Used MemPool Time For Delete = %d ms\n", endA - begA);
begB = clock();

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);


begA = clock();

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);


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
豪 阅读(3277)
评论(3) 编辑 收藏 引用 所属分类:
C++之梦