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

Question

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

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

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

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

Их может быть std::vector< SuperBlock > на случай, если одному суперблоку недостаточно места.

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

1. Для каждого Суперблока: есть ли место в конце Суперблока? поместите распределение там. (Быстро)
2. Если нет, найдите в каждом суперблоке пустое пространство достаточного размера и поместите туда выделение. (Медленно)
3. Все равно ничего не нашли? выделите еще один суперблок и поместите его в начало нового суперблока.

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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