vel*_*lis 9 c++ performance memory-management allocator
我正在构建一个AVL树类,它将具有固定的最大项目数.所以我想的不是自己分配每个项目,而是一次分配整个块,并在需要时使用位图分配新的内存.
我的分配/解除分配代码:
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);
}
为了使用标准的new/delete,我必须用numitems == 0来构造树.为了使用我自己的allocator,我只传递了一些项目.所有功能都内联以获得最佳性能.
这很好,花花公子,但我自己的分配器比新/删除慢20%.现在,我知道复杂的内存分配器是多么复杂,代码运行速度不会比数组查找+一位设置更快,但这就是这里的情况.更糟糕的是:即使我删除了所有代码,我的解除分配器也会变慢？!？
当我检查汇编输出时,我的分配器的代码路径被QWORD PTR指令处理位图,avltree或avlnode.新/删除路径似乎没有太大的不同.
例如,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类只包含4个UINT64变量,bitlist只有3个.
但是,尽管如此,编译器并未将其优化为寄存器.它坚持QWORD PTR指令要慢几个数量级.这是因为我正在使用课程吗？我应该转移到C/plain变量吗？抓一点.愚蠢的我.我也有所有avltree代码,事情不能在寄存器中.
此外,我完全失去了为什么我的deallocator仍然会慢,即使我从中删除所有代码.然而,QueryPerformanceCounter就是这样告诉我的.甚至认为:同样的deallocator也被调用新的/删除代码路径并且它必须删除节点...它是疯狂的...它不需要为我的自定义分配器做任何事情(当我剥离代码时).
Edit2: 我现在已经完全删除了位列表并通过单链表实现了自由空间跟踪.avltree :: newnode函数现在更加紧凑(我的自定义分配器路径有21条指令,其中7条是处理avltree的QWORD PTR操作,4条用于avlnode的构造函数).对于1000万次分配,最终结果(时间)从~3秒减少到~2.95秒.
Edit3: 我还重写了整个代码,现在一切都由单链表处理.现在,avltree类只有两个相关成员:root和first_free.速度差异仍然存在.
编辑4: 重新排列代码并查看性能数据,这些都是最有帮助的:
#pragma pack(1)在struct声明之前添加执行时间再减少20%(2,5秒 - > 2秒)编辑5:
由于这个问题似乎很受欢迎,我已经发布了最终的完整代码作为下面的答案.我对它的表现非常满意.
您的方法仅在一个块中分配原始内存，然后必须为每个元素进行新的放置。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;
}
}
使用 MSVC++ 2013 上的此代码，分配 50M，其性能TestBucket()优于TestNew()16 倍以上（130 毫秒 vs 2080 毫秒）。即使您添加一个std::bitset<>来跟踪分配，它仍然快 4 倍（400 毫秒）。
需要记住的一件重要事情new是，分配对象所需的时间通常取决于堆的状态。空堆将能够相对较快地分配一堆大小恒定的对象，这可能是您的代码看起来比new. 如果您的程序运行一段时间并分配大量不同大小的对象，则堆可能会变得碎片化，并且分配对象可能需要更长的时间。
举个例子，我编写的一个程序正在加载一个包含数百万条记录的 200MB 文件……大量不同大小的分配。第一次加载大约需要 15 秒，但如果我删除该文件并尝试再次加载它，则需要大约 x10-x20 的时间。这完全是由于内存分配和切换到简单的存储桶/竞技场分配器解决了该问题。因此，我设计的显示 x16 加速的基准实际上可能会显示出与碎片堆相比明显更大的差异。
当您意识到不同的系统/平台可能使用不同的内存分配方案，因此一个系统上的基准测试结果可能与另一个系统不同时，事情会变得更加棘手。
将其提炼为几个要点：
注意——这样的基准并不意味着现实，但对于确定某事物的速度上限很有用。它可以与实际代码的配置文件/基准一起使用，以帮助确定应该/不应该优化哪些内容。
更新- 我似乎无法在 MSVC++ 2013 下的代码中复制您的结果。使用与您相同的结构avlnode并尝试放置new会产生与我的非放置存储桶分配器测试相同的速度（新放置实际上更快一点） ）。使用与您类似的类avltree不会对基准产生太大影响。进行 1000 万次分配/释放时，new/的delete时间约为 800 毫秒，自定义分配器的时间约为 200 毫秒（无论是否有放置new）。虽然我并不担心绝对时间的差异，但相对时间的差异似乎很奇怪。
我建议仔细看看你的基准，并确保你衡量的是你认为的自己。如果代码存在于更大的代码库中，则创建一个最小的测试用例来对其进行基准测试。确保您的编译器优化器没有做一些会使基准失效的事情（现在这种情况很容易发生）。
请注意，如果您将问题简化为最小的示例并在问题中包含完整的代码（包括基准代码），那么回答您的问题会容易得多。基准测试是看似简单的事情之一，但其中涉及很多“陷阱”。
更新 2——包括我正在使用的基本分配器类和基准代码，以便其他人可以尝试复制我的结果。请注意，这仅用于测试，与实际工作/生产代码相距甚远。它比您的代码简单得多，这可能就是我们得到不同结果的原因。
#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;
}
目前，我得到的时间约为 800 毫秒TestNew()，并且.TestClass(0)的时间低于 200 毫秒TestClass(NUM_ALLOCS + 10)。自定义分配器非常快，因为它以完全线性的方式对内存进行操作，这使得内存缓存发挥其魔力。我使用它也是GetTickCount()为了简单起见，只要时间高于约 100 毫秒，它就足够准确。