用于加速小内存块的快速高效分配器

• 下载源代码文件 - 3.6 KB

引言

动态内存分配是一件有趣的事情。我的意思是，我认为大多数人在调用 malloc/free 时都不会考虑与之相关的开销。当涉及堆内存分配时，管理内存块以便内存可以被回收和重用会涉及大量的记账工作，而这些记账会消耗 CPU 周期。编写快速代码的第一条规则是：尽量少接触分配器。但是 malloc/free 的存在是有原因的，它与其他工具一样，只是需要正确使用。但是我们能降低它的使用成本吗？

我和我的几个朋友，在一种令人震惊的表现中展现了过多的睾酮会驱使成年男性做出什么事情，我们接受了小内存块的挑战。目标是编写最快、最“高效”的小内存块分配器，并获得与其他所有人相比永恒的吹嘘资本。好吧……这不仅仅是男子气概的姿态，之所以提出这个问题，是因为我们都在从事的一个 UI 工具包以惊人的速度分配了惊人数量的内存，其中大部分是小于 1024 字节的小内存请求。我们只是在谁更“大”……嗯……我的意思是，谁能写出更好的分配器方面有一些君子之争。因此，有了这场比赛及其规则。

• 两个函数签名如下：void* alloc(long size); 和 void free(void*p);
• 必须支持 > 1024 的分配（速度和效率测试在 <= 1024 的分配上进行）
• 必须“自然地”对齐到下一个 2 的幂，最大对齐 8 字节
• NULL free 时不能崩溃
• 必须支持分配 0（返回一个有效指针）
• 必须调用 blockalloc()/blockfree()（本质上是 malloc 和 free）来分配“底层”池内存

评分的主要组成部分是速度和效率，效率低下通过基准测试中的浪费量来衡量。

efficiency = (amount of memory requested of your allocator) / 
             (amount of memory that you have requested from blockalloc)

考虑到效率，分数基本上计算如下：

score = (time in ms) / (efficiency * efficiency * efficiency)

分数越低越好。从这里可以看出，未能做到“尽可能高效”会受到很高的惩罚。在我们的性能和效率测试中，我的分配器在速度上比 Visual C 的 malloc/free 快 25 倍，在效率上高 13% 以上。

本文无意宣称这是最快的小内存块分配器，尽管此实现已非常快速。我对如何使其更快有很多想法，而且我相信市面上肯定有比这更好的实现。但令人惊讶的是，击败 Microsoft 的开箱即用实现如此容易，对于那些有兴趣进一步研究的人来说，这是一个很好的起点。

一个好的格言是：尽可能使事物保持简单，只有在需要时才引入复杂性。我最初的几个分配器非常复杂，这主要是因为我的注意力放在了错误的问题上（例如，最小化块头大小等……）。最终，我的分配器变得极其简单，本质上是一个固定块分配器，管理着 129 个独立的堆。每个堆管理一个特定的固定分配大小，从 4 字节开始，然后是 8 字节，然后以 8 字节的增量递增到 1024 字节。从技术上讲，这是一个子分配器；它使用 malloc 和 free 来分配/释放更大的内存块。此分配器管理这些内存块并用于分配更小的内存块。在我们的测试中，此分配器通过比通用的 malloc/free 更有效地管理这些较小的分配而获胜。

固定块分配器，顾名思义，就是只能分配固定或给定大小块的分配器。由于只需要处理给定大小的块，因此管理内存所需的代码量和数据结构的复杂性得以最小化，这直接转化为性能。

分配内存

让我们开始查看 rtAllocator::alloc 方法。

void* rtAllocator::alloc(long ls);

首先要做的就是确定 129 个独立堆中的哪一个适合满足请求。首先，检查分配的大小（ls），看它是否 > 1024 字节。如果请求大于 1024 字节，则请求直接传递给通用分配器（malloc），因为我们不关心这个大小的分配。如果请求的大小 <= 1024，那么我们需要确定 129 个固定大小堆中的哪一个应该用于满足请求。为了快速有效地完成此操作，使用了一个 1024 个元素的查找表。此查找表已初始化一个数字，该数字指示应该使用 129 个堆中的哪一个来满足请求。看看这方面的代码：

void* rtAllocator::alloc(long ls)
{
  if (ls == 0) ls = 1;
  int bdIndex = -1;
  if (ls <= 1024) bdIndex = mBDIndexLookup[ls];

第一行用于处理尝试分配零字节的特殊情况；在这种情况下，我们将其视为分配一字节，将大小更改为一。在下一行中，我们将索引 bdIndex 初始化为 -1，如果分配在我们的目标范围内（<= 1024），则使用查找表，以大小作为表的偏移量，以确定使用 129 个堆中的哪一个。

如果分配请求大于 1024，则索引 bdIndex 将为 -1，请求将被简单地传递给通用分配器。给定以下代码：

if (bdIndex < 0)
{
  // Not handling blocks of this size throw to blockalloc
  INCALLOCCOUNTER(bdCount);
  return ALLOCJR_ALLOC(ls);
}

注意：宏 ALLOCJR_ALLOC 用于包装 malloc，以便我们可以跟踪和记录分配统计信息。ALLOCJR_FREE 用于类似目的，包装对 free 函数的调用。

此时，我们知道我们正在处理（<=1024）的分配，并且我们知道将使用 129 个固定大小堆中的哪一个来满足请求。因此，下一步是检查我们是否已经有一个具有足够空间的块来满足请求。每个堆都维护一个空闲块的双向链表（至少有一个额外的分配空间）。如果没有空闲块，我们就分配一个块（使用 malloc），并将其链接到我们的空闲块链表中，代码如下：

if (!mFreeBlocks[bdIndex])
{
  INCBLOCKCOUNTER();
  block* b = (block*)ALLOCJR_ALLOC(
    block::getAllocSize(bd[bdIndex].fixedAllocSize, bd[bdIndex].chunks));
  if (b)
  {
    b->init(bd[bdIndex].fixedAllocSize, bdIndex, bd[bdIndex].chunks);

    addBlockToArray(b);
    mFreeBlocks[bdIndex] = b;
  }
}

此时，应该至少有一个块可用于满足分配请求。然后，分配请求被转发到 block::alloc 以从可用空闲块中分配内存。每个块有多个“块”（chunk），每个块足够大以满足一次分配请求。在块数据结构中，维护着一个单向链表，该链表位于块的内部，用于存储空闲的“块”。

为了避免在初始化新分配的块时设置链表的开销，维护了一个 fence 指针，该指针指向第一个未初始化的块。在分配内存时，我们首先查看链表，看看它是否包含任何空闲块。如果没有，我们通过检查 fence 指针来查看块中是否还有尚未包含在空闲块列表中的块。如果还有空间，我们就将 mInitCursor 递增到下一个块，并使用 mInitCursor 之前指向的块。

inline void* alloc()
{
  void* result;

  if (mFreeChunk)
  {
    result = mFreeChunk;
    mFreeChunk = (void**)*mFreeChunk;
  }
  else
  {
    result = mInitCursor;
    mInitCursor += mFixedAllocSize;
  }

  mAllocCount++;
  return result;
}

从 block::alloc 返回后，我们需要检查块是否已满。这通过调用 block::isFull 来实现。如果块已满，我们就将其从空闲块的双向链表中删除，以便在查找未来请求的空间时不再考虑它。当块从空闲列表中删除时，块的 mNextFreeBlock 指针会被赋一个哨兵值，这样我们就可以轻松确定该块已满。给定以下代码：

block *b = mFreeBlocks[bdIndex];

if (b->mNextFreeBlock != ALLOCJR_FULLBLOCK && b->isFull())
{
  // Unlink from freelist
  if (b->mNextFreeBlock)
  {
    b->mNextFreeBlock->mPrevFreeBlock = b->mPrevFreeBlock;
  }
  if (b->mPrevFreeBlock)
  {
    b->mPrevFreeBlock->mNextFreeBlock = b->mNextFreeBlock;
  }
  mFreeBlocks[bdIndex] = b->mNextFreeBlock;
  // special value means removed from free list
  b->mNextFreeBlock = ALLOCJR_FULLBLOCK; 
  b->mPrevFreeBlock = ALLOCJR_FULLBLOCK;
}

此时，我们已成功分配了请求大小的块。现在我们已经完成了内存分配过程，接下来我将带您了解内存释放的过程。

释放内存

内存释放过程以调用 rtAllocator::free 开始。

void rtAllocator::free(void* p)

此方法首先检查是否收到了一个空指针引用；如果是，我们按如下方式返回：

if (!p) return;

如果指针非空，则会检查内存是我们管理的还是通过传递给 malloc 获取的。为了做到这一点，我们对维护的块指针数组进行二分查找，看看它是否是我们的。这通过调用以下函数来完成：

block* b = findBlockInArray(p);

如果该块是我们的，则 b 将非空，否则我们知道我们正在释放的指针不是我们的，并直接将其传递给 free。如果是我们的，则对返回的块调用 block::free。在 block::free 方法中，我们只是将“块”返回到块内的空闲列表中，以便该块可以被重用。

inline void free(void* p)
{
  void **pp = (void**)p;
  *pp = mFreeChunk;
  mFreeChunk = (void**)p;
  mAllocCount--;
}

在此函数的第一行中，我们将指针强制转换为 void **，这使得我们可以轻松地将当前的链表头指针写入块的前面。然后，我们在第二行中执行此操作。在第三行中，通过将头指针设置为指向新插入的块，完成将块插入到块的空闲列表中的操作。最后，我们递减当前块中已分配块的数量计数器。从调用 block::free 返回后，我们仍然需要进行一些其他检查才能完成。首先，我们检查最后一个 block::free 调用是否使块变空。我们这样做如下：

if (b->isEmpty())

如果块现在完全为空，我们就将块从空闲块的双向链表中解除链接，并通过调用 free 并传入该块，将块返回给系统，如下所示：

if (b->isEmpty())
{
  // Unlink from freelist and return to the system
  if (b->mNextFreeBlock)
  {
    b->mNextFreeBlock->mPrevFreeBlock = b->mPrevFreeBlock;
  }
  if (b->mPrevFreeBlock)
  {
    b->mPrevFreeBlock->mNextFreeBlock = b->mNextFreeBlock;
  }
  if (mFreeBlocks[b->mBDIndex] == b) 
    mFreeBlocks[b->mBDIndex] = b->mNextFreeBlock;

  removeBlockFromArray(b);

  DECBLOCKCOUNTER();
  ALLOCJR_FREE(b);
}

如果块不为空，我们确保块包含在双向空闲块列表中，因为我们现在知道该块中至少有一个空闲块。通过将 mNextFreeBlock 成员与无效指针常量 ALLOCJR_FULLBLOCK 进行比较来进行此检查，ALLOCJR_FULLBLOCK 在块满时会被赋给 mNextFreeBlock 块；如果此检查成功，则按如下方式将其重新链接到列表中：

// need to see if block is not in free list if not add it back
if (b->mNextFreeBlock == ALLOCJR_FULLBLOCK)
{
  b->mPrevFreeBlock = NULL;
  b->mNextFreeBlock = mFreeBlocks[b->mBDIndex];
  if (mFreeBlocks[b->mBDIndex]) 
  mFreeBlocks[b->mBDIndex]->mPrevFreeBlock = b;
  mFreeBlocks[b->mBDIndex] = b;
}

此时，内存已回收并可重用。

结论

总而言之，我想说编写这个分配器是一个很有趣的过程，我希望您也喜欢阅读我关于它是如何工作的描述。玩得开心看看代码吧！

作者在 http://www.liquidthought.com 维护着一个博客，里面有更多编程技巧、代码片段和软件。