用了《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
豪 閱讀(667)
評論(0) 編輯 收藏 引用