предложения по улучшению реализации алгоритма распределителя

Для объектов фиксированного размера вы можете создать распределитель фиксированного размера. По сути, вы выделяете блоки, разбиваете их на подблоки соответствующего размера и создаете связанный список с результатом. Выделение из такого блока — O(1), если есть доступная память (просто удалите первый элемент из списка и верните на него указатель), как и освобождение (добавьте блок в список свободных). Во время выделения, если список пуст, захватите новый суперблок, раздел и добавьте все блоки в список.

Для списка переменного размера вы можете упростить его до блока фиксированного размера, выделив только блоки известных размеров: 32 байта, 64 байта, 128 байтов, 512 байтов. Вам нужно будет проанализировать использование памяти, чтобы придумать разные сегменты, чтобы не тратить слишком много памяти. Для больших объектов вы можете вернуться к шаблону динамического выделения размера, который будет медленным, но, надеюсь, количество больших объектов ограничено.

Можете ли вы иметь отдельный пул выделения памяти для каждого типа фиксированного размера, который вы выделяете? Таким образом не будет никакой фрагментации, потому что выделенные объекты всегда будут выравниваться по n-байтовым границам. Это, конечно, не помогает для строк переменной длины.

В Modern C++ Александреску есть пример выделения небольших объектов. дизайн, который иллюстрирует этот принцип и может дать вам некоторые идеи.

Основываясь на ответе Тима, я бы лично использовал что-то вроде BiBOP.

Основная идея проста: используйте пулы фиксированного размера.

К этому есть некоторые уточнения.

Во-первых, размер пулов обычно фиксирован. Это зависит от вашей процедуры распределения, обычно, если вы знаете ОС, с которой вы работаете, на карте как минимум 4 КБ одновременно, когда вы используете malloc, тогда вы используете это значение. Для файла с отображением памяти вы можете увеличить это значение.

Преимущество пулов фиксированного размера в том, что они хорошо борются с фрагментацией. Все страницы имеют одинаковый размер, вы можете легко преобразовать пустую страницу размером 256 байт в страницу размером 128 байт.

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

Во-вторых, как обращаться с пулами? Использование связанных списков.

Страницы обычно не типизированы (сами по себе), поэтому у вас есть свободный список страниц, в котором можно подготовить новые страницы и поместить «переработанные» страницы.

Для каждой категории размера у вас есть список «занятых» страниц, в которых выделена память. Для каждой страницы, которую вы храните:

• размер выделения (для этой страницы)
• количество выделенных объектов (для проверки на пустоту)
• указатель на первую свободную ячейку
• указатель на предыдущую и следующую страницы (может указывать на «голову» списка)

Каждая свободная ячейка сама по себе является указателем (или индексом, в зависимости от размера, который у вас есть) на следующую свободную ячейку.

Список «занятых» страниц заданного размера управляется просто:

• при удалении: если вы очищаете страницу, то удаляете ее из списка и заталкиваете в переработанные страницы, в противном случае обновляете список свободных ячеек этой страницы (примечание: поиск начала текущей страницы обычно является простой операцией по модулю по адресу)
• при вставке: поиск, начиная с заголовка, как только вы найдете неполную страницу, переместите ее перед списком (если это еще не сделано) и вставьте свой элемент

Эта схема очень производительна с точки зрения памяти, поскольку для индексации зарезервирована только одна страница.

Для многопоточных / многопроцессорных приложений вам необходимо добавить синхронизацию (обычно мьютекс на страницу), если вы можете получить вдохновение от tcmalloc Google (попробуйте найти другую страницу вместо блокировки, используйте локальный кеш потока чтобы вспомнить, какую страницу вы использовали в последний раз).

Сказав это, вы пробовали Boost.Interprocess ? Он предоставляет распределители.

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

Для элементов переменной длины это сложнее: вам либо приходится иметь дело с поиском доступного непрерывного пространства, либо использовать какой-то другой подход. Вы можете рассмотреть возможность сохранения другой карты всех свободных узлов, упорядоченных по размеру блока, чтобы вы могли уменьшить карту и, если следующий доступный узел, скажем, только на 5% больше, вернуть его вместо того, чтобы пытаться найти доступное пространство точного размера.

Моя склонность к элементам переменного размера заключалась бы в том, чтобы, если это целесообразно, избегать прямых указателей на данные и вместо этого сохранять дескрипторы. Каждый дескриптор будет индексом суперблока и индексом элемента в суперблоке. Каждый суперблок будет иметь список элементов, распределенный сверху вниз, и элементы, распределенные снизу вверх. Распределению каждого элемента будет предшествовать его длина и индекс элемента, который он представляет; используйте один бит индекса, чтобы указать, является ли элемент «закрепленным».

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

Конечно, если у вас есть только несколько дискретных размеров элементов, вы можете использовать простые распределители фрагментов фиксированного размера.

Я согласен с Тимом — используйте пулы памяти, чтобы избежать фрагментации.

Тем не менее, вы можете избежать некоторых проблем, сохраняя указатели, а не объекты в ваших векторах, возможно, ptr_vector?