协作翻译 | 使用一个快速固定块的内存分配器来替换 malloc/free

• Download xallocator.zip - 9.7 KB

引言

自定义的固定区域（块）分配器是一个特别的内存管理策略专门用来解决全局堆栈的性能问题。 在 " 编写一个高效的固定块内存分配器 "这篇文章中, 我实现了一个可以减少碎片堆栈错误可能性的快速分配器类。那篇文章中的分配器类将会作为今天的主角—— X-分配器 的基石，替换系统的 malloc() 和 free() 函数。

和大部分固定块分配器不同的是， X-分配器 可以在预先不知道块大小和数量的前提下，以完全动态的方式运行。 X-分配器 也会为你提供所有的固定块管理方式。完美运行在任何PC或嵌入式设备上。此外，它还提供了内存的动态使用图可用于内存使用情况的统计。

在这边文章中，我使用可选择的固定内存块版本的xmalloc()和xfree来代替对应的C标准库mallc和free函数。首先，我简要解释下面的Allocator存储回收方法，接着介绍xallocator是如何工作的。

存储回收

基本的内存管理方案是回收在对象被分配期间获得地内存。一旦对象存储创建完成，它永远不会返回推中。相反，内存被回收，允许其他相同类型的对象重用此空间。我已经实现了一个叫做Allocator的类来解释这个技术。

当应用程序使用 Allocator 删除块之后，此对象的内存块被释放以便重用，但并不是直接释放到内存管理器。返回的内存块被保存至一个链表，我们叫它可用链表。此表可继续提供给其他相同类型对象使用。收到分配请求时， Allocator 先检查此可用链表中是否存在可用块。只有当链表中没有可用的块才创建新的块。取决于的 Allocator 期望的行为，存储可来自全局 堆 ，也可来自于具有以下三种操作模式的静态内存池。

1. 堆 块

2. 堆 池

3.静态池

堆 VS 池

当可用链表不能提供相应块时， Allocator 类可以从堆或者内存池创建一个新块。如果使用池，你必须预先指定创建对象的数目。 然后使用这些对象，一个足够大的可以处理最大数目实例的池即可创建。另一方面，从堆创建内存块并没有这方面的数量限制，只要存储允许，我们可创建尽可能多的对象。

堆块模式尽可能的从全局堆中分配一个新内存块给对象，来实现内存分配请求。而释放的时候，内存块被放置在一个可用链表以便后续重用。如果可用链表为空，则创建从堆产生的新内存块，使你摆脱对象数的限制。这个方法提供了动态的操作方式，因为内存块数可以在运行时扩展。其缺点是在内存块创建期带来的确定性执行损失。

堆池模式从全局堆创建一个单一的池来持有所有的块。 Allocator 对象被创建之后，使用操作符new来创建这个池。从此， Alloctor 可以从此池中提供内存块来完成分配。

静态池模式使用单个内存池来持有所有块。这个内存池基本上在静态内存池中。这个池不是由 Allocator 创建的，而是由类的使用者提供的。

堆池和静态池模式都提供一致的分配执行时间，因为内存管理器从不涉及到对单个内存块的获取。这使得新的操作快速而具有确定性。

Allocator构造函数控制者操作模式。

class Allocator { public:     Allocator(size_t size, UINT objects=0, CHAR* memory=NULL, const CHAR* name=NULL); ...

参考 " An efficient C++ fixed block memory allocator "获取更多关于 Allocator 信息。

xallocator模块有6个主要的API.

• xmalloc

• xfree

• xrealloc

• xalloc_stats

• xalloc_init

• xalloc_destroy

xmalloc等同于 malloc ，使用方法也与malloc相同。给定byte数，函数返回一个指向我们所请求的内存块大小的指针。

void* memory1=xmalloc(100);

这个内存块至少和用户请求的一样大，但是因为固定内存块分配实现的原因，实际上会大一些。这个额外分配内存被称为“宽松”，此“宽松”经过了微调块大小，以便浪费最小化。稍后文中我会解释。

xfree()等同于free()函数，只需给xfree传入之前通过xmalloc分配得到的指针来释放此内存。

xfree(memory1)；

xrealloc()和realloc操作类似，用于扩展或者收缩内存块的同时保留内存块的内容。

char* memory2 = (char*)xmalloc(24);     strcpy(memory2, "TEST STRING"); memory2 = (char*)xrealloc(memory2, 124); xfree(memory2);

xalloc_stats 把分配器使用情况统计输出到标准输出流，通过它可以窥探到内部有多少实例/块在使用，块大小，甚至更多。

在任何工作线程开始或嵌入式系统开始之前，xalloc_init必须被调用一次。在C++程序中，此函数会被自动调用。然而，某些情况下，特别是在嵌入式系统中，手动调用此函数更可取，从而避开此小内存开销涉及到自动调用xalloc_init()/xalloc_destory()机制。

当应用程序退出，任何动态分配的资源都将被通过 xalloc_destroy() 调用来清理。这个函数在C++程序终止时被自动调用。你千万别手动调用它，除非在C文件中使用了xallocator函数。

现在在C++程序中，几时调用 xalloc_init()和 xalloc_destroy() 可不是见容易的事。这里引入了静态对象问题。如果xalloc_destory函数过早被调用，而当程序退出时静态对象析构函数被调用到，此时可能还需要xallocator.如下例子：

class MyClassStatic { public:     MyClassStatic()      {          memory = xmalloc(100);      }     ~MyClassStatic()      {          xfree(memory);      } private:     void* memory; };

文件范围内创建此类的一个静态实例。

static MyClassStatic myClassStatic;

既然这个对象是静态的， MyClassStatic 构造函数会在main函数之前被调用。这是没有问题的，在下文的“移植问题”中将作解释。但是，析构函数在main退出之后被调用，如果处理不当，就产生问题。问题在于如何确定何时销毁xallocator动态分配的资源。如果在main函数退出之前调用 xalloc_destroy ,则 xallocator 已经被销毁，而当   ~MyClassStatic() 尝试调用 xfree 函数时就会带来bug.

这个解决方案的关键在于C++标准的保障：

“ 引述：

“在同一个翻译单元内，定义于命名空间范围并具有静态存储期的 动态初始化 对象应该按照他们在翻译单元中的定义顺序去完成初始化。”

”

也就是说，静态对象构造函数调用顺序和他们在文件中的定义顺序一致（翻译单元）。析构函数则以相反的顺序调用。因此， xallocator.h 定义了 XallocInitDestory 类并创建一个静态实例。

class XallocInitDestroy { public:     XallocInitDestroy();     ~XallocInitDestroy(); private:     static INT refCount; }; static XallocInitDestroy xallocInitDestroy;

构造函数记录了创建的静态实例对象数，并在首次构造时调用 xalloc_init 。

INT XallocInitDestroy::refCount = 0; XallocInitDestroy::XallocInitDestroy()  {      // Track how many static instances of XallocInitDestroy are created     if (refCount++ == 0)         xalloc_init(); }

在销毁最后一个实例时，析构函数自动调用xalloc_destroy()。

XallocDestroy::~XallocDestroy() {     // Last static instance to have destructor called?     if (--refCount == 0)         xalloc_destroy(); }

当翻译单元中包含 xallocator.h 时，先声明 xallocInitDestroy ，因为 # include 在用户代码之前。也就意味着，任何依赖 xallocator 的静态用户类声明在在#include“xallocator.h”之后。这样保证了所有用户静态类析构函数执行之后才去调用 XallocInitDestroy 函数。运用此技术， xalloc_destroy 可在程序退出时被安全调用，而不至于带来过早销毁 xallocator 的风险。

XallocInitDestroy是个空类，因此占一个byte大小。此功能给每一个包含了 xallocator .h的翻译单元带来一个byte的开销，以下情况例外：

1.没有应用程序的嵌入式系统不需要此技术。所有对XallocInitDestroy的引用都会安全的删除，并且xalloc_destroy永远不会被调用。

2.当C翻译单元中包含 xallocator， XallocInitDestroy静态实例是不会被创建的。

使用以下宏来自动打开或者关闭 xallocator 初始化和销毁工作。

#define AUTOMATIC_XALLOCATOR_INIT_DESTROY

对于PC或类似的具有高速RAM的系统来说，这一个byte是无关紧要的。作为回报，它确保了程序退出期间在静态类实例中的 xallocator 安全操作。

重载new和delete

为了使xallocator易于使用，我创建了一个宏在类中重载new/delete，在内存请求时路由到xmalloc/xfree函数。只需在你的类定义内任何地方添加此宏即可。

class MyClass  {     XALLOCATOR     // remaining class definition };

使用这个宏，用户类的new/delete函数通过重载new/delete来路由请求至xallocator。

// Allocate MyClass using fixed block allocator MyClass* myClass = new MyClass(); delete myClass;

代码实现

xallocator依赖多个allocator实例来管理固定块。每个allocator实例处理一个模块大小。类似allocator，xallocator是专门设计来操作于推块或静态池模式下。此模式由定义在xallocator.cpp中的 STATIC_POOLS 来控制。

#define STATIC_POOLS    // Static pools mode enabled

在推块模式，xallocator在运行期间基于请求的块大小，动态地创建allocator实例和新块。xallocator默认使用2的次方大小，比如8,16,32,64,128等。这种方式下，xallocator无需提前知道块大小，从而提供最大可能的灵活性。

MAX_ALLOCATORS控制着能够由xallocator动态创建地allocator类实例个数。依据你的目标程序需要适当增加或者减少即可。

静态模式下， xallocator 依赖静态 allocator 实例和静态内存池来满足内存请求。这是一个消除所有推访问与块大小之间的折中方案。并且池是固定大小，运行期间不可扩展的。

当使用静态池模式时， allocator 实例和内存池提前创建，如下所示。当然，每个 allocator 可以按需使用不同的 MAX_BLOCKS 值。全局推在此模式下永远不会被调用。

// Update this section as necessary if you want to use static memory pools #define MAX_ALLOCATORS    11 #define MAX_BLOCKS        32  AllocatorPool<char[8], MAX_BLOCKS> allocator8; AllocatorPool<char[16], MAX_BLOCKS> allocator16; AllocatorPool<char[32], MAX_BLOCKS> allocator32; AllocatorPool<char[64], MAX_BLOCKS> allocator64; AllocatorPool<char[128], MAX_BLOCKS> allocator128; AllocatorPool<char[256], MAX_BLOCKS> allocator256; AllocatorPool<char[396], MAX_BLOCKS> allocator396; AllocatorPool<char[512], MAX_BLOCKS> allocator512; AllocatorPool<char[768], MAX_BLOCKS> allocator768; AllocatorPool<char[1024], MAX_BLOCKS> allocator1024; AllocatorPool<char[2048], MAX_BLOCKS> allocator2048;  static Allocator* _allocators[MAX_ALLOCATORS] = {     &allocator8,     &allocator16,     &allocator32,     &allocator64,     &allocator128,     &allocator256,     &allocator396,     &allocator512,     &allocator768,     &allocator1024,     &allocator2048, };

隐藏固定块大小

当要删除内存时, xallocator 需要知道要删除块的大小，这样单元分配请求才会被路由到正确的  Allocator 对象实例中进行处理。不像 xmalloc() , xfree() 不需要大小仅仅用一个  void* 参数。 事实上  xmalloc() 是通过在请求上添加一个额外的4字节 (标准  sizeof(size_t) )在 一个未使用的内存块上隐藏了内存块大小 . 调用函数会获得一个指针指向那个被隐藏的而不是重写的内存块。

extern "C" void *xmalloc(size_t size) {     lock_get();      // Allocate a raw memory block      Allocator* allocator = xallocator_get_allocator(size);     void* blockMemoryPtr = allocator->Allocate(size);      lock_release();      // Set the block size within the raw memory block region     void* clientsMemoryPtr = set_block_size(blockMemoryPtr, size);     return clientsMemoryPtr; }

当 xfree() 被调用时大小就会从内存块中提取出来这时正确  Allocator 实例就会被调用以释放该内存块 

extern "C" void xfree(void* ptr) {     if (ptr == 0)         return;      // Extract the original client requested block size from the caller's block pointer     size_t size = get_block_size(ptr);      // Convert the client pointer into the original raw block pointer     void* blockPtr = get_block_ptr(ptr);      lock_get();      // Deallocate the block      Allocator* allocator = xallocator_get_allocator(size);     allocator->Deallocate(blockPtr);      lock_release(); }

移植问题

当锁已经在你的目标平台被实现了，那 xallocator 是线程安全的. 这份代码已经提供了windows上的锁得实现. 对于其他平台, 你需要在  xallocator.cpp 中实现以下4个函数来实现锁的功能:

• lock_init()

• lock_get()

• lock_release()

• lock_destroy()

在选择锁的时候, 应该选择系统中最快的锁，以确保 xallocator 操作在多线程环境中是最有效率. 如果你的系统只是单线程的，让上面4个函数空着就好。

根据 xallocator 的使用情况，它可能会在 main() 函数之前被调用. 这就意味着  lock_get() / lock_release() 可能在 lock_init() 之前被调用. 因为这时候系统还只是单线程的,在系统启动前，锁不是必须的. 但是, 如果 lock_init() 没有首先被调用 ， 应当确保  lock_get() / lock_release() 的表现是正确的. 例如,下面的例子会根据对 _xallocInitialized 的检查来确保正确的操作，它会在 lock_init() 被调用前都跳过锁。

static void lock_get() {     if (_xallocInitialized == FALSE)         return;      EnterCriticalSection(&_criticalSection);  }

减少冗余

xallocator返回的块大小可能大于实际请求的数目，这个增加的未使用部分内存称为冗余。比如一个33 bytes请求，xallocator返回一个64 bytes的块。这个新增的未使用内存（64-（33+4）=27 bytes）是个冗余。记住，在此请求中新增的4 bytes用于保存块大小。因此，如果客户请求64 bytes内存，实际分配128 bytes，因为我们需要68 bytes。

以2次幂递增额外分配块大小，可以提供更多块大小来减少浪费。运行你的程序，用一些临时调试代码配置你的xmalloc所请求的大小。然后增加分配器块大小来特别处理那些需要使用大量块的cases。

以下代码中，如果请求块大小介于257到396之间，则创建一个包含一块大小为396内存的allocator实例。类似的，介于513到768的请求则导致allocator处理768 bytes内存块。

// 基于这个大小，寻找下一个大于2次幂的值. // 增加 sizeof(size_t)到请求的块大小，在块内存区保存块大小 // 大部门块是2次幂的, // 但是一些常见allocator块大小可以明确定义来减少浪费.这给于程序调整能力. size_t blockSize; if (size > 256 && size <= 396)     blockSize = 396; else if (size > 512 && size <= 768)     blockSize = 768; else     blockSize = nexthigher<size_t>(size + sizeof(size_t));

因为应用内存使用的模式带来的冗余，你可以通过少量调整来减少存储浪费。如果不需要使用调整而可接受单独以2次幂来分配，则只需数行代码表述以上代码片段即可。

size_t blockSize; blockSize = nexthigher<size_t>(size + sizeof(size_t));

使用xalloc_stats可以方便查看到哪个allocators被使用最多的.

xallocator Block Size: 128 Block Count: 10001 Blocks In Use: 1 xallocator Block Size: 16 Block Count: 2 Blocks In Use: 2 xallocator Block Size: 8 Block Count: 1 Blocks In Use: 0 xallocator Block Size: 32 Block Count: 1 Blocks In Use: 0

Allocator VS xallocator

使用Allocator的优点是：allocator块大小就是对象的实际大小，并且最小块大小为4 bytes。而其缺点是allocator实例是私有的并只对那个类可用。这意味着固定块内存池不易于和其他类似大小块的实例共享。因为缺少在内存池之间的共享，这造成存储浪费。

另一方面，xallocator，使用一系列不同块大小来满足请求并且是线程安全的。其优点是：不同大小内存池可以通过xmalloc和xfree接口来实现共享。这可节省存储，特别是如果你为你的程序调整块大小。其缺点是：即便是有块大小调整，由于冗余的存在，有些存储浪费总会存在的。对于小型对象来说，最小的块大小为8 bytes，4 bytes给空链表指针，4 bytes来保存块大小。但是对于大量小型对象，这就会出现问题。

应用可以在同一个程序中，按照设计者觉得合适的方式，混合使用allocator和xallocator来使内存利用率最大化。

基准测试

在Windows PC上进行的xallocator VS 全局推基准性能测试显示它有多快。一个非常基本的测试实验说明了性能方面的改进。这个实验进行了至多2000 bytes的10000次随机大小块分配与释放。每一次测试都是单独进行并分别测量了分配和释放时间。

// Global heap test for (int i=0; i<MAX_ALLOCATIONS; i++) {     int blockSize = rand() % MAX_BLOCK_SIZE;     memoryBlocks[i] = malloc(blockSize); } for (int i=0; i<MAX_ALLOCATIONS; i++) {     free(memoryBlocks[i]); }  // xallocator heap blocks test for (int i=0; i<MAX_ALLOCATIONS; i++) {     int blockSize = rand() % MAX_BLOCK_SIZE;     memoryBlocks[i] = xmalloc(blockSize); } for (int i=0; i<MAX_ALLOCATIONS; i++) {     xfree(memoryBlocks[i]); }

分配时间单位为毫秒

全局推测如预期的那样最差的。出人意料的是，释放时间远远慢于分配时间。因为推块模式仅仅从推分配内存而从不释放，这个测试显示xallocator（至少在Windowns平台）没有引发性能损失。推分配看起来非常快，并通过回收块来避免释放可以节省大量时间。

堆块测试会连续运行三次。堆块模式依赖全局堆来获取新的块，之后会回收空闲的列表供之后使用。运行1（Run 1）显示了创建10000内存块的分配达到了24730微秒。然而，分配如此快是因为仅仅是将指针压到了栈内。在运行2（Run 2）里，大多数块都是有效的并且全局堆很少使用。因此，第二次10000的分配时间在14730到21685之间。在运行3（Run 3）中， xallocator 不需要使用堆，所有的分配来自先前分配的块，分配10000个块的时间为4876微秒。

从基准测试来看， xallocator 比全局堆有更高的效率和高出几个量级的速度。

总结

我曾经参与一个医疗设备的开发，这个医疗设备有一个商业化的大量使用堆内存的GUI库。内存请求的大小和频率无法预测或者控制。在一个医疗设备上如此不可控的使用堆内存的方式是很个禁忌，所以需要一个解决方案。很幸运，这个GUI库中有个方法可以用我们的实现替换 malloc 和 free 函数。 xallocator 解决了堆内存的速度和碎片化问题，使得这个GUI框架在这个产品上成为可行的方案。

如果你有一个应用程序真的需要反复申请堆内存，并引起了性能问题，或者你担心程序中的堆碎片问题，把 Allocator / xallocator 整合到你的程序里可能会解决这些问题。