Эффективный менеджер кучи для большого оттока, крошечные ассигнования?
https://stackoverflow.com/questions/228081
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я ищу идеи для кучи-менеджера, чтобы справиться с очень специфической ситуацией: много и много очень маленьких выделений, от 12 до 64 байтов каждый. Что-нибудь большее, я перейду к обычному менеджеру кучи, так что нужно обслуживать только крошечные блоки. Требуется только 4-байтовое выравнивание.
Мои основные проблемы:
<Ол>Один полезный аспект заключается в том, что Lua (который является пользователем этой кучи) сообщит вам размер освобождаемого блока при вызове free () - это может включить определенные оптимизации.
Я опубликую свой текущий подход, который работает нормально, но я хотел бы улучшить его, если это вообще возможно. Есть идеи?
Решение
Можно создать менеджер кучи, который будет очень эффективен для объектов одинакового размера. Вы можете создать одну из этих куч для каждого размера объекта, который вам нужен, или, если вы не возражаете, используя немного места, создайте один для 16-байтовых объектов, один для 32 и один для 64. Максимальные издержки будут 31 байт для 33-байтового распределения (которое будет использовано в куче размером 64 блока).
Другие советы
Чтобы подробнее остановиться на том, что говорит Грег Хьюгилл, один из способов сделать ультра-эффективную кучу фиксированного размера:
<Ол>Очевидно, что шаг 3 также должен проверить, пуст ли список, и если это так, выполнить кучу работы, получая новый большой буфер (или потерпеть неудачу).
Еще более эффективно, как говорят Грег Д. и Хаззен, выделять, увеличивая или уменьшая указатель (1 загрузка, 1 хранилище), и вообще не предлагая способ освободить один узел.
Редактировать. В обоих случаях free может справиться со сложностью "все, что я передаю обычному администратору кучи". полезным фактом, что вы получаете размер обратно в вызове бесплатно. В противном случае вы бы смотрели либо на флаг (служебная нагрузка, вероятно, 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) Суперблоки разбиты на блоки (также регулируемые по размеру ... 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 двоичных порядков в моем коде), оно не так критично, как остальная часть распределителя.
