Производительность пользовательского распределителя
Я строю класс дерева 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. Чтобы использовать свой собственный распределитель, я просто передаю количество элементов. Все функции встроены для максимальной производительности.
Это все хорошо и прекрасно, но мой собственный распределитель работает примерно на 20% медленнее, чем new / delete. Теперь я знаю, насколько сложными являются распределители памяти, код не может работать быстрее, чем поиск в массиве + один бит, но это именно тот случай. Что еще хуже: мой деллокатор работает медленнее, даже если я удалю из него весь код?!?
Когда я проверяю вывод сборки, путь к моему распределителю пересекается с инструкциями QWORD PTR, относящимися к растровому изображению, avltree или avlnode. Похоже, он не сильно отличается для пути 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 с помощью default / custom allocator, и оно остается тем же в этой конкретной области кода. Я попытался удалить / заменить все соответствующие детали, но без существенного эффекта.
Честно говоря, я ожидал, что компилятор встроит все это, поскольку переменных очень мало. Я надеялся, что все, кроме самих объектов avlnode, будет помещено в регистры, но, похоже, это не так.
И все же разница в скорости явно измерима. Я не вызываю 3 секунды на 10 миллионов вставленных узлов медленно, но я ожидал, что мой код будет быстрее, а не медленнее, чем универсальный распределитель (2,5 секунды). Это особенно относится к более медленному деаллокатору, который медленнее, даже когда весь код извлекается из него.
Почему это медленнее?
Редактировать: Спасибо всем за отличные мысли по этому поводу. Но я хотел бы еще раз подчеркнуть, что проблема заключается не столько в моем методе распределения, сколько в неоптимальном способе использования переменных: весь класс avltree содержит всего 4 переменные UINT64, а список битов - только 3.
Однако, несмотря на это, компилятор не оптимизирует это в регистры. Он настаивает на инструкциях QWORD PTR, которые на несколько порядков медленнее. Это потому, что я использую классы? Должен ли я перейти к C / обычные переменные? Сотрите это. Глупый я. У меня также есть весь код avltree, что-то не может быть в регистрах.
Кроме того, я в полном недоумении, почему мой диллокатор все еще будет работать медленнее, даже если я удалю из него ВСЕ код. И все же QueryPerformanceCounter говорит мне об этом. Безумно даже думать, что: тот же самый компилятор также вызывается для пути нового / удаляемого кода, и он должен удалять узел... Он не должен ничего делать для моего пользовательского распределителя (когда я удаляю код).
Edit2: теперь я полностью удалил список битов и реализовал отслеживание свободного пространства через список с односвязными связями. Функция avltree:: newnode теперь стала намного более компактной (21 инструкция для моего пользовательского пути выделения, 7 из них - операции QWORD PTR, связанные с avltree, и 4 - для конструктора avlnode). Конечный результат (время) уменьшился с ~3 секунд до ~2,95 секунд для 10 миллионов выделений.
Edit3: я также переписал весь код так, что теперь все обрабатывается односвязным списком. Теперь у класса avltree есть только два соответствующих члена: root и first_free. Разница в скорости сохраняется.
Edit4: перестановка кода и просмотр показателей производительности, вот что помогло больше всего:
- Как отмечают все авторы, наличие растрового изображения было просто плохим. Удален в пользу односвязного списка свободных слотов.
- Локальность кода: добавление зависимых функций (функций, обрабатывающих дерево avl) в локальный класс функций вместо объявления их глобально помогло примерно 15% скорости кода (3 секунды -> 2,5 секунды)
- Размер структуры avlnode: просто добавление
#pragma pack(1)перед объявлением структуры уменьшилось время выполнения еще на 20% (2,5 с -> 2 с)
Изменить 5:
Поскольку этот запрос, кажется, был довольно популярен, я опубликовал окончательный полный код в качестве ответа ниже. Я вполне доволен его производительностью.
4 ответа
Ваш метод выделяет необработанную память только в одном чанке, а затем выполняет новое размещение для каждого элемента. Объедините это со всеми издержками в вашем растровом изображении, и не удивительно, что по умолчанию 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 против 2080 мс). Даже если вы добавите std::bitset<> для отслеживания распределения он все еще в 4 раза быстрее (400 мс).
Важно помнить о new в том, что время, которое требуется для выделения объекта, обычно зависит от состояния кучи. Пустая куча сможет выделить кучу объектов постоянного размера, таких как этот, относительно быстро, что, вероятно, является одной из причин, почему ваш код кажется медленнее, чем new, Если у вас есть программа, которая работает некоторое время и выделяет большое количество объектов разного размера, куча может стать фрагментированной, а выделение объектов может занять намного (намного) больше времени.
Например, одна программа, которую я написал, загружала 200-мегабайтный файл с миллионами записей... много разных размеров. При первой загрузке это заняло ~15 секунд, но если я удалил этот файл и попытался загрузить его снова, это заняло что-то вроде x10-x20 дольше. Это было полностью связано с распределением памяти и переключением на простой распределитель сегментов памяти. Таким образом, этот надуманный тест, который я показал, демонстрируя ускорение x16, на самом деле может показывать значительно большую разницу с фрагментированной кучей.
Это становится еще сложнее, когда вы понимаете, что разные системы / платформы могут использовать разные схемы распределения памяти, поэтому результаты тестов в одной системе могут отличаться от других.
Чтобы разделить это на несколько коротких моментов:
- Бенчмаркинг выделения памяти сложен (производительность зависит от многих вещей)
- В некоторых случаях вы можете получить лучшую производительность с помощью специального распределителя. В некоторых случаях вы можете стать намного лучше.
- Создание собственного распределителя может быть сложным и требует времени для профилирования / сравнения вашего конкретного варианта использования.
Примечание. Такие тесты не должны быть реалистичными, но полезны для определения верхней границы того, насколько быстро что-то может быть. Его можно использовать вместе с профилем / эталоном вашего реального кода, чтобы определить, что следует / не следует оптимизировать.
Обновление - я не могу воспроизвести ваши результаты в моем коде под MSVC++ 2013. Используя ту же структуру, что и ваш avlnode и пытается разместить new дает ту же скорость, что и мои тесты распределителя сегментов без размещения (размещение новых было на самом деле немного быстрее). Используя класс, похожий на ваш avltree не сильно влияет на тест С 10 миллионами выделений / выделений я получаю ~800 мс для new/delete и ~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 мс.
Трудно быть уверенным с таким небольшим кодом для изучения, но я держу пари на местность ссылки. Ваше растровое изображение с метаданными не совпадает с кэшированной линией, как сама выделенная память. А также get_first_unset может быть линейный поиск.
Просто для справки, следующий код был наиболее эффективным для рассматриваемой проблемы.
Это простая реализация avltree, но она достигает 1,7 секунды для 10 миллионов вставок и 1,4 секунды для равного количества удалений на моих 2600K при 4,6 ГГц.
#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;
}
Теперь я знаю, насколько сложными являются распределители памяти, код не может работать быстрее, чем поиск в массиве + один бит, но это именно тот случай.
Это даже не совсем правильно. Приличная корзина с низкой кучей фрагментации - это O(1) с очень низким постоянным временем (и фактически нулевым дополнительным пространственным расходом). Я видел версию, которая дошла до ~18 asm инструкций (с одной веткой) раньше. Это намного меньше, чем ваш код. Помните, что кучи могут быть чрезвычайно сложными, но быстрый путь через них может быть очень, очень быстрым.