高性能、灵活、跨平台的内存池
关于高性能、灵活、跨平台内存池的简要指南。
前言
通常，操作系统内存分配速度很快，尤其是在刚启动电脑时。但随着时间的推移，内存碎片会变得越来越严重，内存分配和访问会变得越来越慢。内存碎片是由不同大小的内存不断分配和释放引起的。
当内存碎片变得严重时，由于执行序列所需的内存地址非常分散，MMU（内存管理单元，硬件，CPU的一部分）会更频繁地触发缺页中断。这是内存访问缓慢的原因。
当内存碎片变得严重时，要找到最匹配内存分配大小的空闲内存块变得很困难。因为操作系统需要搜索更多的空闲内存块来找到一个大小最合适的。这是内存分配缓慢的原因。
解决上述问题的关键是尽可能避免内存碎片，并减少内存的分配和释放。解决方案是内存池。
对于内存池来说，加速内存分配不如加速内存访问重要。因为内存访问贯穿于程序始终。而内存分配则不那么频繁。在接下来的部分，我将介绍一种内存池，它通过分配大块内存来减少内存碎片，并通过不真正释放已分配的内存来加速内存分配。
引言
这是一个高性能、灵活、跨平台的内存池，根据MIT许可证发布。它对个人或商业用途免费，并已在许多生产环境中使用。
在过去的三年里，我一直从事交通管理计算机视觉系统的开发。在这类程序中，需要许多大块内存来缓存来自IP摄像头的图像并实时处理它们。如果我们每次需要分配大块内存时都使用malloc或new，随着程序的运行，我们会发现内存分配越来越慢，并且越来越容易失败。程序运行也变得更慢。
原因是不同大小的内存不断分配和释放造成的内存碎片。我找到了解决问题的关键，那就是内存池。我研究了Apache Portable Runtime中的内存池。发现它有点复杂，并且难以使其支持嵌入式平台。最重要的是，APR更擅长创建和销毁内存池，而不是在一个池中分配和释放内存。
实现
内存通过该内存池的节点（node）和切片（slice）进行管理。节点是一大块内存，切片是节点中的一小块内存。从该内存池分配的每个内存块都属于一个切片。
内存池中的所有切片大小都相同，因此该内存池更像是一个对象池。但是，我们可以通过使用具有不同切片大小的多个内存池实例来实现更灵活的内存池。
节点以链表的形式连接，可用切片也以链表的形式连接。当从内存池分配内存时。它首先检查是否存在空闲切片。如果存在，则取一个。如果不存在，则检查新分配的节点是否从未使用的切片。如果有，则从节点中取一个切片。如果没有，则分配一个新的节点并从中取一个切片。当释放内存块时，只需将其移到可用切片列表的头部。
这个内存池以树状结构组织。创建内存池时，我们可以通过使用指向父池的指针作为elr_mpl_create函数的第一个参数来指定其父内存池。当销毁一个内存池时，其子内存池也会被销毁。因此，当我们不需要这些内存池时，无需销毁内存池及其子内存池，只需销毁父内存池即可。如果在创建内存池时不指定父内存池，则该内存池的父内存池是全局内存池，该内存池在第一次调用elr_mpl_init时创建，并在最后一次调用elr_mpl_finalize时销毁。
内存池控制结构的内存使用是从全局内存池分配的。我们可以看到，在这个内存池的实现中，所有内存池实例都是全局内存池的子级或子子级。这意味着所有内存池将在最后一次调用elr_mpl_finalize时被销毁。这最大限度地减少了内存泄漏的可能性。
此内存池还支持多线程使用。如果我们希望它在多线程环境中工作，我们必须实现elr_mtx.h文件中定义的所有六个接口，并定义ELR_USE_THREAD。幸运的是，这是一项非常容易的工作，并且已经提供了Windows平台的实现。
在制作Windows实现时，我也考虑了Linux。因此，原子计数器（整数）类型（Linux的atomic_t，Windows的volatile LONG）和计数器值类型（Linux的int，Windows的LONG）是分开定义的。在Windows上没有原子类型，只有一个被volatile修饰的LONG（volatile LONG）。我们可以在LONG和volatile LONG之间进行赋值。但在Linux上，原子计数器（整数）类型定义如下。
typedef struct
{
volatile int counter;
}atomic_t;
int和atomic_t之间的赋值违反了C语言的语法。
用法
内存池的客户端原型定义如下。
typedef struct __elr_mpl_t
{
void* pool; /*!< the actual handler of internal memory pool object. */
int tag; /*!< the identity code of memory pool object. */
}
elr_mpl_t,*elr_mpl_ht;
#define ELR_MPL_INITIALIZER {NULL,0}
tag成员是内存池实例的标识码，用于判断elr_mpl_t变量是否仍然有效。稍后将对此进行解释。
这个内存池只有八个函数。
- int elr_mpl_init();
- elr_mpl_t elr_mpl_create(elr_mpl_ht fpool,size_t obj_size);
- int elr_mpl_avail(elr_mpl_ht pool);
- void* elr_mpl_alloc(elr_mpl_ht pool);
- size_t elr_mpl_size(void* mem);
- void elr_mpl_free(void* mem);
- void elr_mpl_destroy(elr_mpl_ht pool);
- void elr_mpl_finalize();
以下是源文件中的解释。
/*! \brief initialize memory pool module.
* \retval zero if failed.
*
* this function can invoke many times in one process.
* bear in mind that one should invoke elr_mpl_finalize
* the same times as invoke this function in one process
* when the process about to end.
*/
int elr_mpl_init();
/*! \brief create a memory pool.
* \param fpool the parent pool of the about to created pool.
* \param obj_size the size of memory block can alloc from the pool.
* \retval NULL if failed.
*
* in fact this memory pool is more like object pool.
*/
elr_mpl_t elr_mpl_create(elr_mpl_ht fpool,size_t obj_size);
/*! \brief verifies that a memory pool is valid or not.
* \param pool pointer to a elr_mpl_t type variable.
* \retval zero if invalid.
*/
int elr_mpl_avail(elr_mpl_ht pool);
/*! \brief alloc a memory block from a memory pool.
* \param pool pointer to a elr_mpl_t type variable.
* \retval NULL if failed.
*
* size of the memory block alloced is the second parameter
* of elr_mpl_create when create the pool.
*/
void* elr_mpl_alloc(elr_mpl_ht pool);
/*! \brief get the size of a memory block from a memory pool.
* \param mem pointer to a memory block from a memory pool.
* \retval size of the memory block.
*/
size_t elr_mpl_size(void* mem);
/*! \brief give back a memory block to it`s from memory pool.
*/
void elr_mpl_free(void* mem);
/*! \brief destroy a memory pool and it`s child pools.
*/
void elr_mpl_destroy(elr_mpl_ht pool);
/*! \brief finalize memory pool module.
*
* when finalize is finished all memory pools will be destroyed.
* make sure that when finalize is in process all memory pool is not in using.
* so it is recommend that elr_mpl_finalize invoked only in the end of a process.
*/
void elr_mpl_finalize();
一个简单的使用示例。
#include <stdio.h>
#include <stdlib.h>
#include "elr_mpl.h"
int main()
{
elr_mpl_t mypool = ELR_MPL_INITIALIZER;
elr_mpl_t mysubpool = ELR_MPL_INITIALIZER;
void* mem = NULL;
int len = 0;
elr_mpl_init();
mypool = elr_mpl_create(NULL,256);
printf("%s\n","create a memory pool: mypool.");
mysubpool = elr_mpl_create(&mypool,128);
printf("%s\n","create a sub memory pool of mypool, name is mysubpool.");
mem = elr_mpl_alloc(&mysubpool);
printf("%s\n","alloc a memory block form mysubpool.");
len = elr_mpl_size(mem);
printf("the memory block size is %d.\n",len);
elr_mpl_free(mem);
printf("give back the memory block to mysubpool.\n",len);
mem = elr_mpl_alloc(&mypool);
printf("%s\n","alloc a memory block form mypool.");
len = elr_mpl_size(mem);
printf("the memory block size is %d.\n",len);
elr_mpl_free(mem);
printf("give back the memory block to mypool.\n",len);
elr_mpl_destroy(&mypool);
printf("destroy mypool.\n",len);
printf("when mypool has destoryed, it`s sub pool, mysubpool, did %s destoryed.\n",
elr_mpl_avail(&mysubpool) == 0?"also":"not");
elr_mpl_finalize();
getchar();
return 0;
}
要点
为什么需要标识码
所有内存池的控制结构都来自全局内存池。假设我们有两个elr_mpl_t变量指向同一个内存池实例，其中一个elr_mpl_t变量调用了elr_mpl_destroy。然后，另一次elr_mpl_create调用可能会重用该内存池实例控制结构的内存。在这种情况下，我们仍然可以对另一个elr_mpl_t变量成功调用elr_mpl_alloc，但我们可能会分配一个不同大小的内存块。如果大小更大，可能没有问题。如果大小更小，则会发生内存访问冲突错误。
因此，我使用一个整数值来标识每个内存切片。每当一个内存切片从内存池中取出或归还给内存池时，我都会将该整数加一。所以，如果elr_mpl_t变量指向一个有效的内存池，那么tag成员就等于实际处理内部内存池对象的标识值（void* pool;）。
文件结构
该项目只有四个文件。elr_mpl.h和elr_mpl.c是核心实现文件，elr_mtx.h和elr_mtx.c用于多线程支持。如果您不需要多线程支持，只需将elr_mpl.h和elr_mpl.c添加到您的项目中。
评估版
为了评估这个内存池，我编写了一个测试程序。为了更好地模拟实际情况，我让内存分配、内存释放和内存访问随机发生，并记录总次数和总时间消耗。之后，总时间消耗除以总次数就是单次操作的耗时。
以下是我的模拟。
/* alloc_size the memory block size for allocating, access, freeing.*/
/* alloc_times total times of memory allocation operation. Need to be initialized to zero. */
/* alloc_clocks total time consumption of memory allocation operations. Need to be initialized to zero. */
/* other parameters ditto.*/
void mpl_alloc_free_access(size_t alloc_size,
int *alloc_times,
unsigned long *alloc_clocks,
int *free_times,
unsigned long *free_clocks,
int *access_times,
unsigned long *access_clocks)
{
int i = 0, j = 0, ri = 0;
unsigned long alloc_clks;
unsigned long free_clks;
unsigned long access_clks;
char *mem_stack[1000];
char stub = 0;
elr_mpl_t pool = elr_mpl_create(NULL,alloc_size);
if(elr_mpl_avail(&pool) != 0)
{
srand((unsigned)time(NULL));
for (j = 0; j < 1000; j++)
{
ri = rand()%100;
if(ri < 50)
{
alloc_clks = my_clock();
mem_stack[i] = (char*)elr_mpl_alloc(&pool);
*alloc_clocks += (my_clock()-alloc_clks);
(*alloc_times)++;
if(mem_stack[i] != NULL)
{
stub = 0;
access_clks = my_clock();
*(mem_stack[i]+(alloc_size-1)) = 0;
*access_clocks += (my_clock()-access_clks);
(*access_times)++;
}
i++;
}
else
{
if (i > 0)
{
i--;
free_clks = my_clock();
elr_mpl_free(mem_stack[i]);
*free_clocks += (my_clock()-free_clks);
(*free_times)++;
}
}
}
elr_mpl_destroy(&pool);
}
}
实现如下模拟函数是没有意义的。因为内存分配操作只在测量周期的第一次执行。所有其他的内存分配操作只是内部空闲内存块列表的节点删除操作。
//Array-test (Memory Pool):
for(unsigned int j = 0; j < TestCount; j++)
{
// ArraySize = 1000
char *ptrArray = (char *) g_ptrMemPool->GetMemory(ArraySize) ;
g_ptrMemPool->FreeMemory(ptrArray, ArraySize) ;
}
以下是我的计算机（Windows XP sp3，AMD Athlon II P340双核处理器，2G内存）生成的测量结果。
| size | alloc | alloc_elr | 免费 | free_elr | access | access_elr |
| 16 | 227.778 | 117.173 | 245.023 | 67.856 | 62.068 | 61.827 |
| 32 | 214.169 | 75.425 | 239.875 | 65.992 | 62.296 | 61.51 |
| 64 | 243.302 | 84.609 | 248.748 | 65.89 | 62.127 | 61.474 |
| 128 | 241.643 | 79.833 | 242.345 | 65.843 | 62.52 | 61.552 |
| 256 | 238.966 | 103.869 | 241.29 | 65.922 | 63.036 | 61.493 |
| 512 | 238.108 | 146.14 | 242.172 | 65.86 | 61.909 | 61.535 |
| 1024 | 338.797 | 138.467 | 351.727 | 65.932 | 64.49 | 61.486 |
| 2048 | 409.334 | 186.892 | 353.214 | 65.943 | 62.514 | 61.531 |
| 4096 | 524.18 | 290.163 | 791.648 | 66.21 | 64.514 | 61.524 |
| 8192 | 1686.29 | 504.569 | 1049.064 | 66.962 | 78.307 | 61.577 |
| 16384 | 2665.226 | 1146.425 | 1404.958 | 68.29 | 94.467 | 61.586 |
*_elr 表示elr_memory_pool的操作。X轴上从1到11的整数表示以下大小值。
{16,32,64,128,256,512,1024,2048,4096,8192,16384};
对于拥有多核CPU或多CPU的机器，应该将此测试程序绑定到某个核心运行。否则，时间测量是不准确的。因为我使用启动后的CPU滴答作为时间基准。
unsigned long my_clock()
{
__asm RDTSC
}
在实际程序中使用时，这个内存池的性能会比测试结果更好。在实际程序中，内存消耗在一段时间后会趋于稳定。届时，操作系统层面就没有内存分配了，只是重用内存池中的内存块。在测试程序中，始终存在操作系统级别的内存分配。
待办
该内存池已在许多生产环境中投入使用，其能力已经得到证明。尽管如此，仍有很大的改进空间。现在，每个内存池都有自己的互斥量对象，但在许多情况下这不是必需的。因此，至少有两个方面需要改进。第一，减少互斥量对象的消耗。第二，使其成为一个通用的内存池，类似于Apache内存池，可以从中分配许多固定大小的内存块。
历史
- 2014年3月30日：完成评估。
- 2014年3月27日：调整文章结构，添加前言段落。
- 2014年3月25日：首次发布。