c/c++:efficient c++,单线程内存池

c++ efficient 的第六章，看书笔记，顺便说下理解。

对于一般直接 new 与delete 性能较差，可以自己管理写内存的申请与释放。

版本0：

class Rational
{
public:
    Rational(int a=0, int b =1 ): n(a),d(b){}
private:
    int n;
    int d;
};

版本1：专用的内存管理器

这版本是通过重载目标类中的new 与delete 实现内存管理，只适用于目标类，但是速度是最快的。

实现方式是维护一个链表，类中静态声明链表头，链表维护一串空间，通过类型转换在目标类和链表指针之间转换。

如果内存不够（freelist=NULL）是一次申请较多内存进行维护。

链表的添加删除（对于函数释放空间与申请空间）是在链首操作。

书上47 行 52行通过静态类型转换不成功，改为了强制转换，在codeblock g++ 中能够编译运行。

主要在主函数中调用静态函数链表的申请与释放。即74 86行。

注意65 行把原来的delete [] 改为了 delete[] (char*) 原因可以参考第二版本。

 1 class NextOnFreeList
 2 {
 3 public:
 4     NextOnFreeList *next;
 5 };
 6 
 7 class Rational
 8 {
 9 public:
10     Rational(int a=0, int b =1 ): n(a),d(b){}
11     inline void *operator new(size_t size);
12     inline void operator delete(void * doomed, size_t size);
13 
14     static void newMemPool(){ expandTheFreeList();   }
15     static void deleteMemPool();
16     static void expandTheFreeList();
17 private:
18     int n;
19     int d;
20     static NextOnFreeList * freelist;
21     enum{   EXPANSION_SIZE = 32 };
22 };
23 
24 inline
25 void * Rational::operator new( size_t size)
26 {
27     if(0 == freelist)
28     {
29         expandTheFreeList();
30     }
31     NextOnFreeList * head =freelist;
32     freelist=head->next;
33     return head;
34 }
35 
36 inline
37 void Rational::operator delete(void * doomed ,size_t size)
38 {
39     NextOnFreeList *head=static_cast<NextOnFreeList *>( doomed);
40     head->next=freelist;
41     freelist=head;
42 }
43 
44 void Rational:: expandTheFreeList()
45 {
46     size_t size= (sizeof(Rational)>sizeof(NextOnFreeList*))?sizeof(Rational):sizeof(NextOnFreeList*);
47 //    NextOnFreeList *runner= static_cast<NextOnFreeList *>(new char [size]);
48     NextOnFreeList *runner= (NextOnFreeList *)(new char [size]);
49     freelist=runner;
50     for(int i=0;i<EXPANSION_SIZE;i++)
51     {
52 //        runner->next= static_cast<NextOnFreeList *>( new char [size] );
53         runner->next= (NextOnFreeList *) new char [size] ;
54         runner=runner->next;
55     }
56     runner->next= 0;
57 }
58 
59 void Rational::deleteMemPool()
60 {
61     NextOnFreeList * nextPtr;
62     for(nextPtr=freelist;nextPtr!=NULL;nextPtr=freelist)
63     {
64         freelist=freelist->next;
65         delete [](char *)nextPtr;
66     }
67 }
68 
69 NextOnFreeList * Rational::freelist =0;
70 
71 int main()
72 {
73     Rational * array[1000];
74     Rational::newMemPool();
75     for(int j=0;j<500;j++)
76     {
77         for(int i=0;i<1000;i++)
78         {
79             array[i]=new Rational(i);
80         }
81         for(int i=0;i<1000;i++)
82         {
83             delete array[i];
84         }
85     }
86     Rational::deleteMemPool();
87     return 0;
88 }

版本2：固定大小对象的内存池

考虑版本1，可以通过模板实现管理特定的对象。最主要的参数是类的大小。

实现是专门声明一个管理内存的内存池类，使用模板实现，提供alloc（） free（）接口，给类申请与释放内存。

内存池类的实现是自身有一个MemoryPool<T>* next 指针用来指向维护的链表，内存的操作都在链首位置。

第32行书上代码编译不通过，

delete [] nextPrt;

时，nextPrt 的类型为 MemoryPool * ，这样在释放的时候再一次调用了 ~MemoryPool 而不是默认的内存释放。（第一次调用是上层类的析构函数调用的）

所以在这改为了

delete [](char*)nextPrt;

这样才能成功释放内存。

下面的是底层类的代码。

 1 template<class T>
 2 class MemoryPool
 3 {
 4 public:
 5     MemoryPool(size_t size =EXPANSION_SIZE);
 6     ~MemoryPool();
 7 
 8     //从空闲列表中分配T元素
 9     inline void * alloc(size_t size);
10     inline void free(void * someElement);
11 private:
12     MemoryPool<T>* next;
13     enum{EXPANSION_SIZE=2};
14     //将空闲元素添加至空闲列表
15     void expanTheFreeList(int howMany=EXPANSION_SIZE);
16 };
17 
18 template<class T>
19 MemoryPool<T>::MemoryPool(size_t size)
20 {
21     expanTheFreeList( size);
22 }
23 
24 template<class T>
25 MemoryPool<T>::~MemoryPool()
26 {
27     cout<<next<<endl;
28     MemoryPool<T> * nextPrt=next;
29     for(nextPrt=next;nextPrt!=NULL;nextPrt=next)
30     {
31         next=next->next;
32 //        delete [] nextPrt;
33         delete [](char*)nextPrt;
34     }
35 }
36 
37 template<class T>
38 inline
39 void * MemoryPool<T>::alloc(size_t size)
40 {
41     if(!next)
42     {
43         expanTheFreeList();
44     }
45     MemoryPool<T> * head=next;
46     next=head->next;
47     return head;
48 }
49 
50 template<class T>
51 inline
52 void MemoryPool<T>::free(void * doomed)
53 {
54 //    MemoryPool<T> *head=static_cast<MemoryPool<T>* >(doomed);
55     MemoryPool<T> *head=(MemoryPool<T>* )(doomed);
56     head->next=next;
57     next=head;
58 }
59 
60 template<class T>
61 void MemoryPool<T>::expanTheFreeList(int howmany)
62 {
63     size_t size=(sizeof(T)>sizeof(MemoryPool<T>*))? sizeof(T):sizeof(MemoryPool<T>*);
64 //    MemoryPool<T>* runner =static_cast< MemoryPool<T>* >(new char [size]);
65     MemoryPool<T>* runner =( MemoryPool<T>* )(new char [size]);
66     next=runner;
67     for(int i=0 ;i<howmany;i++)
68     {
69 //        runner->next=static_cast< MemoryPool<T>* >(new char [size]);
70         runner->next=( MemoryPool<T>* )(new char [size]);
71         runner=runner->next;
72     }
73     runner->next=0;
74 }

下面是调用类与使用的代码：

12行的时候会调用 MemoryPool 的构造函数。

 1 //使用内存池的类
 2 class Rational
 3 {
 4 private:
 5     int n;
 6     int d;
 7     static MemoryPool<Rational > *memPool;
 8 public:
 9     Rational(int a=0, int b=1) : n(a),d(b){}
10     void *operator new(size_t size){    return memPool->alloc(size);    }
11     void operator delete(void* doomed, size_t size){    memPool->free(doomed);    }
12     static void newMemPool(){   memPool=new MemoryPool <Rational >;    }
13     static void deleteMemPool(){    delete memPool; }
14 };
15 
16 MemoryPool<Rational>* Rational::memPool=0;
17 
18 int main()
19 {
20     //...
21     Rational::newMemPool();
22     //...
23     Rational::deleteMemPool();
24     //..
25     return 0;
26 }

版本3：将版本2的固定长度改为不定长度,称为可变大小内存池

首先要有个认识，既然是可变长度，那么通常释放后，再一次申请的时候不会申请这一段内存的，（通过代码的实现是不打算复用内存的）第一是不适用，第二就算够那么将造成管理的困难

想想申请而来123连续的3段内存，第二段内存需要释放，这大小就固定下来了(13还没释放)，如果想复用，这个就另外实现吧。 - -！

实现方式是在内存池(版本2 的MemoryPool)下层在创建一个类，用来指向一个大内存块，一个计数，表示前多少内存已经使用了，如果不够就再一次申请一个内存块。至于浪费的考虑，看书上说的吧。 - -！

MemoryPool 还是第二版本的功能，提供接口，不过对于物理内存的申请就下放了。

仍然是维护链表实现，还是链首操作。

内存块类：

因为最低成的释放free 基于设计因素什么也不赶，要想的也可以对free 修改，参数什么的都有传递。

29行书上是直接 delete [] mem; 不过这样会提示void* 操作，强制转换了

 1 class MemoryChunk
 2 {
 3 private:
 4     MemoryChunk* next;//指向下个内存块
 5     void * mem;//指向可用的内存
 6     size_t chunkSize;//该内存块的大小
 7     size_t bytesAlreadyAllocated;//已经分配的字节数
 8 public:
 9     MemoryChunk(MemoryChunk *nextChunk ,size_t chunkSize);
10     ~MemoryChunk();
11 
12     inline void* alloc(size_t size);
13     inline void free (void* someElement);
14     MemoryChunk* nextMemChunk() {  return next; }
15     size_t spaceAvailable() {   return chunkSize - bytesAlreadyAllocated;   }
16     enum{   DEFUALT_CHUNK_SIZE = 4096  };
17 };
18 
19 MemoryChunk::MemoryChunk(MemoryChunk* nextChunk, size_t reqSize)
20 {
21     chunkSize = (reqSize > DEFUALT_CHUNK_SIZE) ? reqSize : DEFUALT_CHUNK_SIZE;
22     next = nextChunk;
23     bytesAlreadyAllocated=0;
24     mem= new char [chunkSize];
25 }
26 
27 MemoryChunk::~MemoryChunk()
28 {
29     delete [] (char*)mem;
30 }
31 
32 void* MemoryChunk::alloc(size_t requestSize)
33 {
34     void* addr = (void* )((size_t )mem + bytesAlreadyAllocated );
35     bytesAlreadyAllocated+=requestSize;
36     return addr;
37 }
38 
39 inline void MemoryChunk::free(void* someElement ) {}

内存池类：

必须注意16行，对链表的末尾赋0，书上是没有的，这句没有会导致析构的时候不能判断结束。

第26行的时候是调用memChunk的析构函数的。

 1 //内存池类
 2 class ByteMemoryPool
 3 {
 4 private:
 5     MemoryChunk* listOfMemoryChunks;
 6     void expandStorage(size_t reqSize);
 7 public:
 8     ByteMemoryPool(size_t initSize = MemoryChunk::DEFUALT_CHUNK_SIZE);
 9     ~ByteMemoryPool();
10     inline void* alloc(size_t size);
11     inline void free(void* someElement);
12 };
13 
14 ByteMemoryPool::ByteMemoryPool(size_t initSize)
15 {
16     listOfMemoryChunks=NULL;
17     expandStorage(initSize);
18 }
19 
20 ByteMemoryPool::~ByteMemoryPool()
21 {
22     MemoryChunk* memChunk = listOfMemoryChunks;
23     while(memChunk)
24     {
25         listOfMemoryChunks = memChunk->nextMemChunk();
26         delete memChunk;
27         memChunk = listOfMemoryChunks;
28     }
29 }
30 
31 inline
32 void* ByteMemoryPool::alloc(size_t requestSize)
33 {
34     size_t space = listOfMemoryChunks->spaceAvailable();
35     if(space<requestSize)
36     {
37         expandStorage(requestSize);
38     }
39     return listOfMemoryChunks->alloc(requestSize);
40 }
41 
42 inline
43 void ByteMemoryPool::free(void* doomed)
44 {
45     listOfMemoryChunks->free(doomed);
46 }
47 
48 void ByteMemoryPool::expandStorage(size_t requestSize)
49 {
50     listOfMemoryChunks = new MemoryChunk(listOfMemoryChunks,requestSize);
51 }

调用类与测试：

21 、33对应创建内存池与释放内存池，是同一个类中共享内存池。

 1 //调用类
 2 class Rational
 3 {
 4 private:
 5     int n;
 6     int d;
 7     static ByteMemoryPool* memPool;
 8 public:
 9     Rational(int a=0, int b=1):n(a),d(b){}
10     void* operator new (size_t size){   return memPool->alloc(size);    }
11     void operator delete (void* doomed, size_t size){   memPool->free(doomed);  }
12     static void newMemPool(){   memPool = new ByteMemoryPool;   }
13     static void deleteMemPool(){    delete memPool; }
14 };
15 
16 ByteMemoryPool* Rational::memPool=0;
17 
18 int main()
19 {
20     Rational * array[1000];
21     Rational::newMemPool();
22     for(int j=0;j<500;j++)
23     {
24         for(int i=0;i<1000;i++)
25         {
26             array[i]=new Rational(i);
27         }
28         for(int i=0;i<1000;i++)
29         {
30             delete array[i];
31         }
32     }
33     Rational::deleteMemPool();
34     return 0;
35 }

总结：

1.灵活性以速度为代价。

2.全局内存管理器是通用的（new 和 delete），因此代价高。

3.专用内存管理器比全局内存管理器快一个数量级以上。

4.如果主要分配固定大小的内存块，专用的固定大小内存管理器将明显地提升性能。

5.如果主要分配限于单线程内存块，那么内存块管理器也会有类似的性能提高。