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

Question

У меня есть приложение Visual Studio 2008 C++, где я использую настраиваемый распределитель для стандартных контейнеров, так что их память поступает из файла с отображением памяти, а не из кучи. Этот распределитель используются для 4-х различных случаев использования:

1. 104-байтовых структуры фиксированного размера std::vector< SomeType, MyAllocator<SomeType> > foo;
2. 200-байтового фиксированного размером структура
3. 304-байтовых структуры фиксированного размера
4. н-байтовых строк std::basic_string< char, std::char_traits<char>, MyAllocator<char> > strn;

Мне нужно уметь распределять примерно 32 МБ для каждого из них.

Распределитель отслеживает использование памяти с помощью указателей std::map указателей на размер выделения. typedef std::map< void*, size_t > SuperBlock; Каждый SuperBlock представляет собой 4 МБ памяти.

Существует std::vector<SuperBlock> из них, если один SuperBlock недостаточно.

Алгоритм, используемый для распределителем выглядит следующим образом:

1. Для каждого SuperBlock: Есть ли место в конце SuperBlock? поставьте там распределение. (быстро)
2. Если нет, выполните поиск в пределах каждого SuperBlock для свободного пространства достаточного размера и разместите выделение там. (медленно)
3. По-прежнему ничего? выделите еще один SuperBlock и поставьте выделение в начале нового SuperBlock.

К сожалению, шаг 2 через некоторое время может стать ОЧЕНЬ медленным. По мере создания копий объектов и уничтожения временных переменных я получаю много фрагментации. Это вызывает много глубоких поисков в структуре памяти. Фрагментация возникает, так как у меня ограниченный объем памяти для работы (см. Примечание ниже).

Может ли кто-нибудь предложить усовершенствования этого алгоритма, что ускорит процесс? Нужно ли мне два отдельных алгоритма (1 для распределений фиксированного размера и один для распределителя строк)?

Примечание: Для тех, кому нужна причина: я использую этот алгоритм в Windows Mobile, где ограничение на процессорное пространство составляет 32 МБ. Таким образом, обычный std::allocator не отрежет. Мне нужно поставить выделение в 1 ГБ большой области памяти, чтобы иметь достаточно места, и это то, что это делает.

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

Есть некоторые усовершенствования.

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

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

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

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

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

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

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

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

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

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

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

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

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