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

Question

Я ищу идеи для кучи-менеджера, чтобы справиться с очень специфической ситуацией: много и много очень маленьких выделений, от 12 до 64 байтов каждый. Что-нибудь большее, я перейду к обычному менеджеру кучи, так что нужно обслуживать только крошечные блоки. Требуется только 4-байтовое выравнивание.

Мои основные проблемы

1. Накладные. Обычная куча libc обычно округляет выделение до кратного 16 байт, а затем добавляет еще один 16-байтовый заголовок - это означает более 50% накладных расходов при 20-байтовом выделении, что отстой.
2. Performance

Один полезный аспект заключается в том, что Lua (который является пользователем этой кучи) сообщит вам размер освобождаемого блока при вызове free () - это может включить определенные оптимизации.

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

Мне нравится один ответ.

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

Answer 5

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

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

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

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

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 соответствует количеству суперблоков, а не количеству элементов. Поскольку количество суперблоков очень мало по сравнению с количеством элементов (примерно в 20 двоичных порядках величины в моем коде), оно не так критично, как остальная часть распределителя.

Answer 6

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

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;
}