当前位置: 首页 > 工具软件 > MemoryPool > 使用案例 >

MemoryPool —— 简单高效的内存池 allocator 实现

楮庆
2023-12-01

       什么是内存池?什么是 C++ 的 allocator?

     内存池简单说,是为了减少频繁使用 malloc/free new/delete 等系统调用而造成的性能损耗而设计的。当我们的程序需要频繁地申请和释放内存时,频繁地使用内存管理的系统调用可能会造成性能的瓶颈,嗯,是可能,毕竟操作系统的设计也不是盖的(麻麻说把话说太满会被打脸的(⊙v⊙))。内存池的思想是申请较大的一块内存(不够时继续申请),之后把内存管理放在应用层执行,减少系统调用的开销。

     那么,allocator 呢?它默默的工作在 C++ 所有容器的内存分配上。默默贴几个链接吧:

     http://www.cnblogs.com/wpcockroach/archive/2012/05/10/2493564.html

     http://blog.csdn.net/justaipanda/article/details/7790355

     http://www.cplusplus.com/reference/memory/allocator/

     http://www.cplusplus.com/reference/memory/allocator_traits/

     当你对 allocator 有基本的了解之后,再看这个项目应该会有恍然大悟的感觉,因为这个内存池是以一个 allocator 的标准来实现的。一开始不明白项目里很多函数的定义是为了什么,结果初步了解了 allocator 后才知道大部分是标准接口。这样一个 memory pool allocator 可以与大多数 STL 容器兼容,也可以应用于你自定义的类。像作者给出的例子 —— test.cpp, 是用一个基于自己写的 stack 来做 memory pool allocator 和 std::allocator 性能的对比 —— 最后当然是 memory pool allocator 更优。


      项目:

      Github:MemoryPool


      基本使用:

      因为这是一个 allocator 类,所以所有使用 std::allocator 的地方都可以使用这个 MemoryPool。在项目的 test.cpp 中,MemoryPool 作为 allocator 用于 StackAlloc(作者实现的 demo 类) 的内存管理类。定义如下:

  1. StackAlloc<int, MemoryPool<int> > stackPool;  
     其次,你也可以将其直接作为任一类型的内存池,用 newElement 创建新元素,deleteElement 释放元素,就像 new/delete 一样。用下面的例子和 new/delete 做对比:
  1. #include <iostream>  
  2. #include <cassert>  
  3. #include <time.h>  
  4. #include <vector>  
  5. #include <stack>  
  6.   
  7. #include "MemoryPool.h"  
  8.   
  9. using namespace std;  
  10.   
  11. /* Adjust these values depending on how much you trust your computer */  
  12. #define ELEMS 1000000  
  13. #define REPS 50  
  14.   
  15. int main()  
  16. {  
  17.   
  18.     clock_t start;  
  19.   
  20.     MemoryPool<size_t> pool;  
  21.     start = clock();  
  22.     for(int i = 0;i < REPS;++i)  
  23.     {  
  24.         for(int j = 0;j< ELEMS;++j)  
  25.         {  
  26.             // 创建元素  
  27.             size_t* x = pool.newElement();  
  28.   
  29.             // 释放元素  
  30.             pool.deleteElement(x);  
  31.         }  
  32.     }  
  33.     std::cout << "MemoryPool Time: ";  
  34.     std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";  
  35.   
  36.   
  37.     start = clock();  
  38.     for(int i = 0;i < REPS;++i)  
  39.     {  
  40.         for(int j = 0;j< ELEMS;++j)  
  41.         {  
  42.             size_t* x = new size_t;  
  43.   
  44.             delete x;  
  45.         }  
  46.     }  
  47.     std::cout << "new/delete Time: ";  
  48.     std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";  
  49.   
  50.     return 0;  
  51.   
  52. }  
     运行的结果是:

     MemoryPool Time: 1.93389

     new/delete Time: 4.64903
     嗯,内存池快了一倍多。如果是自定义的类的话这个差距应该还会更大一点。


     代码分析:

     项目的实现有 C++11 和 C++98 两个版本,C++11 版本似乎更加高效,不过个人 C++11 了解不多,就以 C++98 版本来分析吧。

      主要函数:

     allocate    分配一个对象所需的内存空间

     deallocate   释放一个对象的内存(归还给内存池,不是给操作系统)

     construct   在已申请的内存空间上构造对象

     destroy  析构对象

     newElement  从内存池申请一个对象所需空间,并调用对象的构造函数

     deleteElement  析构对象,将内存空间归还给内存池

     allocateBlock  从操作系统申请一整块内存放入内存池

       关键知识点:

      理解项目的关键在于理解 placement new 和 union 的用法.

      placement new: http://blog.csdn.net/zhangxinrun/article/details/5940019

      union:http://www.cnblogs.com/BeyondTechnology/archive/2010/09/19/1831293.html

      关于 union 的使用觉得好巧妙,这是相应的定义:

  1. union Slot_ {  
  2.   value_type element;  
  3.   Slot_* next;  
  4. };  
     Slot_ 在创建对象的时候存放对象的值,当这个对象被释放时这块内存作为一个 Slot_* 指针放入 free 的链表。所以 Slot_ 既可以用来存放对象,又可以用来构造链表。
       工作原理:

      内存池是一个一个的 block 以链表的形式连接起来,每一个 block 是一块大的内存,当内存池的内存不足的时候,就会向操作系统申请新的 block 加入链表。还有一个 freeSlots_ 的链表,链表里面的每一项都是对象被释放后归还给内存池的空间,内存池刚创建时 freeSlots_ 是空的,之后随着用户创建对象,再将对象释放掉,这时候要把内存归还给内存池,怎么归还呢?就是把指向这个对象的内存的指针加到 freeSlots_ 链表的前面(前插)。

     用户在创建对象的时候,先检查 freeSlots_ 是否为空,不为空的时候直接取出一项作为分配出的空间。否则就在当前 block 内取出一个 Slot_ 大小的内存分配出去,如果 block 里面的内存已经使用完了呢?就向操作系统申请一个新的 block。

     内存池工作期间的内存只会增长,不释放给操作系统。直到内存池销毁的时候,才把所有的 block delete 掉。

       注释源码:

      点我到 Github

      头文件:

  1. /*- 
  2.  * Copyright (c) 2013 Cosku Acay, http://www.coskuacay.com 
  3.  * 
  4.  * Permission is hereby granted, free of charge, to any person obtaining a 
  5.  * copy of this software and associated documentation files (the "Software"), 
  6.  * to deal in the Software without restriction, including without limitation 
  7.  * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
  8.  * and/or sell copies of the Software, and to permit persons to whom the 
  9.  * Software is furnished to do so, subject to the following conditions: 
  10.  * 
  11.  * The above copyright notice and this permission notice shall be included in 
  12.  * all copies or substantial portions of the Software. 
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  15.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
  16.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
  17.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
  18.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
  19.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
  20.  * IN THE SOFTWARE. 
  21.  */  
  22.   
  23. #ifndef MEMORY_POOL_H  
  24. #define MEMORY_POOL_H  
  25.   
  26. #include <limits.h>  
  27. #include <stddef.h>  
  28.   
  29. template <typename T, size_t BlockSize = 4096>  
  30. class MemoryPool  
  31. {  
  32.   public:  
  33.     /* Member types */  
  34.     typedef T               value_type;       // T 的 value 类型  
  35.     typedef T*              pointer;          // T 的 指针类型  
  36.     typedef T&              reference;        // T 的引用类型  
  37.     typedef const T*        const_pointer;    // T 的 const 指针类型  
  38.     typedef const T&        const_reference;  // T 的 const 引用类型  
  39.     typedef size_t          size_type;        // size_t 类型  
  40.     typedef ptrdiff_t       difference_type;  // 指针减法结果类型  
  41.   
  42.     template <typename U> struct rebind {  
  43.       typedef MemoryPool<U> other;  
  44.     };  
  45.   
  46.     /* Member functions */  
  47.     /* 构造函数 */  
  48.     MemoryPool() throw();  
  49.     MemoryPool(const MemoryPool& memoryPool) throw();  
  50.     template <class U> MemoryPool(const MemoryPool<U>& memoryPool) throw();  
  51.   
  52.     /* 析构函数 */  
  53.     ~MemoryPool() throw();  
  54.   
  55.     /* 元素取址 */  
  56.     pointer address(reference x) const throw();  
  57.     const_pointer address(const_reference x) const throw();  
  58.   
  59.     // Can only allocate one object at a time. n and hint are ignored  
  60.     // 分配和收回一个元素的内存空间  
  61.     pointer allocate(size_type n = 1, const_pointer hint = 0);  
  62.     void deallocate(pointer p, size_type n = 1);  
  63.   
  64.     // 可达到的最多元素数  
  65.     size_type max_size() const throw();  
  66.   
  67.     // 基于内存池的元素构造和析构  
  68.     void construct(pointer p, const_reference val);  
  69.     void destroy(pointer p);  
  70.   
  71.     // 自带申请内存和释放内存的构造和析构  
  72.     pointer newElement(const_reference val);  
  73.     void deleteElement(pointer p);  
  74.   
  75.   private:  
  76.     // union 结构体,用于存放元素或 next 指针  
  77.     union Slot_ {  
  78.       value_type element;  
  79.       Slot_* next;  
  80.     };  
  81.   
  82.     typedef char* data_pointer_;  // char* 指针,主要用于指向内存首地址  
  83.     typedef Slot_ slot_type_;     // Slot_ 值类型  
  84.     typedef Slot_* slot_pointer_; // Slot_* 指针类型  
  85.   
  86.     slot_pointer_ currentBlock_;  // 内存块链表的头指针  
  87.     slot_pointer_ currentSlot_;   // 元素链表的头指针  
  88.     slot_pointer_ lastSlot_;      // 可存放元素的最后指针  
  89.     slot_pointer_ freeSlots_;     // 元素构造后释放掉的内存链表头指针  
  90.   
  91.     size_type padPointer(data_pointer_ p, size_type align) const throw();  // 计算对齐所需空间  
  92.     void allocateBlock();  // 申请内存块放进内存池  
  93.    /* 
  94.     static_assert(BlockSize >= 2 * sizeof(slot_type_), "BlockSize too small."); 
  95.     */  
  96. };  
  97.   
  98. #include "MemoryPool.tcc"  
  99.   
  100. #endif // MEMORY_POOL_H  

      实现文件:

  1. /*- 
  2.  * Copyright (c) 2013 Cosku Acay, http://www.coskuacay.com 
  3.  * 
  4.  * Permission is hereby granted, free of charge, to any person obtaining a 
  5.  * copy of this software and associated documentation files (the "Software"), 
  6.  * to deal in the Software without restriction, including without limitation 
  7.  * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
  8.  * and/or sell copies of the Software, and to permit persons to whom the 
  9.  * Software is furnished to do so, subject to the following conditions: 
  10.  * 
  11.  * The above copyright notice and this permission notice shall be included in 
  12.  * all copies or substantial portions of the Software. 
  13.  * 
  14.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  15.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
  16.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
  17.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
  18.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
  19.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
  20.  * IN THE SOFTWARE. 
  21.  */  
  22.   
  23. #ifndef MEMORY_BLOCK_TCC  
  24. #define MEMORY_BLOCK_TCC  
  25.   
  26. // 计算对齐所需补的空间  
  27. template <typename T, size_t BlockSize>  
  28. inline typename MemoryPool<T, BlockSize>::size_type  
  29. MemoryPool<T, BlockSize>::padPointer(data_pointer_ p, size_type align)  
  30. const throw()  
  31. {  
  32.   size_t result = reinterpret_cast<size_t>(p);  
  33.   return ((align - result) % align);  
  34. }  
  35.   
  36. /* 构造函数,所有成员初始化 */  
  37. template <typename T, size_t BlockSize>  
  38. MemoryPool<T, BlockSize>::MemoryPool()  
  39. throw()  
  40. {  
  41.   currentBlock_ = 0;  
  42.   currentSlot_ = 0;  
  43.   lastSlot_ = 0;  
  44.   freeSlots_ = 0;  
  45. }  
  46.   
  47. /* 复制构造函数,调用 MemoryPool 初始化*/  
  48. template <typename T, size_t BlockSize>  
  49. MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool& memoryPool)  
  50. throw()  
  51. {  
  52.   MemoryPool();  
  53. }  
  54.   
  55. /* 复制构造函数,调用 MemoryPool 初始化*/  
  56. template <typename T, size_t BlockSize>  
  57. template<class U>  
  58. MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool<U>& memoryPool)  
  59. throw()  
  60. {  
  61.   MemoryPool();  
  62. }  
  63.   
  64. /* 析构函数,把内存池中所有 block delete 掉 */  
  65. template <typename T, size_t BlockSize>  
  66. MemoryPool<T, BlockSize>::~MemoryPool()  
  67. throw()  
  68. {  
  69.   slot_pointer_ curr = currentBlock_;  
  70.   while (curr != 0) {  
  71.     slot_pointer_ prev = curr->next;  
  72.     // 转化为 void 指针,是因为 void 类型不需要调用析构函数,只释放空间  
  73.     operator delete(reinterpret_cast<void*>(curr));  
  74.     curr = prev;  
  75.   }  
  76. }  
  77.   
  78. /* 返回地址 */  
  79. template <typename T, size_t BlockSize>  
  80. inline typename MemoryPool<T, BlockSize>::pointer  
  81. MemoryPool<T, BlockSize>::address(reference x)  
  82. const throw()  
  83. {  
  84.   return &x;  
  85. }  
  86.   
  87. /* 返回地址的 const 重载*/  
  88. template <typename T, size_t BlockSize>  
  89. inline typename MemoryPool<T, BlockSize>::const_pointer  
  90. MemoryPool<T, BlockSize>::address(const_reference x)  
  91. const throw()  
  92. {  
  93.   return &x;  
  94. }  
  95.   
  96. // 申请一块空闲的 block 放进内存池  
  97. template <typename T, size_t BlockSize>  
  98. void  
  99. MemoryPool<T, BlockSize>::allocateBlock()  
  100. {  
  101.   // Allocate space for the new block and store a pointer to the previous one  
  102.   // operator new 申请对应大小内存,返回 void* 指针  
  103.   data_pointer_ newBlock = reinterpret_cast<data_pointer_>  
  104.                            (operator new(BlockSize));  
  105.   // 原来的 block 链头接到 newblock  
  106.   reinterpret_cast<slot_pointer_>(newBlock)->next = currentBlock_;  
  107.   // 新的 currentblock_  
  108.   currentBlock_ = reinterpret_cast<slot_pointer_>(newBlock);  
  109.   // Pad block body to staisfy the alignment requirements for elements  
  110.   data_pointer_ body = newBlock + sizeof(slot_pointer_);  
  111.   // 计算为了对齐应该空出多少位置  
  112.   size_type bodyPadding = padPointer(body, sizeof(slot_type_));  
  113.   // currentslot_ 为该 block 开始的地方加上 bodypadding 个 char* 空间  
  114.   currentSlot_ = reinterpret_cast<slot_pointer_>(body + bodyPadding);  
  115.   // 计算最后一个能放置 slot_type_ 的位置  
  116.   lastSlot_ = reinterpret_cast<slot_pointer_>  
  117.               (newBlock + BlockSize - sizeof(slot_type_) + 1);  
  118. }  
  119.   
  120. // 返回指向分配新元素所需内存的指针  
  121. template <typename T, size_t BlockSize>  
  122. inline typename MemoryPool<T, BlockSize>::pointer  
  123. MemoryPool<T, BlockSize>::allocate(size_type, const_pointer)  
  124. {  
  125.   // 如果 freeSlots_ 非空,就在 freeSlots_ 中取内存  
  126.   if (freeSlots_ != 0) {  
  127.     pointer result = reinterpret_cast<pointer>(freeSlots_);  
  128.     // 更新 freeSlots_  
  129.     freeSlots_ = freeSlots_->next;  
  130.     return result;  
  131.   }  
  132.   else {  
  133.     if (currentSlot_ >= lastSlot_)  
  134.       // 之前申请的内存用完了,分配新的 block  
  135.       allocateBlock();  
  136.     // 从分配的 block 中划分出去  
  137.     return reinterpret_cast<pointer>(currentSlot_++);  
  138.   }  
  139. }  
  140.   
  141. // 将元素内存归还给 free 内存链表  
  142. template <typename T, size_t BlockSize>  
  143. inline void  
  144. MemoryPool<T, BlockSize>::deallocate(pointer p, size_type)  
  145. {  
  146.   if (p != 0) {  
  147.     // 转换成 slot_pointer_ 指针,next 指向 freeSlots_ 链表  
  148.     reinterpret_cast<slot_pointer_>(p)->next = freeSlots_;  
  149.     // 新的 freeSlots_ 头为 p  
  150.     freeSlots_ = reinterpret_cast<slot_pointer_>(p);  
  151.   }  
  152. }  
  153.   
  154. // 计算可达到的最大元素上限数  
  155. template <typename T, size_t BlockSize>  
  156. inline typename MemoryPool<T, BlockSize>::size_type  
  157. MemoryPool<T, BlockSize>::max_size()  
  158. const throw()  
  159. {  
  160.   size_type maxBlocks = -1 / BlockSize;  
  161.   return (BlockSize - sizeof(data_pointer_)) / sizeof(slot_type_) * maxBlocks;  
  162. }  
  163.   
  164. // 在已分配内存上构造对象  
  165. template <typename T, size_t BlockSize>  
  166. inline void  
  167. MemoryPool<T, BlockSize>::construct(pointer p, const_reference val)  
  168. {  
  169.   // placement new 用法,在已有内存上构造对象,调用 T 的复制构造函数,  
  170.   new (p) value_type (val);  
  171. }  
  172.   
  173. // 销毁对象  
  174. template <typename T, size_t BlockSize>  
  175. inline void  
  176. MemoryPool<T, BlockSize>::destroy(pointer p)  
  177. {  
  178.   // placement new 中需要手动调用元素 T 的析构函数  
  179.   p->~value_type();  
  180. }  
  181.   
  182. // 创建新元素  
  183. template <typename T, size_t BlockSize>  
  184. inline typename MemoryPool<T, BlockSize>::pointer  
  185. MemoryPool<T, BlockSize>::newElement(const_reference val)  
  186. {  
  187.   // 申请内存  
  188.   pointer result = allocate();  
  189.   // 在内存上构造对象  
  190.   construct(result, val);  
  191.   return result;  
  192. }  
  193.   
  194. // 删除元素  
  195. template <typename T, size_t BlockSize>  
  196. inline void  
  197. MemoryPool<T, BlockSize>::deleteElement(pointer p)  
  198. {  
  199.   if (p != 0) {  
  200.     // placement new 中需要手动调用元素 T 的析构函数  
  201.     p->~value_type();  
  202.     // 归还内存  
  203.     deallocate(p);  
  204.   }  
  205. }  
  206.   
  207. #endif // MEMORY_BLOCK_TCC 
 类似资料: