对小内存块快速有效的内存分配器

作者 znrobinson   翻译 郭世龙

介绍

     动态内存分配是件有趣的事。大多数人在调用malloc/free不会考虑发生的与之相关的代价。提到基于堆的内存分配，为了能够重新申请和重新使用这些内存，内存块的管理必须进行大量的薄记，而这中薄记是要花费CPU周期的。我们尝试写高效的代码时候，首要的规则是：尽量避免触及分配器。但是存在malloc/free的一个原因是，它像其他函数一样也是一个工具，只是它需要被适当的使用。但是您能低成本地使用它吗？

      很多人和我自己一样接手这个小小的挑战，以展示大量xxx驱动下的一个成熟男人所做的工作。目标是写一个快速的，xxx率的小内存块分配器并且有机会获得在被人面前滔滔不绝吹牛的权利。那么，好...这不是大男子气概的姿态，根本原因是我们工作的UI工具箱以惊人的速度分配了惊人的内存数量，其中包括非常多的小于1024byte的小内存请求。对于谁更牛一些，我们有着很绅士的不同意见。嗯...我的意思是谁能够写出跟好的分配器。既然竞争，那么基本的规则是:

       具有如下声明的两个函数：void* alloc(long size); void free(void *p)；

       必须支持>1024的分配（速度和效率测试是基于<=1024的分配）；

       必须是“自然的”对齐到下一个2的幂，{zd0}8byte对齐；

       NULL释放时不能崩溃；

       必须支持0分配（返回一个有效的指针）；

       必须调用blockalloc（）/blockfree（）（实质上是malloc和free）来构建池分配。

得分的主要点是速度和效率，通过在评估过程中你有多少的内存浪费来衡量效率的缺乏。

      效率=你的分配器请求的内存量/你从blockalloc请求的内存量

给定效率，得分基本计算如下：

       分数=时间(单位毫秒)/（效率×效率×效率）

得分{zd1}者胜。从这里可以看出，不尽可能的高效则会有很大的惩罚。在我们的效果和效率测试中，我的分配器能够击败Visual C的malloc/free,速度上提高25倍效率提高13%。

 尽管这个实现相当的快速，但是不主张将这个建立为最快的可能的小块分配器。我有很多想法关于怎样使它更快并且我确信这之外还有实现能击败它。但是，有趣的是它击败微软的箱外（out-of-the-box）实现是多么的容易啊。并且对与有兴趣进一步开发它的你们，这是一个好的起点。

    一句很好的信条是使事情尽可能的简单，只在需要的时候才引入复杂。我的前两个分配器都是复杂的怪兽，{zd0}的原因是我将焦点集中在了错误的问题上了（例如，最小化块头尺寸等等）。{zh1}，我的分配器变成了相当简单本质上是一个固定块分配器，它管理者129个分离的堆，每个堆管理一个具体的固定分配大小从4byte开始然后是8byte然后以8byte增长到1024byte。技术上，这是一个子分配器；他使用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];

 {dy}行处理试图分配0byte的特例；在这种情况中，你处理它为分配1byte，通过改变大小为1来。在下一行，初始化索引bdIndex值为-1，并且如果分配在你的目标范围之内（<=1024)，那么查找表用大小作为表的偏移量决定使用129个堆中的哪个。

  如果分配请求大于1024，index和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函数在可提供的空闲块中分配内存。每一个块都有很多大块，每一个大块都足够大到满足一次分配请求。在block数据结构中，在block中维护着一个空闲大块(chunck)的单链表。

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;
}

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

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);
}

发表于 @ 2008年06月27日　15:49:00 | | | |