用了《Modern C++ Design》上的那個(gè)Chunk，在Chunk查找Block的時(shí)間是O(1)，但是在MemPool的ChunkList里面查找某內(nèi)存地址卻需要O(n)的時(shí)間復(fù)雜度，因?yàn)槲业乃惴ㄖ皇蔷€性的便利ChunkLisk的鏈表，所以但內(nèi)存池里面同時(shí)存在大量小對(duì)象時(shí)候，效果不是很好，比普通的new還差，但是如果內(nèi)存池內(nèi)同時(shí)存在的小對(duì)象的數(shù)目較小的時(shí)候，可以獲得不錯(cuò)的性能，計(jì)劃version2.0要改進(jìn)算法，但是嘗試加Map做O(logn)的查找，效果很不好，常數(shù)太大了，如果加hash又耗太多內(nèi)存，暫時(shí)沒(méi)什么想法，估計(jì)要改數(shù)據(jù)結(jié)構(gòu)了，+個(gè)freelist可以實(shí)現(xiàn)new操作O(1)但是free操作很難搞，怎樣快速定位某個(gè)內(nèi)存屬于哪個(gè)Chunk呢？有點(diǎn)難度，再看看書(shū)，再想想。
Chunk.h
#ifndef CHUNK_H
#define CHUNK_H
#include <cassert>
struct Chunk 
{
//初始化一個(gè)Chunk
void init(size_t blockSize, unsigned char blocks);
//分配一個(gè)block
void* allocate(size_t blockSize);
//回收一個(gè)block
void deallocate(void* p, size_t blockSize);
//Chunk的起始地址
unsigned char* pData_;
//第一個(gè)可用的block
unsigned char firstAvailableBlock_;
//block的塊數(shù)
unsigned char blocksAvailable_;
//析構(gòu)函數(shù)釋放內(nèi)存
~Chunk();
};
void Chunk::init(size_t blockSize, unsigned char blocks) {
//從操作系統(tǒng)申請(qǐng)一個(gè)Chunk的內(nèi)存
pData_ = new unsigned char[blockSize * blocks];
firstAvailableBlock_ = 0;
blocksAvailable_ = blocks;
unsigned char *p = pData_;
//每個(gè)可用的block存放它下一個(gè)可用的block的編號(hào)
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);
//更新第一個(gè)可用的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);
//判斷是否產(chǎn)生精度誤差
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 :
//新分配一個(gè)Chunk
ChunkList* allocChunk();
//釋放一個(gè)Chunk
void freeChunk(ChunkList* pChunkList);
//一個(gè)Chunk所擁有的Block數(shù)
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;
//新建一個(gè)Chunk
pTmpChunkList->valChunk_->init(blockSize_, BLOCKS);
//把這個(gè)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() {
//測(cè)試新建100000個(gè)SmallObjet所需要的時(shí)間
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;
}
運(yùn)行結(jié)果：
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
可以看到明顯當(dāng)內(nèi)存池有大量小對(duì)象同時(shí)存在的時(shí)候，回收的時(shí)間很慢，其余時(shí)候效果還是不錯(cuò)的。
posted on 2008-04-20 17:53
豪 閱讀(661)
評(píng)論(0) 編輯 收藏 引用