内存池实现原理+(中文)

developerWorks图书频道:C++应用程序性能优化，第6章：内存池级别：中级冯宏华,高级软件工程师,IBM中国开发中心徐莹,开发经理,IBM中国软件开发中心程远,高级软件工程师,IBM软件开发中心汪磊,高级软件工程师,IBM中国开发中心2007年11月29日本书主要针对的是C++程序的性能优化，深入介绍C++程序性能优化的方法和实例。全书由4个篇组成，第1篇介绍C++语言的对象模型，该篇是优化C++程序的基础；第2篇主要针对如何优化C++程序的内存使用；第3篇介绍如何优化程序的启动性能；第4篇介绍了三类性能优化工具，即内存分析工具、性能分析工具和I/O检测工具，它们是测量程序性能的利器。本章首先简单介绍自定义内存池性能优化的原理，然后列举软件开发中常用的内存池的不同类型，并给出具体实现的实例。在此我们推出了本书的前言和第2、6章供大家在线浏览。更多推荐书籍请访问developerWorks图书频道。引言本书主要针对的是C++程序的性能优化，深入介绍C++程序性能优化的方法和实例。全书由4个篇组成，第1篇介绍C++语言的对象模型，该篇是优化C++程序的基础；第2篇主要针对如何优化C++程序的内存使用；第3篇介绍如何优化程序的启动性能；第4篇介绍了三类性能优化工具，即内存分析工具、性能分析工具和I/O检测工具，它们是测量程序性能的利器。本章首先简单介绍自定义内存池性能优化的原理，然后列举软件开发中常用的内存池的不同类型，并给出具体实现的实例。6.1自定义内存池性能优化的原理如前所述，读者已经了解到堆和栈的区别。而在编程实践中，不可避免地要大量用到堆上的内存。例如在程序中维护一个链表的数据结构时，每次新增或者删除一个链表的节点，都需要从内存堆上分配或者释放一定的内存；在维护一个动态数组时，如果动态数组的大小不能满足程序需要时，也要在内存堆上分配新的内存空间。6.1.1默认内存管理函数的不足利用默认的内存管理函数new/delete或malloc/free在堆上分配和释放内存会有一些额外的开销。系统在接收到分配一定大小内存的请求时，首先查找内部维护的内存空闲块表，并且需要根据一定的算法（例如分配最先找到的不小于申请大小的内存块给请求者，或者分配最适于申请大小的内存块，或者分配最大空闲的内存块等）找到合适大小的空闲内存块。如果该空闲内存块过大，还需要切割成已分配的部分和较小的空闲块。然后系统更新内存空闲块表，完成一次内存分配。类似地，在释放内存时，系统把释放的内存块重新加入到空闲内存块表中。如果有可回页首能的话，可以把相邻的空闲块合并成较大的空闲块。默认的内存管理函数还考虑到多线程的应用，需要在每次分配和释放内存时加锁，同样增加了开销。可见，如果应用程序频繁地在堆上分配和释放内存，则会导致性能的损失。并且会使系统中出现大量的内存碎片，降低内存的利用率。默认的分配和释放内存算法自然也考虑了性能，然而这些内存管理算法的通用版本为了应付更复杂、更广泛的情况，需要做更多的额外工作。而对于某一个具体的应用程序来说，适合自身特定的内存分配释放模式的自定义内存池则可以获得更好的性能。6.1.2内存池的定义和分类自定义内存池的思想通过这个池字表露无疑，应用程序可以通过系统的内存分配调用预先一次性申请适当大小的内存作为一个内存池，之后应用程序自己对内存的分配和释放则可以通过这个内存池来完成。只有当内存池大小需要动态扩展时，才需要再调用系统的内存分配函数，其他时间对内存的一切操作都在应用程序的掌控之中。应用程序自定义的内存池根据不同的适用场景又有不同的类型。从线程安全的角度来分，内存池可以分为单线程内存池和多线程内存池。单线程内存池整个生命周期只被一个线程使用，因而不需要考虑互斥访问的问题；多线程内存池有可能被多个线程共享，因此则需要在每次分配和释放内存时加锁。相对而言，单线程内存池性能更高，而多线程内存池适用范围更广。从内存池可分配内存单元大小来分，可以分为固定内存池和可变内存池。所谓固定内存池是指应用程序每次从内存池中分配出来的内存单元大小事先已经确定，是固定不变的；而可变内存池则每次分配的内存单元大小可以按需变化，应用范围更广，而性能比固定内存池要低。6.1.3内存池工作原理示例下面以固定内存池为例说明内存池的工作原理，如图6-1所示。图6-1固定内存池固定内存池由一系列固定大小的内存块组成，每一个内存块又包含了固定数量和大小的内存单元。如图6-1所示，该内存池一共包含4个内存块。在内存池初次生成时，只向系统申请了一个内存块，返回的指针作为整个内存池的头指针。之后随着应用程序对内存的不断需求，内存池判断需要动态扩大时，才再次向系统申请新的内存块，并把所有这些内存块通过指针链接起来。对于操作系统来说，它已经为该应用程序分配了4个等大小的内存块。由于是大小固定的，所以分配的速度比较快；而对于应用程序来说，其内存池开辟了一定大小，内存池内部却还有剩余的空间。例如放大来看第4个内存块，其中包含一部分内存池块头信息和3个大小相等的内存池单元。单元1和单元3是空闲的，单元2已经分配。当应用程序需要通过该内存池分配一个单元大小的内存时，只需要简单遍历所有的内存池块头信息，快速定位到还有空闲单元的那个内存池块。然后根据该块的块头信息直接定位到第1个空闲的单元地址，把这个地址返回，并且标记下一个空闲单元即可；当应用程序释放某一个内存池单元时，直接在对应的内存池块头信息中标记该内存单元为空闲单元即可。可见与系统管理内存相比，内存池的操作非常迅速，它在性能优化方面的优点主要如下。（1）针对特殊情况，例如需要频繁分配释放固定大小的内存对象时，不需要复杂的分配算法和多线程保护。也不需要维护内存空闲表的额外开销，从而获得较高的性能。（2）由于开辟一定数量的连续内存空间作为内存池块，因而一定程度上提高了程序局部性，提升了程序性能。（3）比较容易控制页边界对齐和内存字节对齐，没有内存碎片的问题。6.2一个内存池的实现实例本节分析在某个大型应用程序实际应用到的一个内存池实现，并详细讲解其使用方法与工作原理。这是一个应用于单线程环境且分配单元大小固定的内存池，一般用来为执行时会动态频繁地创建且可能会被多次创建的类对象或者结构体分配内存。本节首先讲解该内存池的数据结构声明及图示，接着描述其原理及行为特征。然后逐一讲解实现细节，最后介绍如何在实际程序中应用此内存池，并与使用普通内存函数申请内存的程序性能作比较。6.2.1内部构造内存池类MemoryPool的声明如下：回页首classMemoryPool{private:MemoryBlock*pBlock;USHORTnUnitSize;USHORTnInitSize;USHORTnGrowSize;public:MemoryPool(USHORTnUnitSize,USHORTnInitSize=1024,USHORTnGrowSize=256);~MemoryPool();void*Alloc();voidFree(void*p);};MemoryBlock为内存池中附着在真正用来为内存请求分配内存的内存块头部的结构体，它描述了与之联系的内存块的使用信息：structMemoryBlock{USHORTnSize;USHORTnFree;USHORTnFirst;USHORTnDummyAlign1;MemoryBlock*pNext;charaData[1];staticvoid*operatornew(size_t,USHORTnTypes,USHORTnUnitSize){return::operatornew(sizeof(MemoryBlock)+nTypes*nUnitSize);}staticvoidoperatordelete(void*p,size_t){::operatordelete(p);}MemoryBlock(USHORTnTypes=1,USHORTnUnitSize=0);~MemoryBlock(){}};此内存池的数据结构如图6-2所示。图6-2内存池的数据结构6.2.2总体机制此内存池的总体机制如下。（1）在运行过程中，MemoryPool内存池可能会有多个用来满足内存申请请求的内存块，这些内存块是从进程堆中开辟的一个较大的连续内存区域，它由一个MemoryBlock结构体和多个可供分配的内存单元组成，所有内存块组成了一个内存块链表，MemoryPool的pBlock是这个链表的头。对每个内存块，都可以通过其头部的MemoryBlock结构体的pNext成员访问紧跟在其后面的那个内存块。（2）每个内存块由两部分组成，即一个MemoryBlock结构体和多个内存分配单元。这些内存分配单元大小固定（由MemoryPool的nUnitSize表示），MemoryBlock结构体并不维护那些已经分配的单元的信息；相反，它只维护没有分配的自由分配单元的信息。它有两个成员比较重要：nFree和nFirst。nFree记录这个内存块中还有多少个自由分配单元，而nFirst则记录下一个可供分配的单元的编号。每一个自由分配单元的头两个字节（即一个USHORT型值）记录了紧跟它之后的下一个自由分配单元的编号，这样，通过利用每个自由分配单元的头两个字节，一个MemoryBlock中的所有自由分配单元被链接起来。（3）当有新的内存请求到来时，MemoryPool会通过pBlock遍历MemoryBlock链表，直到找到某个MemoryBlock所在的内存块，其中还有自由分配单元（通过检测MemoryBlock结构体的nFree成员是否大于0）。如果找到这样的内存块，取得其MemoryBlock的nFirst值（此为该内存块中第1个可供分配的自由单元的编号）。然后根据这个编号定位到该自由分配单元的起始位置（因为所有分配单元大小固定，因此每个分配单元的起始位置都可以通过编号分配单元大小来偏移定位），这个位置就是用来满足此次内存申请请求的内存的起始地址。但在返回这个地址前，需要首先将该位置开始的头两个字节的值（这两个字节值记录其之后的下一个自由分配单元的编号）赋给本内存块的MemoryBlock的nFirst成员。这样下一次的请求就会用这个编号对应的内存单元来满足，同时将此内存块的MemoryBlock的nFree递减1，然后才将刚才定位到的内存单元的起始位置作为此次内存请求的返回地址返回给调用者。（4）如果从现有的内存块中找不到一个自由的内存分配单元（当第1次请求内存，以及现有的所有内存块中的所有内存分配单元都已经被分配时会发生这种情形），MemoryPool就会从进程堆中申请一个内存块（这个内存块包括一个MemoryBlock结构体，及紧邻其后的多个内存分配单元，假设内存分配单元的个数为n，n可以取值MemoryPool中的nInitSize或者nGrowSize），申请完后，并不会立刻将其中的一个分配单元分配出去，而是需要首先初始化这个内存块。初始化的操作包括设置MemoryBlock的nSize为所有内存分配单元的大小（注意，并不包括MemoryBlock结构体的大小）、nFree为n-1（注意，这里是n-1而不是n，因为此次新内存块就是为了满足一次新的内存请求而申请的，马上就会分配一块自由存储单元出去，如果设为n-1，分配一个自由存储单元后无须再将n递减1），nFirst为1（已经知道nFirst为下一个可以分配的自由存储单元的编号。为1的原因与nFree为n-1相同，即立即会将编号为0的自由分配单元分配出去。现在设为1，其后不用修改nFirst的值），MemoryBlock的构造需要做更重要的事情，即将编号为0的分配单元之后的所有自由分配单元链接起来。如前所述，每个自由分配单元的头两个字节用来存储下一个自由分配单元的编号。另外，因为每个分配单元大小固定，所以可以通过其编号和单元大小（MemoryPool的nUnitSize成员）的乘积作为偏移值进行定位。现在唯一的问题是定位从哪个地址开始