Эффективное распределение динамических массивов в памяти mmap
У меня очень большое (фиксированное во время выполнения, около 10 — 30 миллионов) количество массивов. Каждый массив содержит от 0 до 128 элементов, каждый из которых составляет 6 байтов.
Мне нужно хранить все массивы в памяти mmap (поэтому я не могу использовать malloc), и массивы должны иметь возможность динамически расти (до 128 элементов, и массивы никогда не уменьшаются).
Я реализовал наивный подход, состоящий в том, чтобы массив int представлял состояние каждого блока из 6 байтов в памяти mmap. Значение 0xffffffff в смещении представляет соответствующее смещение в свободной памяти mmap, любое другое значение — это идентификатор массива (который необходим для дефрагментации блоков в моей текущей реализации, блоки не могут быть перемещены без зная идентификатор их массива для обновления других структур данных). При выделении и когда массив превышает его распределение, он будет просто повторяться, пока не найдет достаточно свободных блоков, и вставлять с соответствующим смещением.
Вот как выглядят массив размещения и память mmap:
| 0xffffffff | 0xfffffff | 1234 | 1234 | 0xffffffff | ...
-----------------------------------------------------------------
| free | free |array1234[0]|array1234[1]| free | ...
Этот подход, однако, имеет накладные расходы памяти offset of furthest used block in mmap'ed memory x 4 (4 байта бер int).
Какие есть лучшие подходы для этого конкретного случая?
Мои идеальные требования для этого:
- Затраты памяти (любые таблицы размещения + неиспользуемое пространство) <= 1,5 бита на элемент + 4 * 6 байт на массив
- O (1) распределение и рост массивов
Решение
Boost.Interprocess кажется, есть аккуратная реализация управляемые файлы с отображением в памяти, с положениями, похожими на malloc / free, но для сопоставленных файлов (то есть у вас есть дескриптор достаточно большого отображаемого в память файла, и вы можете попросить библиотеку перераспределить неиспользуемую часть файла для чего-то, например, массива). Из документации:
Boost.Interprocess предлагает несколько базовых классов для создания разделяемой памяти
объекты и сопоставления файлов и сопоставить эти сопоставляемые классы с
адресное пространство процесса.Тем не менее, управление этими сегментами памяти не так просто для
нетривиальные задачи. Отображаемая область представляет собой буфер памяти фиксированной длины и
создание и уничтожение объектов любого типа динамически, требует
много работы, так как это потребует программирования управления памятью
алгоритм для выделения частей этого сегмента. Много раз, мы также
хотите связать имена с объектами, созданными в общей памяти, так что все
процессы могут найти объект, используя имя.Boost.Interprocess предлагает 4 класса сегментов управляемой памяти:
- Для управления отображаемой областью совместно используемой памяти (класс basic_managed_shared_memory).
- Для управления отображенным в память файлом (basic_managed_mapped_file).
- Для управления выделенной кучей (оператор новый) буфер памяти (класс basic_managed_heap_memory).
- Для управления пользователем предусмотрен фиксированный размер буфера (класс basic_managed_external_buffer).
Наиболее важные сервисы сегмента управляемой памяти:
- Динамическое распределение порций памяти на сегмент.
- Построение объектов C ++ в сегменте памяти. Эти объекты могут быть анонимными или мы можем связать с ними имя.
- Возможности поиска по названным объектам.
- Настройка многих функций: алгоритм выделения памяти, типы индексов или типы символов.
- Атомные конструкции и разрушения, так что если сегмент разделен между двумя процессами, невозможно создать два объекта
связано с тем же именем, упрощая синхронизацию.
Другие решения
Сколько областей mmap вы можете себе позволить? Если 128 в порядке, то я создал 128 областей, соответствующих всем возможным размерам ваших массивов. И в идеале это связанный список бесплатных записей для каждой области. В этом случае вы получите фиксированный размер записи для каждой области. Увеличение массива от N до N + 1 — это операция перемещения данных из области [N] в область [N + 1] в конце (если связанный список пустых записей для N + 1 пуст) или в пустой слот, если нет. Для области [N] удаленный слот добавляется в список бесплатных записей.
ОБНОВЛЕНИЕ: связанный список может быть встроен в основные структуры. Таким образом, никаких дополнительных выделений не требуется, первое поле (int) внутри каждой возможной записи (от размера 1 до 128) может быть индексом для следующей свободной записи. Для выделенных записей это всегда void (0xffffffff), но если запись свободна, этот индекс становится членом соответствующей связанной цепочки.
Я разработал и в конечном итоге пошел с алгоритмом распределения памяти, который почти соответствует моим требованиям, с амортизированной O (1), очень мало фрагментации и очень мало накладных расходов. Не стесняйтесь комментировать, и я подробно опишу, когда у меня будет шанс.