Эффективный менеджер кучи для интенсивного оттока, крошечных распределений?

Можно создать диспетчер кучи, который будет очень эффективен для объектов одинакового размера. Вы можете создать одну из этих куч для каждого размера объекта, который вам нужен, или, если вы не возражаете против использования небольшого пространства, создайте одну для 16-байтовых объектов, одну для 32-байтовых и одну для 64-байтовых. Максимальные накладные расходы будут 31 байт для 33-байтового распределения (которое поместится в куче размером 64 блока).

Чтобы расширить то, что говорит Грег Хьюгилл, один из способов сделать сверхэффективную кучу фиксированного размера:

1. Разделите большой буфер на узлы. Размер узла должен быть не меньше sizeof(void*).
2. Соедините их вместе в односвязный список («свободный список»), используя первый sizeof(void*) байт каждого свободного узла в качестве указателя связи. Выделенные узлы не нуждаются в указателе ссылки, поэтому накладные расходы на каждый узел равны 0.
3. Выделите, удалив заголовок списка и вернув его (2 загрузки, 1 сохранение).
4. Бесплатно, вставив в начало списка (1 загрузка, 2 магазина).

Очевидно, что шаг 3 также должен проверить, пуст ли список, и если это так, проделать кучу работы, чтобы получить новый большой буфер (или потерпеть неудачу).

Еще более эффективным, как говорят Грег Д. и Хаззен, является выделение путем увеличения или уменьшения указателя (1 загрузка, 1 сохранение) и вообще не предлагать способ освобождения одного узла.

Редактировать: в обоих случаях бесплатно может справиться с осложнением «все, что больше, я передаю обычному диспетчеру кучи», благодаря полезному факту, что вы возвращаете размер при вызове бесплатно. В противном случае вы бы смотрели либо на флаг (накладные расходы, вероятно, 4 байта на узел), либо на поиск в какой-то записи буфера (буферов), который вы использовали.

Ответ может зависеть от моделей жизненного цикла этих объектов. Если все объекты создаются по мере продвижения, а затем все удаляются одним махом, может иметь смысл создать очень простой менеджер кучи, который выделяет память, просто увеличивая указатель. Затем, когда вы закончите, сдуйте всю кучу.

Рэймонд Чен опубликовал интересный пост, который может помочь вдохновлять вас. :)

Мне нравится ответ одного человека.

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

Если куча памяти выделяется, используется и освобождается перед переходом к следующему раунду выделения, я бы предложил использовать самый простой из возможных распределителей:

typedef struct _allocator {
    void* buffer;
    int start;
    int max;
} allocator;

void init_allocator(size_t size, allocator* alloc) {
    alloc->buffer = malloc(size);
    alloc->start = 0;
    alloc->max = size;
}

void* allocator_malloc(allocator* alloc, size_t amount) {
    if (alloc->max - alloc->start < 0) return NULL;
    void* mem = alloc->buffer + alloc->start;
    alloc->start += bytes;
    return mem;
}

void allocator_free(allocator* alloc) {
    alloc->start = 0;
}

Я использую в основном O(1) Small Block Memory Manager (SBMM). В основном это работает следующим образом:

1) Он выделяет большие суперблоки из ОС и отслеживает начальный и конечный адреса как диапазон. Размер SuperBlock регулируется, но 1 МБ — это довольно хороший размер.

2) SuperBlocks разбиты на блоки (также регулируемые по размеру... 4K-64K хорошо, в зависимости от вашего приложения). Каждый из этих блоков обрабатывает распределения определенного размера и хранит все элементы в блоке в виде односвязного списка. Когда вы выделяете суперблок, вы создаете связанный список свободных блоков.

3) Выделение предмета означает А) проверку наличия блока с бесплатными предметами такого размера, а если нет, выделение нового блока из суперблоков. Б) Удаление элемента из списка свободных блоков.

4) Освобождение элемента по адресу означает A) поиск суперблока, содержащего адрес(*) B) поиск блока в суперблоке (вычтите начальный адрес суперблока и разделите на размер блока) C) перемещение элемента обратно в список бесплатных элементов блока.

Как я уже говорил, этот SBMM очень быстрый, поскольку работает с производительностью O(1)(*). В версии, которую я реализовал, я использую AtomicSList (похожий на SLIST в Windows), так что это не только производительность O(1), но и ThreadSafe и LockFree в реализации. На самом деле вы можете реализовать алгоритм, используя Win32 SLIST, если хотите.

Интересно, что алгоритм выделения блоков из суперблоков или элементов из блоков приводит к почти идентичному коду (оба являются O(1) выделениями из свободного списка).

(*) Суперблоки расположены в карте диапазона со средней производительностью O(1) (но потенциальным O(Lg N) для наихудшего случая, где N — количество суперблоков). Ширина карты диапазона зависит от примерного знания того, сколько памяти вам понадобится, чтобы получить производительность O (1). Если вы превысите лимит, вы потратите немного памяти, но все равно получите производительность O (1). Если вы недооцените, вы приблизитесь к производительности O (Lg N), но N относится к количеству суперблоков, а не к количеству элементов. Поскольку количество SuperBlock очень мало по сравнению с количеством Item (примерно на 20 двоичных порядков в моем коде), оно не так критично, как остальная часть распределителя.