Производительность пользовательского распределителя

Question

Я создаю класс дерева 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); 
} 

Для того, чтобы использовать стандартные новый/удалить, я должен построить дерево с количество_элементами == 0. Для того, чтобы использовать свой собственный аллокатор, я просто передать номер предметов. Все функции встроены для максимальной производительности.

Все это прекрасно и денди, но мой собственный распределитель на 20% медленнее, чем новый/удалить. Теперь, я знаю, насколько сложны распределители памяти, нет никакого способа, чтобы этот код мог работать быстрее, чем поиск массива + один бит, но это точно так. Что еще хуже: мой деллакоратор медленнее, даже если я удалю из него весь код?!?

Когда я проверяю сборку, мой код распределителя управляется инструкциями QWORD PTR, связанными с растровым, avltree или avlnode. Это не похоже на новый путь/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, которые будут помещены в регистры, но это, похоже, не так.

Тем не менее, разница в скорости заметно измерима. Я не звоню на 3 секунды на 10 миллионов узлов, вставленных медленно, но я ожидал, что мой код будет быстрее, а не медленнее, чем общий распределитель (2,5 секунды). Это особенно важно для более медленного deallocator, который работает медленнее, даже когда весь код удаляется из него.

Почему это медленнее?

Редактировать: Благодарим всех вас за отличные мысли об этом. Но я хотел бы еще раз подчеркнуть, что проблема заключается не столько в моем методе распределения, сколько в субоптимальном способе использования переменных: весь класс avltree содержит только 4 переменные UINT64, только у списка битлингов есть 3.

Однако, несмотря на это, компилятор не оптимизирует это в регистры. Он настаивает на инструкциях QWORD PTR, которые на несколько порядков ниже. Это потому, что я использую классы? Должен ли я перейти к переменным C/plain? Поцарапать это. Глупый я. У меня есть весь код avltree, и все не может быть в реестрах.

Кроме того, у меня полная потеря, почему мой деллакоратор все равно будет медленнее, даже если я удалю из него ВСЕ код. Тем не менее QueryPerformanceCounter говорит мне именно об этом. Это безумие даже думать, что: тот же deallocator также получает вызов для нового/удалить код, и он должен удалить узел ... Он не должен ничего делать для моего пользовательского распределителя (когда я стираю код).

Редактировать 2: Теперь я полностью удалил список бит и осуществил отслеживание свободного места через односвязный список. Функция avltree :: newnode теперь намного более компактна (21 инструкция для моего пользовательского пути распределителя, из которых 7 - это операторы QWORD PTR, имеющие отношение к avltree и 4 - для конструктора avlnode). Конечный результат (время) уменьшился с ~ 3 секунд до ~ 2.95 секунд для 10 миллионов распределений.

Редактирование 3: Я также переписал весь код таким образом, что теперь все обрабатывается односвязным списком. Теперь класс avltree имеет только два соответствующих члена: root и first_free. Разница в скорости остается.

Edit4: Перегруппировка код и, глядя на цифры производительности, эти вещи, что помогло больше всего:

1. Как было отмечено всеми участниками, имея битовую карту там было просто плохо. Удалено в пользу отдельного списка свободных слотов.
2. Локальность кода: добавление зависимых функций (управление деревьями avl) в локально-локальный класс вместо того, чтобы объявить их глобально, помогло приблизительно 15% с кодовой скоростью (3 сек. -> 2,5 сек).
3. Размер структуры avlnode : просто добавив #pragma pack(1) перед тем структура декларации уменьшить время выполнения еще на 20% (2,5 сек -> 2 сЕК)

Edit 5:

Поскольку querstion, кажется, был довольно популярным, Я опубликовал окончательный полный код в качестве ответа ниже. Я вполне доволен своей работой.

Answer 1

Ваш метод распределяет необработанную память только в одном фрагменте, а затем должен делать новое место для каждого элемента. Объедините это со всеми накладными расходами в вашем растровом изображении, и его не слишком удивительно, что распределение по умолчанию 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<> для отслеживания распределений, он по-прежнему x4 быстрее (400 мс).

Важно помнить о new, так это то, что время, затрачиваемое на выделение объекта, обычно зависит от состояния кучи. Пустая куча сможет выделить кучу объектов с постоянным размером, таких как это относительно быстро, что, вероятно, является одной из причин, по которой ваш код выглядит медленнее, чем new. Если у вас есть программа, которая работает некоторое время и выделяет большое количество объектов разного размера, куча может стать фрагментированной, а выделение объектов может занять много (дольше).

В качестве примера, одна программа, которую я написал, загружала 200-мегабайтный файл с миллионами записей ... много разных распределений. При первом загрузке потребовалось ~ 15 секунд, но если бы я удалил этот файл и попытался загрузить его снова, понадобилось бы что-то вроде x10-x20 дольше. Это было полностью связано с распределением памяти и переключением на простой распределитель ячеек/арены. Таким образом, этот ухищренный бенчмарк, который я продемонстрировал в результате ускорения x16, может фактически показать гораздо большую разницу с фрагментированной кучей.

Это становится еще более сложным, когда вы понимаете, что разные системы/платформы могут использовать разные схемы распределения памяти, поэтому результаты тестов в одной системе могут отличаться от других.

Чтобы отогнать это в нескольких коротких пункты:

1. распределение Бенчмаркинг памяти является сложным (производительность зависит от многих вещей)
2. В некоторых случаях вы можете получить более высокую производительность пользовательского распределителя. В нескольких случаях вы можете стать намного лучше.
3. Создание настраиваемого распределителя может быть сложным и требует времени для профилирования/сравнения вашего конкретного варианта использования.

Примечание - контрольные показатели, как это не значит быть реалистичными, но полезны для определения верхней границы того, как быстро что-то может быть. Он может использоваться вместе с профилем/эталоном вашего фактического кода, чтобы определить, что следует/не следует оптимизировать.

Update - Я не могу воспроизвести результаты в моем коде под MSVC++ 2013. Используя ту же структуру, как ваш avlnode и пробуя размещение new дает ту же скорость, что и моему неразмещение тестов ведра Allocator (размещение нового было на самом деле немного быстрее). Использование класса, аналогичного вашему 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; 
} 

В настоящее время я получаю ~ 800ms для обоих TestNew() и TestClass(0) и под 200мс для TestClass(NUM_ALLOCS + 10). Пользовательский распределитель работает довольно быстро, так как он работает с памятью совершенно линейно, что позволяет кешу памяти работать с магией. Я также использую GetTickCount() для простоты и достаточно точен, если времена превышают ~ 100 мс.

Answer 2

Трудно быть уверенным в таком маленьком коде для изучения, но я ставлю на местность ссылок. Ваше растровое изображение с метаданными не совпадает с той же линией, что и выделенная память. И get_first_unset может быть линейным поиском.

Answer 3

Теперь, я знаю, как сложны распределители памяти, нет никакого способа, чтобы этот код мог работать быстрее, чем поиск массива + один бит, но это точно так.

Это даже не совсем правильно. Достаточная куча кукурузы с низкой фрагментацией - O (1) с очень низким постоянным временем (и фактически нулевым дополнительным пространством). Я видел версию, которая доходила до инструкций ~ 18 asm (с одной веткой). Это намного меньше, чем ваш код. Помните, что кучи могут быть массово сложными, но быстрый путь через них может быть действительно, очень быстрым.

Answer 4

Для справки, следующий код был наиболее эффективным для данной проблемы.

Это просто простая реализация 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; 
}