用了《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
#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_;
//析构函数释放内存
~Chunk();
};
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_++;
}
Chunk::~Chunk() {
delete[] pData_;
}
#endif
MemPool.h
#ifndef MEMPOOL_H
#define MEMPOOL_H
#include "Chunk.h"
struct ChunkList {
Chunk* valChunk_;
ChunkList* next_;
ChunkList() : valChunk_(new Chunk), next_(0) {}
~ChunkList() {delete valChunk_;}
};
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);
//一个Chunk所拥有的Block数
static const int BLOCKS;
//free的Chunk
ChunkList* headOfChunkList_;
size_t blockSize_;
};
const int MemPool::BLOCKS = 255;
MemPool::MemPool(size_t blockSize) : blockSize_(blockSize), headOfChunkList_(0) {};
MemPool::~MemPool() {
while (headOfChunkList_) {
freeChunk(headOfChunkList_);
}
}
void* MemPool::alloc(size_t size) {
if (size != blockSize_) {
return ::operator new(size);
}
//查找可用的Block
ChunkList* p = headOfChunkList_;
while (p && !p->valChunk_->blocksAvailable_) p = p->next_;
if (!p) p = allocChunk();
void* pRet = p->valChunk_->allocate(blockSize_);
return pRet;
}
void MemPool::free(void* p, size_t size) {
if (!p) return ;
if (size != blockSize_) {
::operator delete(p);
return ;
}
//查找p所属的Chunk
ChunkList* pTmp = headOfChunkList_;
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_);
}
ChunkList* MemPool::allocChunk() {
ChunkList* pTmpChunkList = new ChunkList;
//新建一个Chunk
pTmpChunkList->valChunk_->init(blockSize_, BLOCKS);
//把这个Chunk加入到ChunkList的链表头
pTmpChunkList->next_ = headOfChunkList_;
headOfChunkList_ = pTmpChunkList;
return pTmpChunkList;
}
void MemPool::freeChunk(ChunkList* pChunkList) {
//在链表中查找
if (!pChunkList) return ;
ChunkList* p, * q;
p = headOfChunkList_;
q = p->next_;
if (p == pChunkList) {
//在表头
headOfChunkList_ = p->next_;
delete pChunkList;
return ;
}
while (q && q != pChunkList) {
p = q;
q = q->next_;
}
if (q) {
//查找成功
p->next_ = q->next_;
delete pChunkList;
}
}
#endif
test.cpp
#include <iostream>
#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 = 100000;
TestClassA* pa[CTIMES];
TestClassB* pb[CTIMES];
int main() {
//测试新建100000个SmallObjet所需要的时间
int i;
clock_t begB = clock();
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);
clock_t begA = clock();
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);
begB = clock();
for (i=0; i<CTIMES; 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 = 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
豪 阅读(654)
评论(0) 编辑 收藏 引用