一种高效的C++固定内存块分配器
snkl6509
8年前
<h2>简介</h2> <p>自定义固定内存块分配器用于解决两种类型的内存问题。第一，全局堆内存的分配和释放非常慢而且是不确定的。你不能确定内存管理需要消耗多长时间。第二，降低由堆内存碎片（对于执行关键操作的系统尤为重要）造成的内存分配失败的可能性。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/60899847b61f7ed515f159faf1ed7d81.jpg"></p> <p>即使不是执行关键操作的系统，一些嵌入式系统也需要被设计成需要运行数周甚至数年而不重启。取决于内存分配的模式和堆内存的实现方式，长时间的使用堆内存可能导致堆内存错误。</p> <p>典型的解决方案是预先静态声明所有对象的内存，从而摆脱动态申请内存。然而，由于对象即使没有被使用，也已经存在并占据一部分内存，静态分配内存的方式会浪费内存存储。此外，使用动态内存分配方式实现的系统提供更为自然的设计框架，而不像静态内存分配需要事先分配所有对象。</p> <p>固定内存块分配器并不是一种新的方法。人们已经设计过多种自定义内存分配器很长时间了。这里，我提供的是我在很多项目中成功使用的，一种简单的C++内存分配器的实现。</p> <p>这种分配器的实现具有如下特点：</p> <ul> <li>比全局堆内存速度快</li> <li>消除堆内存碎片错误</li> <li>不需要额外的内存存储（除了需要几个字节的静态内存）</li> <li>易于使用</li> <li>代码量很小</li> </ul> <p>这里将提供一个申请、释放内存的，包含上面所提到特点的简单类。</p> <h2>回收内存存储</h2> <p>内存管理模式的基本哲学是在对象内存分配时能够回收内存。一旦在内存中创建了一个对象，它所占用的内存就不能被重新分配。同时，内存要能够回收，允许相同类型的对象重用这部分内存。我实现了一个名为Allocator的类来展示这些技巧。</p> <p>当应用程序使用Allocator类进行删除时，对象占用的内存空间被释放以备重用，但却不会立即释放给内存管理器，这些内存保留在就一个称之为“释放列表”的链表中，并再次分配给相同类型的对象。对每个内存分配的请求，Allocaor类首先检查“释放列表”中是否存在待释放的内存。只有“释放列表”中没有可用的内存空间时才会分配新的内存。根据所需的Allocator类的行为，内存存储以三种操作模式使用全局堆内存或者静态内存池。</p> <ul> <li>1.堆内存</li> <li>2.堆内存池</li> <li>3.静态内存池</li> </ul> <h2>堆内存 vs. 内存池</h2> <p>Allocator类在“释放列表”为空时，能够从堆内存或者内存池中申请新内存。如果使用内存池，你必须事先确定好对象的数量。确保内存池足够容纳所有需要使用的对象。另一方面，使用堆内存没有数量大小的限制——可以构造内存允许的尽可能多的对象。</p> <p>堆内存模式在全局堆内存上为对象分配内存。释放操作将这块内存放入“释放了列表”以备重用。当“释放列表”为空时，需要在堆内存上创建新内存。这种方式提供了动态内存的分配和释放，优点是内存块可以在运行时动态增加，缺点是内存块创建期间是不确定的，可能创建失败。</p> <p>堆内存池模式从全局堆内存创建一个内存池。当Allocator类对象创建时，使用new操作符创建内存池。然后使用内存池中的内存块进行内存分配。</p> <p>静态内存池模式使用从静态内存中分配的内存池。静态内存池由使用者进行分配而不是由Allocator对象进行创建。</p> <p>堆内存池模式和静态内存池模式提供了内存操作的连续使用，因为内存分配器不需要分配单独的内存块。这样分配内存的过程是十分快速且具有确定性的。</p> <h2>类设计</h2> <p>类的接口很简单。Allocate()返回指向内存块的指针，Deallocate()释放内存以备重用。构造函数需要设置对象的大小，并且如果使用内存池，需要分配内存池空间。</p> <p>类的构造函数中的参数用于决定内存块分配的位置。size参数控制固定内存块的大小。objects参数设置申请内存块的个数，其值为0表示从堆内存中申请新内存块，非0表示使用内存池方式（堆内存池或者静态内存池）分配对象实例空间。memory参数是指向静态内存的指针。如果memory等于0并且objects非零，Allocator将从堆内存中创建一个内存池。静态内存池内存大小必须是size*object字节。name参数为内存分配器命名，用于收集分配器使用信息。</p> <pre> <code class="language-cpp">class Allocator { public: Allocator(size_t size, UINT objects=0, CHAR* memory=NULL, const CHAR* name=NULL); ...</code></pre> <p>下面的例子展示三种分配器模式中的构造函数是如何赋值的。</p> <pre> <code class="language-cpp">// Heap blocks mode with unlimited 100 byte blocks Allocator allocatorHeapBlocks(100); // Heap pool mode with 20, 100 byte blocks Allocator allocatorHeapPool(100, 20); // Static pool mode with 20, 100 byte blocks char staticMemoryPool[100 * 20]; Allocator allocatorStaticPool(100, 20, staticMemoryPool);</code></pre> <p>为了简化静态内存池方法，提供AllocatorPool<>模板类。模板的第一个参数设置申请内存对象类型，第二个参数设置申请对象的数量。</p> <pre> <code class="language-cpp">// Static pool mode with 20 MyClass sized blocks AllocatorPool<MyClass, 20> allocatorStaticPool2;</code></pre> <p>Deallocate()将内存地址放入“栈”中。这个“栈”的实现方式类似于单项链表（“释放列表”），但是只能添加、移除头部的对象，其行为类似栈的特性。使用“栈”使得分配、释放操作更为快速，因为不需要全链表遍历而只需要压入和弹出操作。</p> <pre> <code class="language-cpp">void* memory1 = allocatorHeapBlocks.Allocate(100);</code></pre> <p>这样便在不增加额外存储的情况下，将内存块链接在“释放列表”中。例如，当我们使用全局operate new时，首先申请内存，然后调用构造函数。delete的过程与此相反，首先调用析构函数，然后释放掉内存。调用完析构函数后，在内存释放给堆之前，这块内存不再被原有的对象使用，而是放到“释放列表”中以备重用。由于Allocator类需要保存已经释放的内存块，在使用delete操作符时，我们将“释放列表”中的下一个指针指向这个被delete的对象内存地址。当应用程序再次使用这块内存时，指针被覆写为对象的地址。通过这种方法，就不需要预先实例化内存空间。</p> <p>使用释放对象的内存来将内存块连接在一起意味着对象的内存空间需要足够容纳一个指针占用内存空间的大小。构造函数初始化列表中的代码保证了最小内存块大小不会小于指针占用内存块的大小。</p> <p>类的析构函数通过释放堆内存池或者遍历“释放列表”并逐个释放内存块来实现内存的释放。由于Allocator类对象常被用作是static的，那么Allocator对象的释放是在程序结束时。对于大多数嵌入式设备，应用只在人们拔断电源时才会结束。因此，对于这种嵌入式设备，析构函数的作用就显无所谓了。</p> <p>如果使用堆内存块模式，除非所有分配的内存被链接在“释放列表”，应用结束时分配的内存块不能被释放。因此，所有对象应该在程序结束时被“删除”（指放入“释放列表”）。这似乎是内存泄漏，也带来了一个有趣的问题。Allocator应该跟踪正在使用和已经释放的内存块吗？答案是否定的。以为一旦一块内存通过指针被应用所使用，那么应用程序有责任在程序结束前通过调用Deallocate()返回该内存块指针给Allocator。这样的话，我么只需要跟踪释放的内存块。</p> <h2>代码的使用</h2> <p>Allocator易于使用，因此创建宏来自动在客户端类中实现接口。宏提供一个静态类型的Allocator实例和两个成员函数：操作符new和操作符delete。通过重写new和delete操作符，Allocator截取并处理所有的客户端类的内存分配行为。</p> <p>DECLARE_ALLOCATOR宏提供头文件接口，并且应该在类定义时将其包含在内，如下面这样：</p> <pre> <code class="language-cpp">#include "Allocator.h" class MyClass { DECLARE_ALLOCATOR // remaining class definition };</code></pre> <p>操作符new函数调用Allocator创建类实例所需要的内存空间。内存分配后，根据定义，操作符new调用该类的构造函数。重写的new只修改了内存的分配任务。构造函数的调用由语言保证。删除对象时，系统首先调用析构函数，然后调用执行操作符delete函数。操作符delete使用Deallocate()函数将内存块加入到“释放列表”中。</p> <p>尽管没有明确声明，操作符delete是静态函数（静态函数才能调用静态成员）。因此它不能被声明为virtual。这样看上去通过基类的指针删除对象不能达到删除真实对象的目的。毕竟，调用基类指针的静态函数只会调用基类的成员函数，而不是其真实类型的成员函数。然而，我们知道，调用操作符delete时首先调用析构函数。修饰为virtual的析构函数会实际调用子类的析构函数。类的析构函数执行完后，子类的操作符delete函数被调用。因此实际上，由于虚析构函数的调用，重写的操作符delete会在子类中调用。所以，使用基类指针删除对象时，基类对象的析构函数必须声明为virtual。否则，将会不能正确调用析构函数和操作符delete。</p> <p>IMPLEMENT_ALLOCATOR宏是接口的源文件实现部分，并应该放置于源文件中。</p> <pre> <code class="language-cpp">IMPLEMENT_ALLOCATOR(MyClass, 0, 0)</code></pre> <p>使用上述宏后，可以如下面一样创建并销毁类的实例，同事循环使用释放的内存空间。</p> <pre> <code class="language-cpp">MyClass* myClass = new MyClass(); delete myClass;</code></pre> <p>Allocator类支持单继承和多继承。例如，Derived类继承Base类，如下代码是正确的。</p> <pre> <code class="language-cpp">Base* base = new Derived; delete base;</code></pre> <h2>运行时</h2> <p>运行时，Allocator初始化时“释放列表”中没有可重用的内存块。因此，第一次调用Allocate()将从内存池或者堆中获取内存空间。随着程序的执行，系统不断使用对象会造成分配器的波动。并且只有当释放列表无法提供内存时，新内存才会被申请和创建。最终，系统使用对象的实例会固定，因此每次内存分配将会使用已经存在的内存空间二不是再从内存池或者堆中申请。</p> <p>与使用内存管理器分配所有对象内存相比，Allocator分配器更加高效。内存分配时，内存指针仅仅是从“释放列表”中弹出，速度非常快。内存释放时也仅仅是将内存指针放入到“释放列表”当中，速度也十分快。</p> <h2>基准测试</h2> <p>在Windows PC上使用Allocator和全局堆内存的对比性能测试显示出Allocator的高性能。测试分配和释放20000个4096和2048大小的内存块来测试分配和释放内存的速度。测试的算法详见附件中的代码。</p> <table align="center"> <tbody> <tr> <td>Allocator</td> <td>Mode</td> <td>Run</td> <td>Benchmark Time (mS)</td> </tr> <tr> <td>Global Heap</td> <td>Debug Heap</td> <td>1</td> <td>1640</td> </tr> <tr> <td>Global Heap</td> <td>Debug Heap</td> <td>2</td> <td>1864</td> </tr> <tr> <td>Global Heap</td> <td>Debug Heap</td> <td>3</td> <td>1855</td> </tr> <tr> <td>Global Heap</td> <td>Release Heap</td> <td>1</td> <td>55</td> </tr> <tr> <td>Global Heap</td> <td>Release Heap</td> <td>2</td> <td>47</td> </tr> <tr> <td>Global Heap</td> <td>Release Heap</td> <td>3</td> <td>47</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>1</td> <td>19</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>2</td> <td>7</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>3</td> <td>7</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>1</td> <td>30</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>2</td> <td>7</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>3</td> <td>7</td> </tr> </tbody> </table> <p>使用调试模式执行时，Windows使用调试堆内存。调试堆内存添加额外的安全检查降低了性能。发布堆内存性能更好，因为不使用安全检查。通过在Visual Studio工程选项中，设置【调试】-【环境】中_NO_DEBUG_HEAP=1来禁止调试内存模式。</p> <p>全局调试堆内存模式需要平均1.8秒，是最慢的。释放对内存模式50毫秒左右，稍快。基准测试的场景非常简单，实际情况下，不同大小的内存块和随机的申请、释放可能产生不同的结果。然而，最简单的也最能说明问题。内存管理器比Allocator内存分配器慢，并且很大程度上依赖于平台的实现能力。</p> <p>内存分配器Allocator使用静态内存模式不依赖于堆内存的分配。一旦“释放列表”中含有内存块后，其执行时间大约为7毫秒。第一次耗时19毫秒用于将内存池中的内存防止到Allocator分配器中管理。</p> <p>Aloocator使用堆内存模式时，当“释放列表”中有可重用的内存后，其速度与静态内存模式一样快。堆内存模式依赖于全局堆来获取内存块，但是循环利用“释放列表”中的内存。第一次需要申请堆内存，耗时30毫秒。由于重用“释放列表”中的内存，之后的申请仅需要7毫秒。</p> <p>上面的基准测试结果表示，Allocator内存分配器更加高效，拥有7倍于Windows全局发布堆内存模式的速度。</p> <p>对于嵌入式系统，我使用Keil在ARM STM32F4 CPU（168Hz）上运行相同测试。由于资源限制，我将最大内存块数量降低到500，单个内存块大小降低到32和16字节。下面是结果：</p> <table align="center"> <tbody> <tr> <td>Allocator</td> <td>Mode</td> <td>Run</td> <td>Benchmark Time (mS)</td> </tr> <tr> <td>Global Heap</td> <td>Release</td> <td>1</td> <td>11.6</td> </tr> <tr> <td>Global Heap</td> <td>Release</td> <td>2</td> <td>11.6</td> </tr> <tr> <td>Global Heap</td> <td>Release</td> <td>3</td> <td>11.6</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>1</td> <td>0.85</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>2</td> <td>0.79</td> </tr> <tr> <td>Allocator</td> <td>Static Pool</td> <td>3</td> <td>0.79</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>1</td> <td>1.19</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>2</td> <td>0.79</td> </tr> <tr> <td>Allocator</td> <td>Heap Blocks</td> <td>3</td> <td>0.79</td> </tr> </tbody> </table> <p>基于ARM的基准测试显示，使用Allocator分配器的类性能快15倍。这个结果会让Keil堆内存的表现相形见绌。基准测试分配500个16字节大小的内存块进行测试。每个16字节大小的内存删除后申请500个32字节大小的内存块。全局堆内存耗时11.6毫秒，而且，在内存碎片化后，内存管理器可能会在没有安全检查的情况下耗时更大。</p> <h2>分配器决议</h2> <p>第一个决定是你是否需要使用分配器。如果你的项目不关心执行的速度和是否需要容错，那么你可能不需要自定义的分配器，全局堆分配管理器足够用了。</p> <p>另一方面，如果你需要考虑执行速度和容错管理，分配器会起到作用。你需要根据项目的需要选择分配器的模式。重要任务系统的设计可能强制要求使用全局堆内存。而动态分配内存可能更高效，设计更优雅。这种情况下，你可以在调试开发时使用堆内存模式获取内存使用参数，然后发布时切换到静态内存池模式避免内存分配带来的性能消耗。一些编译时的宏可用于模式的切换。</p> <p>另外，堆内存模式可能对应用更适合。该模式利用堆来获取新内存，同时阻止了堆碎片错误。当“释放列表”链接足够的内存块后更能加快内存的分配效率。</p> <p>在源代码中没有实现的涉及多线程的问题不在本文的讨论范围内。运行系统一会后，可以方便地使用GetlockCount函数和GetName函数获取内存块数量和名称。这些度量参数提供关于内存分配的信息。尽量多申请点内存，以便给分配盘一些弹性来避免内存耗尽。</p> <h2>调试内存泄漏</h2> <p>调试内存泄漏非常困难，原因是堆内存就像一个黑盒，对于分配对象的类型和大小是不可见的。使用Allocator，由于Allocator跟踪记录内存块的总数，内存泄漏检查变得简单一点。对每个分配器实例重复输出（例如输出到终端）GetBlockCount和GetName并比对它们的不同能让我们更好的了解分配器对内存的分配。</p> <h2>错误处理</h2> <p>C++中使用new_handler函数处理内存分配错误。如果内存管理器在申请内存时发生错误，用户的错误处理函数就会被调用。通过将用户的错误处理函数地址复制给new_handler，内存管理器就能调用用户自定义的错误处理程序。为了让Allocator类的错误处理机制与内存管理器保持一致，分配器也通过new_handler调用错误处理函数，集中处理所有的内存分配错误。</p> <pre> <code class="language-cpp">static void out_of_memory() { // new-handler function called by Allocator when pool is out of memory assert(0); } int _tmain(int argc, _TCHAR* argv[]) { std::set_new_handler(out_of_memory); ...</code></pre> <h2>限制</h2> <p>分配器类不支持数组对象的内存分配。为每一个对象创建分开的内存是无法保证的，因为new的多次调用不保证内存块的连续，但这又是数组所需要的。因此Allocator只支持固定大小内存块的分配，对象数组不支持。</p> <h2>移植问题</h2> <p>Allocator在静态内存池耗尽时调用new_handle指向的函数，这对于某些系统不合适。假设new_handle函数没返回，例如无尽的循环或者断言，调用这个函数不起任何作用。使用固定内存池时这无济于事。</p> <h2> </h2> <p> </p> <p>来自：http://developer.51cto.com/art/201701/528438.htm</p> <p> </p>