再參考了《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
豪 閱讀(3294)
評論(3) 編輯 收藏 引用 所屬分類:
C++之夢