自定义分配器性能

Question

我正在构建一个 AVL 树 class，它将具有固定的最大项目数。所以我想与其单独分配每个项目，不如一次分配整个块，并在需要时使用位图分配新内存。

我的分配/解除分配代码：

avltree::avltree(UINT64 numitems)
{
  root = NULL;

  if (!numitems)
    buffer = NULL;
  else {
    UINT64 memsize = sizeof(avlnode) * numitems + bitlist::storagesize(numitems);
    buffer = (avlnode *) malloc(memsize);
    memmap.init(numitems, buffer + numitems);
    memmap.clear_all();
    freeaddr = 0;
  }
}

avlnode *avltree::newnode(keytype key)
{
  if (!buffer)
    return new avlnode(key);
  else 
  {
    UINT64 pos;
    if (freeaddr < memmap.size_bits)
      pos = freeaddr++;
    else
      pos = memmap.get_first_unset();
    memmap.set_bit(pos);
    return new (&buffer[pos]) avlnode(key);
  }
}

void avltree::deletenode(avlnode *node)
{
  if (!buffer)
    delete node;
  else
    memmap.clear_bit(node - buffer);
}

为了使用标准的新建/删除，我必须用 numitems == 0 构造树。为了使用我自己的分配器，我只传递了项目数。所有函数都内联以获得最佳性能。

一切都很好，但我自己的分配器比新建/删除慢了大约 20%。现在，我知道内存分配器是多么复杂，代码无法运行比数组查找 + 一位设置更快，但这正是这种情况。更糟糕的是：即使我从中删除了所有代码，我的释放器也变慢了？！？

当我检查程序集输出时，我的分配器的代码路径充满了处理位图、avltree 或 avlnode 的 QWORD PTR 指令。 new/delete路径好像没有太大区别

例如avltree::newnode的汇编输出：

;avltree::newnode, COMDAT
mov     QWORD PTR [rsp+8], rbx
push    rdi
sub     rsp, 32

;if (!buffer)
cmp     QWORD PTR [rcx+8], 0
mov     edi, edx
mov     rbx, rcx
jne     SHORT $LN4@newnode

;  return new avlnode(key);
mov     ecx, 24
call    ??2@YAPEAX_K@Z         ; operator new
jmp     SHORT $LN27@newnode

;$LN4@newnode:
;else {
;  UINT64 pos;
;  if (freeaddr < memmap.size_bits)
mov     r9, QWORD PTR [rcx+40]
cmp     r9, QWORD PTR [rcx+32]
jae     SHORT $LN2@newnode

;    pos = freeaddr++;
lea     rax, QWORD PTR [r9+1]
mov     QWORD PTR [rcx+40], rax

;  else
jmp     SHORT $LN1@newnode
$LN2@newnode:

;    pos = memmap.get_first_unset();
add     rcx, 16
call    ?get_first_unset@bitlist@@QEAA_KXZ ; bitlist::get_first_unset
mov     r9, rax

$LN1@newnode:
; memmap.set_bit(pos);
mov     rcx, QWORD PTR [rbx+16]                    ;data[bindex(pos)] |= bmask(pos);
mov     rdx, r9                                    ;return pos / (sizeof(BITINT) * 8);
shr     rdx, 6
lea     r8, QWORD PTR [rcx+rdx*8]                  ;data[bindex(pos)] |= bmask(pos);
movzx   ecx, r9b                                   ;return 1ull << (pos % (sizeof(BITINT) * 8));
mov     edx, 1
and     cl, 63
shl     rdx, cl

;   return new (&buffer[pos]) avlnode(key);
lea     rcx, QWORD PTR [r9+r9*2]
; File c:\projects\vvd\vvd\util\bitlist.h
or      QWORD PTR [r8], rdx                        ;data[bindex(pos)] |= bmask(pos)

; 195  :     return new (&buffer[pos]) avlnode(key);
mov     rax, QWORD PTR [rbx+8]
lea     rax, QWORD PTR [rax+rcx*8]
; $LN27@newnode:
test    rax, rax
je      SHORT $LN9@newnode

; avlnode constructor; 
mov     BYTE PTR [rax+4], 1
mov     QWORD PTR [rax+8], 0
mov     QWORD PTR [rax+16], 0
mov     DWORD PTR [rax], edi

; 196  :   }
; 197  : }
; $LN9@newnode:
mov     rbx, QWORD PTR [rsp+48]
add     rsp, 32                        ; 00000020H
pop     rdi
ret     0
?newnode@avltree@@QEAAPEAUavlnode@@H@Z ENDP             ; avltree::newnode
_TEXT   ENDS

当我使用默认/自定义分配器构造我的 avltree 时，我已经多次检查了编译输出，并且在这个特定的代码区域中它保持不变。我已经尝试删除/替换所有相关部分，但没有明显效果。

老实说，我希望编译器能够内联所有这些，因为变量很少。我希望除了 avlnode 对象本身之外的所有东西都放在寄存器中，但事实似乎并非如此。

然而，速度差异是显而易见的。我并不是每插入 1000 万个节点就调用 3 秒，但我希望我的代码比通用分配器（2.5 秒）更快，而不是更慢。这尤其适用于较慢的释放器，即使从中剥离所有代码，释放器也较慢。

为什么变慢了？

编辑：谢谢大家对此的出色想法。但我想再次强调，问题不在于我的分配方法，而在于使用变量的次优方式：整个 avltree class 仅包含 4 个 UINT64 变量，位列表只有 3.

~~然而，尽管如此，编译器并未将其优化为寄存器。它坚持使用慢几个数量级的 QWORD PTR 指令。这是因为我正在使用 classes 吗？我应该转向 C / 纯变量吗？~~ 从头开始。愚蠢的我。我也有所有的 avltree 代码，东西不能在寄存器中。

此外，我完全不知道为什么我的释放器仍然会变慢，即使我从中删除了所有代码。然而 QueryPerformanceCounter 告诉我的正是这一点。甚至认为是疯狂的：同样的解除分配器也被调用用于新的/删除代码路径并且它必须删除节点......它不必为我的自定义分配器做任何事情（当我剥离代码时）。

编辑2： 我现在已经完全删除了位列表并通过单链表实现了免费 space 跟踪。 avltree::newnode 函数现在更加紧凑（我的自定义分配器路径有 21 条指令，其中 7 条是处理 avltree 的 QWORD PTR 操作，4 条用于 avlnode 的构造函数）。 1000 万次分配的最终结果（时间）从约 3 秒减少到约 2.95 秒。

编辑3： 我还重写了整个代码，现在一切都由单链表处理。现在 avltree class 只有两个相关成员：root 和 first_free。速度差异仍然存在。

编辑4： 重新排列代码并查看性能数据，这些是最有帮助的：

正如所有贡献者所指出的那样，其中包含位图实在是太糟糕了。已删除以支持单链接空闲槽列表。
代码局部性：通过将依赖函数（avl 树处理函数）添加到局部函数中 class 而不是全局声明它们有助于提高约 15% 的代码速度（3 秒 --> 2.5 秒）
avlnode 结构大小：只需在结构声明之前添加 #pragma pack(1) 即可将执行时间进一步减少 20%（2.5 秒 --> 2 秒）

编辑 5：

由于这个问题似乎很受欢迎，所以我在下面发布了最终的完整代码作为答案。我对它的表现很满意。

Answer 1

很难确定要研究的代码如此之少，但我敢打赌参考的位置。带有元数据的位图与分配的内存本身不在同一缓存线上。 get_first_unset 可能是线性搜索。

Answer 2

Now, I know how complex memory allocators are, there's no way that code can run faster than an array lookup + one bit set, but that is exactly the case here.

这几乎不正确。一个体面的分桶低碎片堆是 O(1)，具有非常低的常数时间（并且有效地为零额外 space 开销）。我以前见过一个版本减少到 ~18 条 asm 指令（有一个分支）。这比你的代码少很多。请记住，堆总体上可能非常复杂，但通过它们的快速路径可能真的非常快。

Answer 3

你的方法只在一个块中分配原始内存，然后必须为每个元素做一个新的放置。将它与位图中的所有开销结合起来，默认的 new 分配在假设空堆的情况下胜过你的分配也就不足为奇了。

为了在分配时获得最大的速度提升，您可以在一个大数组中分配整个对象，然后从那里分配给它。如果你看一个非常简单和做作的基准：

struct test_t {
    float f;
    int i;
    test_t* pNext;
};

const size_t NUM_ALLOCS = 50000000;

void TestNew (void)
{
    test_t* pPtr = new test_t;

    for (int i = 0; i < NUM_ALLOCS; ++i)
    {
        pPtr->pNext = new test_t;
        pPtr = pPtr->pNext;
    }

}

void TestBucket (void)
{
    test_t* pBuckets = new test_t[NUM_ALLOCS + 2];
    test_t* pPtr = pBuckets++;

    for (int i = 0; i < NUM_ALLOCS; ++i)
    {
        pPtr->pNext = pBuckets++;
        pPtr = pPtr->pNext;
    }

}

在具有 50M 分配的 MSVC++ 2013 上使用此代码 TestBucket() 优于 TestNew() 超过 x16 倍（130 与 2080 毫秒）。即使您添加 std::bitset<> 来跟踪分配，它仍然快 4 倍（400 毫秒）。

关于 new 需要记住的一件重要事情是，分配对象所花费的时间通常取决于堆的状态。一个空堆将能够相对快速地分配一堆像这样的常量大小的对象，这可能是您的代码看起来比 new 慢的原因之一。如果您的程序运行了一段时间并分配了大量不同大小的对象，则堆可能会变得碎片化并且分配对象可能需要更长（更多）的时间。

例如，我编写的一个程序正在加载一个 200MB 的文件，其中包含数百万条记录……许多不同大小的分配。在第一次加载时需要大约 15 秒，但如果我删除该文件并尝试再次加载它，它会花费大约 x10-x20 的时间。这完全是由于内存分配和切换到一个简单的 bucket/arena 分配器解决了这个问题。因此，我所做的显示 x16 加速的人为基准测试实际上可能会显示出与碎片堆的显着差异。

当您意识到不同的 systems/platforms 可能使用不同的内存分配方案时，这会变得更加棘手，因此一个系统上的基准测试结果可能与另一个不同。

将其提炼成几个简短的要点：

基准内存分配很棘手（性能取决于很多因素）
在某些情况下，您可以使用自定义分配器获得更好的性能。在某些情况下，您可以变得更好。
创建自定义分配器可能很棘手，需要时间 profile/benchmark 您的特定用例。

注意 -- 这样的基准并不意味着是现实的，但有助于确定某事物的速度上限。它可以与您的实际代码的 profile/benchmark 一起使用，以帮助确定哪些 should/shouldn 没有被优化。

Update -- 我似乎无法在 MSVC++ 2013 下的代码中复制您的结果。使用与您的 avlnode 相同的结构并尝试放置 new 产生与我的非放置桶分配器测试相同的速度（放置新实际上更快一点）。使用类似于 avltree 的 class 不会对基准产生太大影响。有了 1000 万 allocations/deallocations，new/delete 得到 ~800 毫秒，自定义分配器得到 ~200 毫秒（有和没有放置 new）。虽然我不担心绝对时间的差异，但相对时间差异似乎很奇怪。

我建议您仔细查看您的基准并确保您衡量的是您认为的自己。如果代码存在于更大的代码库中，则创建一个最小的测试用例来对其进行基准测试。确保您的编译器优化器没有做一些会使基准测试无效的事情（这些天很容易发生）。

请注意，如果您将问题简化为最小示例并将完整代码（包括基准代码）包含在问题中，那么回答您的问题会容易得多。基准测试是看似简单的事情之一，但其中涉及很多 "gotchas"。

更新 2 -- 包括我正在使用的基本分配器 class 和基准代码，以便其他人可以尝试复制我的结果。请注意，这仅用于测试，与实际 working/production 代码相去甚远。它比您的代码简单得多，这可能就是我们得到不同结果的原因。

#include <string>
#include <Windows.h>

struct test_t 
{
    __int64 key;
    __int64 weight;
    __int64 left;
    __int64 right;
    test_t* pNext;     // Simple linked list

    test_t() : key(0), weight(0), pNext(NULL), left(0), right(0) { }
    test_t(const __int64 k) : key(k), weight(0), pNext(NULL), left(0), right(0) { }
};

const size_t NUM_ALLOCS = 10000000;
test_t* pLast; //To prevent compiler optimizations from being "smart"

struct CTest 
{
    test_t* m_pBuffer;
    size_t  m_MaxSize;
    size_t  m_FreeIndex;
    test_t* m_pFreeList;

    CTest(const size_t Size) :
            m_pBuffer(NULL),
            m_MaxSize(Size),
            m_pFreeList(NULL),
            m_FreeIndex(0)
    {
        if (m_MaxSize > 0) m_pBuffer = (test_t *) new char[sizeof(test_t) * (m_MaxSize + 1)];
    }

    test_t* NewNode(__int64 key)
    {
        if (!m_pBuffer || m_FreeIndex >= m_MaxSize) return new test_t(key);

        size_t Pos = m_FreeIndex;
        ++m_FreeIndex;
        return new (&m_pBuffer[Pos]) test_t(key);
    }

    void DeleteNode(test_t* pNode)
    {
        if (!m_pBuffer) {
            delete pNode;
        }
        else
        {
            pNode->pNext = m_pFreeList;
            m_pFreeList = pNode;
        }
    }

};


void TestNew(void)
{
    test_t* pPtr = new test_t;
    test_t* pFirst = pPtr;

    for (int i = 0; i < NUM_ALLOCS; ++i)
    {
        pPtr->pNext = new test_t;
        pPtr = pPtr->pNext; 
    }

    pPtr = pFirst;

    while (pPtr)
    {
        test_t* pTemp = pPtr;
        pPtr = pPtr->pNext;
        delete pTemp;
    }

    pLast = pPtr;    
}


void TestClass(const size_t BufferSize)
{
    CTest Alloc(BufferSize);
    test_t* pPtr = Alloc.NewNode(0);
    test_t* pFirstPtr = pPtr;

    for (int i = 0; i < NUM_ALLOCS; ++i)
    {
        pPtr->pNext = Alloc.NewNode(i);
        pPtr = pPtr->pNext;
    }

    pLast = pPtr;
    pPtr = pFirstPtr;

    while (pPtr != NULL)
    {
        test_t* pTmp = pPtr->pNext;
        Alloc.DeleteNode(pPtr);
        pPtr = pTmp;
    }
}


int main(void)
{
    DWORD StartTick = GetTickCount();
    TestClass(0);
    //TestClass(NUM_ALLOCS + 10);
    //TestNew();
    DWORD EndTick = GetTickCount();

    printf("Time = %u ms\n", EndTick - StartTick);
    printf("Last = %p\n", pLast);

    return 0;
}

目前 TestNew() 和 TestClass(0) 都在 800 毫秒左右，TestClass(NUM_ALLOCS + 10) 在 200 毫秒以下。自定义分配器非常快，因为它以完全线性的方式在内存上运行，这允许内存缓存发挥其魔力。为了简单起见，我也使用 GetTickCount()，只要时间超过 ~100ms，它就足够准确。

Answer 4

仅供参考，以下代码是解决手头问题的最佳代码。

这只是一个简单的 avltree 实现，但在我的 2600K @ 4.6 GHz 上它确实达到了 1.7 秒的 1000 万次插入和 1.4 秒的相同数量的删除。

#include "stdafx.h"
#include <iostream>
#include <crtdbg.h>
#include <Windows.h>
#include <malloc.h>
#include <new>

#ifndef NULL
#define NULL 0
#endif

typedef int keytype;
typedef unsigned long long UINT64;

struct avlnode;

struct avltree
{
  avlnode *root;
  avlnode *buffer;
  avlnode *firstfree;

  avltree() : avltree(0) {};
  avltree(UINT64 numitems);

  inline avlnode *newnode(keytype key);
  inline void deletenode(avlnode *node);

  void insert(keytype key) { root = insert(root, key); }
  void remove(keytype key) { root = remove(root, key); }
  int height();
  bool hasitems() { return root != NULL; }
private:
  avlnode *insert(avlnode *node, keytype k);
  avlnode *remove(avlnode *node, keytype k);
};

#pragma pack(1)
struct avlnode
{
  avlnode *left;     //left pointer
  avlnode *right;    //right pointer
  keytype key;       //node key
  unsigned char hgt; //height of the node

  avlnode(int k)
  {
    key = k;
    left = right = NULL;
    hgt = 1;
  }

  avlnode &balance()
  {
    struct F
    {
      unsigned char height(avlnode &node)
      {
        return &node ? node.hgt : 0;
      }
      int balance(avlnode &node)
      {
        return &node ? height(*node.right) - height(*node.left) : 0;
      }
      int fixheight(avlnode &node)
      {
        unsigned char hl = height(*node.left);
        unsigned char hr = height(*node.right);
        node.hgt = (hl > hr ? hl : hr) + 1;
        return (&node) ? hr - hl : 0;
      }
      avlnode &rotateleft(avlnode &node)
      {
        avlnode &p = *node.right;
        node.right = p.left;
        p.left = &node;
        fixheight(node);
        fixheight(p);
        return p;
      }
      avlnode &rotateright(avlnode &node)
      {
        avlnode &q = *node.left;
        node.left = q.right;
        q.right = &node;
        fixheight(node);
        fixheight(q);
        return q;
      }
      avlnode &b(avlnode &node)
      {
        int bal = fixheight(node);
        if (bal == 2) {
          if (balance(*node.right) < 0)
            node.right = &rotateright(*node.right);
          return rotateleft(node);
        }
        if (bal == -2) {
          if (balance(*node.left) > 0)
            node.left = &rotateleft(*node.left);
          return rotateright(node);
        }
        return node; // balancing is not required
      }
    } f;
    return f.b(*this);
  }
};

avltree::avltree(UINT64 numitems)
{
  root = buffer = firstfree = NULL;
  if (numitems) {
    buffer = (avlnode *) malloc(sizeof(avlnode) * (numitems + 1));
    avlnode *tmp = &buffer[numitems];
    while (tmp > buffer) {
      tmp->right = firstfree;
      firstfree = tmp--;
    }
  }
}

avlnode *avltree::newnode(keytype key)
{
  avlnode *node = firstfree;
  /*
  If you want to support dynamic allocation, uncomment this.
  It does present a bit of an overhead for bucket allocation though (8% slower)
  Also, if a condition is met where bucket is too small, new nodes will be dynamically allocated, but never freed
  if (!node)
  return new avlnode(key);
  */
  firstfree = firstfree->right;
  return new (node) avlnode(key);
}

void avltree::deletenode(avlnode *node)
{
  /*
  If you want to support dynamic allocation, uncomment this.
  if (!buffer)
  delete node;
  else {
  */
  node->right = firstfree;
  firstfree = node;
}

int avltree::height()
{
  return root ? root->hgt : 0;
}

avlnode *avltree::insert(avlnode *node, keytype k)
{
  if (!node)
    return newnode(k);
  if (k == node->key)
    return node;
  else if (k < node->key)
    node->left = insert(node->left, k);
  else
    node->right = insert(node->right, k);
  return &node->balance();
}

avlnode *avltree::remove(avlnode *node, keytype k) // deleting k key from p tree
{
  if (!node)
    return NULL;
  if (k < node->key)
    node->left = remove(node->left, k);
  else if (k > node->key)
    node->right = remove(node->right, k);
  else //  k == p->key 
  {
    avlnode *l = node->left;
    avlnode *r = node->right;
    deletenode(node);
    if (!r) return l;

    struct F
    {
      //findmin finds the minimum node
      avlnode &findmin(avlnode *node)
      {
        return node->left ? findmin(node->left) : *node;
      }
      //removemin removes the minimum node
      avlnode &removemin(avlnode &node)
      {
        if (!node.left)
          return *node.right;
        node.left = &removemin(*node.left);
        return node.balance();
      }
    } f;

    avlnode &min = f.findmin(r);
    min.right = &f.removemin(*r);
    min.left = l;
    return &min.balance();
  }
  return &node->balance();
}
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
  // 64 bit release performance (for 10.000.000 nodes)
  // malloc:       insertion: 2,595  deletion 1,865
  // my allocator: insertion: 2,980  deletion 2,270
  const int nodescount = 10000000;

  avltree &tree = avltree(nodescount);
  cout << "sizeof avlnode " << sizeof(avlnode) << endl;
  cout << "inserting " << nodescount << " nodes" << endl;
  LARGE_INTEGER t1, t2, freq;
  QueryPerformanceFrequency(&freq);
  QueryPerformanceCounter(&t1);
  for (int i = 1; i <= nodescount; i++)
    tree.insert(i);
  QueryPerformanceCounter(&t2);
  cout << "Tree height " << (int) tree.height() << endl;
  cout << "Insertion time: " << ((double) t2.QuadPart - t1.QuadPart) / freq.QuadPart << " s" << endl;
  QueryPerformanceCounter(&t1);
  while (tree.hasitems())
    tree.remove(tree.root->key);
  QueryPerformanceCounter(&t2);
  cout << "Deletion time: " << ((double) t2.QuadPart - t1.QuadPart) / freq.QuadPart << " s" << endl;

#ifdef _DEBUG
  _CrtMemState mem;
  _CrtMemCheckpoint(&mem);
  cout << "Memory used: " << mem.lTotalCount << " high: " << mem.lHighWaterCount << endl;
#endif
    return 0;
}

自定义分配器性能

Custom allocator performance

c++

performance

memory-management

allocator