Учитывая массив, есть ли алгоритм, который может выделить память из него?

Question

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

Что отличается от решения, которое мне нужно, чем от C-распределителя, так это то, что я никогда не вызываю malloc. Вместо этого я предварительно выделяю массив, а затем мне нужен объект, который оборачивает его, отслеживает свободное пространство и выделяет диапазон (пару указателей начала / конца) из распределения, которое я передаю.

Большое спасибо.

Answer 1

в целом: вы ищете диспетчер памяти, который использует (см. Википедию) пул памяти (например, boost :: pool в ответе TokenMacGuy). Они бывают разных вкусов. Важные соображения:

• размер блока (фиксированный или переменный; количество блоков разных размеров; можно ли прогнозировать использование размера блока (статистически)?
• эффективность (некоторые менеджеры имеют 2 ^ n размеров блоков, т. Е. Для использования в сетевых стеках, где они ищут наиболее подходящий блок; очень хорошая производительность и отсутствие утомления за счет потери памяти)
• накладные расходы на администрирование (я предполагаю, что у вас будет много очень маленьких блоков; таким образом, число целых и указателей, поддерживаемых диспетчером памяти, существенно для эффективности)

В случае boost :: pool, я думаю, простое сегрегированное хранилище стоит посмотреть. Это позволит вам настроить пул памяти с множеством блоков разных размеров, для которых ищется наилучшее совпадение.

Answer 2

boost :: pool делает это для вас очень хорошо!

Answer 3

Вместо этого я предварительно распределяю массив, а затем мне нужен объект, который оборачивает его и отслеживает свободное пространство и выделяет диапазон (пару указателей начала / конца) из распределения, которое я передаю.

Это , в основном , что внутренне делает malloc () (однако, malloc () может увеличить размер этого "предварительно выделенного массива", если он заполнится). Так что да, есть алгоритм для этого. На самом деле их много, и Википедия дает базовый обзор. Различные стратегии могут работать лучше в разных ситуациях. (Например, если все блоки имеют одинаковый размер, или если есть какой-то шаблон для выделения и освобождения)

Если у вас много объектов одинакового размера, посмотрите на препятствия.

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