随笔 - 87  文章 - 279  trackbacks - 0
<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214820
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

用了《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 *= pData_;
    
//每个可用的block存放它下一个可用的block的编号
    for (unsigned char i = 1; i < blocks; i++, p += blockSize) {
        
*= i;
    }

}


void* Chunk::allocate(size_t blockSize) {
    
if (blocksAvailable_ == 0return 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 阅读(653) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理