登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

聊天机器

Chatbot's private blog

 
 
 

日志

 
 

【转】最简单的内存池-原理与实现  

2010-03-10 10:17:48|  分类: 程序理论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

内存池的主要作用,简单地说来,便是提高内存的使用效率。堆内存的申请与释放(new/delete及malloc/free),涉及复杂的内存分配算法,相比由简单CPU指令支持的栈内存的申请与释放,则是慢上了数量级。另一方面,栈的大小是有限制的,在需要大量内存的操作时,堆的使用是必要的。当然,频繁地申请与释放堆内存,效率是很低的,这也就是内存池出现的原因。

类似std::vector容器,在向vector里添加一个元素之前,该容器往往提前申请了一大块内存,实际添加时就只需要拿出其中一小块来使用,不用每添加一个都使用new一次。内存池所做的,也就是一次申请一块大内存,然后再小块小块地拿出来用:一次申请NM大小的内存,必然比N次申请M大小的内存要快,这就是内存池高效的简单解释。

一般来说,内存池可以按两种维度划分:单线程与多线程,可变大小和固定大小。其中最简单的单线程固定大小的内存池。这类内存池只考虑单线程的程序,分配与回收的对象都是固定大小的。这个简单的内存池类模板声明如下:

view  plaincopy  to  clipboardprint?
template<typename  T,  int  BaseSize=32>     
class  SimpleMemPool       
{     
private:     
#pragma  pack(push,  1)     
        union  ObjectChunk     
        {     
                ObjectChunk  *  next;     
                char  buf[sizeof(T)];     
        };         
        struct  MemBlock     
        {     
                MemBlock*  next;     
                ObjectChunk  chunks[BaseSize];     
        };     
#pragma  pack(pop)     
   
        SimpleMemPool(const  SimpleMemPool<T,  BaseSize>  &)  ;     
             
        MemBlock  *  head;     
        ObjectChunk  *  freeChunk;     
public:     
        SimpleMemPool();     
        ~SimpleMemPool();     
   
        T*  New();     
        void  Delete(T*  t);     
};   
template<typename  T,  int  BaseSize=32>
class  SimpleMemPool 
{
private:
#pragma  pack(push,  1)
 union  ObjectChunk
 {
  ObjectChunk  *  next;
  char  buf[sizeof(T)];
 }; 
 struct  MemBlock
 {
  MemBlock*  next;
  ObjectChunk  chunks[BaseSize];
 };
#pragma  pack(pop)

 SimpleMemPool(const  SimpleMemPool<T,  BaseSize>  &)  ;
 
 MemBlock  *  head;
 ObjectChunk  *  freeChunk;
public:
 SimpleMemPool();
 ~SimpleMemPool();

 T*  New();
 void  Delete(T*  t);
};
 

该内存池类模板实例化之后,产生一个只用于申请对象T的内存池。创建对象的方法是T*  New(),删除对象的方法是void  Delete(T  *)。类模板中还定义了两个数据结构及两个成员变量,还禁止了内存池的拷贝构造。对于这种内存池,它有两层的链表结构:第一层是内存块链表(MemBlock),由成员head为头,把内存池中申请的大块内存串接起来。MemBlock结构的next指针指向了下一个内存块,chunks则为BaseSize个ObjectChunk对象。该链表的每个结点都是内存池进行一次申请得到的大内存块;第二层为自由内存块链表(ObjectChunk),由freeChunk为头指针串着,该链表的每一个结点,都是一个可以使用的小内存块。大体结构如下图(BaseSize为5)所示:

 

当用户向内存池申请一个对象T时,内存池会检查freeChunk是否为NULL。不为NULL时,表示还有自由的小内存块(ObjectChunk)可供使用,将它返回给用户,并将freeChunk移到下一个自由内存块;若freeChunk为NULL,则内存池需要使用new/malloc从申请一块大内存(MemBlock),然后将其中的BaseSize个ObjectChunk都串连上形成链表,再将freeChunk做为头指针。这时freeChunk不为NULL了,可以提供给用户一块小内存了(具体即是,取出链表的首结点)。

view  plaincopy  to  clipboardprint?
template<>     
class  SimpleMemPool     
{     
        T*  New()     
        {     
                if  (!freeChunk)     
                {     
                        MemBlock  *  t  =  new  MemBlock;     
                        t->next  =  head;     
                        head  =  t;     
                        for(unsigned  int  i=0;  i<BaseSize-1;++i)     
                        {     
                                head->chunks[i].next  =  &  (head->chunks[i+1]);     
                        }     
                        head->chunks[BaseSize-1].next  =  0;     
                        freeChunk  =  &  (head->chunks[0]);     
                }       
   
                ObjectChunk  *  t  =  freeChunk;     
                freeChunk  =  freeChunk->next;     
                return  reinterpret_cast<T*>(t);     
        }     
};   
template<>
class  SimpleMemPool
{
 T*  New()
 {
  if  (!freeChunk)
  {
   MemBlock  *  t  =  new  MemBlock;
   t->next  =  head;
   head  =  t;
   for(unsigned  int  i=0;  i<BaseSize-1;++i)
   {
    head->chunks[i].next  =  &  (head->chunks[i+1]);
   }
   head->chunks[BaseSize-1].next  =  0;
   freeChunk  =  &  (head->chunks[0]);
  } 

  ObjectChunk  *  t  =  freeChunk;
  freeChunk  =  freeChunk->next;
  return  reinterpret_cast<T*>(t);
 }
}; 

当用户不再使用某块小内存时,需要调用Delete方法。此时,内存池把用户不用的小块内存,重新连接到以freeChunk为首指针的链表中就行了(将结点插入链表的首位置)。代码如下:

view  plaincopy  to  clipboardprint?
template<>     
class  SimpleMemPool     
{     
        void  Delete(T*  t)     
        {     
                ObjectChunk  *  chunk  =  reinterpret_cast<ObjectChunk*>(t);     
                chunk->next=  freeChunk;     
                freeChunk  =  chunk;     
        }     
};   
template<>
class  SimpleMemPool
{
 void  Delete(T*  t)
 {
  ObjectChunk  *  chunk  =  reinterpret_cast<ObjectChunk*>(t);
  chunk->next=  freeChunk;
  freeChunk  =  chunk;
 }
}; 

当内存池不在使用时,析构释放全部内存,此时只需要释放head为首指针的链表的每个结点(遍历删除)。代码如下:

view  plaincopy  to  clipboardprint?
template<>     
class  SimpleMemPool()     
{     
        ~SimpleMemPool()     
        {           
                while(head)     
                {     
                        MemBlock  *  t  =  head;     
                        head  =  head->next;     
                        delete  t;     
                }     
        }     
}   
template<>
class  SimpleMemPool()
{
 ~SimpleMemPool()
 { 
  while(head)
  {
   MemBlock  *  t  =  head;
   head  =  head->next;
   delete  t;
  }
 }

实现中,需要注意的是ObjectChunk的双重身份:当它是自由内存块,还未分配给用户时,它是ObjectChunk的数据结构,包含一个链表指针,用于串连;当它分配给用户时,它退出了自由内存块链表,它被强制转换为T类型(代码中用了reinterpret_cast操作符号强制转换),此时便不再有ObjectChunk里的数据,不再需要链表指针。所以ObjectChunk结构的大小,应该大于或等于T类型的大小(出现大于情况,是因为ObjectChunk最小也必须包含一个指针大小,而T类型却小于一个指针大小)。#pragma  pack指令的使用,便是尽量使ObjectChunk的大小符合我们的预期(MemBlock也一样)当用户不再使用T类型对象时,便调用了Delete(T*),此时,T类型里的数据内容都不再重要了,强制变为ObjectChunk后,把其内容覆盖,使用前几个字节作为指针,又加入自由内存链表中。

总体说来,这个简单的内存池,仅仅实现了一次(向系统)申请,多次分配(给用户)的功能。对于大内存块(MemBlock),采取的方法是只申不放,仅在内存池销毁时才一次性全部释放。这样的策略仅仅适用于内存申请与释放频繁,且内存充足的情况。而多线程,可变大小的情况,也需要更多考虑。

附完整代码:

  view  plaincopy  to  clipboardprint?
template<typename  T,  int  BaseSize=32>     
class  SimpleMemPool       
{     
private:     
#pragma  pack(push,  1)     
        union  ObjectChunk     
        {     
                ObjectChunk  *  next;     
                char  buf[  sizeof(T)];     
        };         
        struct  MemBlock     
        {     
                MemBlock*  next;     
                ObjectChunk  chunks[BaseSize];     
        };     
#pragma  pack(pop)     
   
        SimpleMemPool(const  SimpleMemPool<T,  BaseSize>  &)       
        {}         
             
        MemBlock  *  head;     
        ObjectChunk  *  freeChunk;     
public:     
        SimpleMemPool()  :  head(0),  freeChunk(0)     
        {           
        }     
             
        ~SimpleMemPool()     
        {           
                while(head)     
                {     
                        MemBlock  *  t  =  head;     
                        head  =  head->next;     
                        delete  t;     
                }     
        }     
   
        T*  New()     
        {     
                if  (!freeChunk)     
                {     
                        MemBlock  *  t  =  new  MemBlock;     
                        t->next  =  head;     
                        head  =  t;     
                        for(unsigned  int  i=0;  i<BaseSize-1;++i)     
                        {     
                                head->chunks[i].next  =  &  (head->chunks[i+1]);     
                        }     
                        head->chunks[BaseSize-1].next  =  0;     
                        freeChunk  =  &  (head->chunks[0]);     
                }       
   
                ObjectChunk  *  t  =  freeChunk;     
                freeChunk  =  freeChunk->next;     
                return  reinterpret_cast<T*>(t);     
        }     
   
        void  Delete(T*  t)     
        {     
                ObjectChunk  *  chunk  =  reinterpret_cast<ObjectChunk*>(t);     
                chunk->next=  freeChunk;     
                freeChunk  =  chunk;     
        }     
   
};   

 

三个问题:1、内存碎片处理问题。

                  2、效率处理问题

                  3、调用构造函数已经数组式时的问题。

 

 

  评论这张
 
阅读(806)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018