Распределение динамической памяти на основе диска

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

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

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

В этой ситуации:

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

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

Я спрашиваю, какой лучший подход для этой проблемы? Должен ли я реализовать простой распределитель памяти, который обрабатывает файл как кучу?

Для справки im использует С++ для встроенных устройств.

Изменить: я реализовал свой собственный менеджер памяти, который использует распределение памяти приятеля и размеры блоков в два раза. Я доволен, что это правильно и не течет, сглаживает свободные блоки и может сделать дефрагментацию "остановить мир".

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

Некоторые полезные, но до сих пор несовместимые темы:

mmap tbh Я havent использовал mmap, но он обращается к файлу IO, но не к управлению адресным пространством файла.

BOOST: сериализация У меня есть (возможно, необоснованное) нежелание использовать библиотеки boost на данный момент.

STXXL Интересно, но не адресует выделение памяти с переменным размером

Doug Lea Memory Allocator Имеет очень хорошее представление о проблемах с распределителями памяти, но я не в состоянии попытаться сделать свой собственный реализация

Ответ 1

Ваши две цели - сократить использование памяти и сохранить ваши данные. Это определенно похоже на работу для базы данных. Но тогда вы говорите

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

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

Записи с переменной длиной

...

SQLite, напротив, использует только необходимый объем дискового пространства для хранения информации в строке. Если вы сохраняете один символ в VARCHAR (100), то только потребляется один байт дискового пространства. (На самом деле два байта - есть некоторые накладные расходы в начале каждого столбца для записи его типа данных и длина.)

Он также является хорошим выбором для встроенной разработки:

Встроенные устройства и приложения

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

Ответ 2

Я реализовал свой собственный менеджер памяти, который использует распределение памяти приятеля и размеры блоков в два раза. Я доволен, что это правильно и не просачивается, свободные канистры и блокируют дефрагментацию "остановить мир".

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

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

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

Я также хотел бы предложить эту замечательную статью Андрея Александреску и Эмери Бергер по теме выделения памяти: Распределение памяти на основе политик и последние работают, в частности: Распределитель памяти Hoard.

Если возможно, просмотрите ссылки, упомянутые в конце этой статьи. Они также могут предоставить дополнительную информацию.

Ответ 3

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

Ответ 4

Недавно я закодировал класс виртуальной кучи для высокой проблемы использования памяти, которая у меня была. Код LGPL'ed и размещен на code.google.com по адресу:

http://code.google.com/p/kgui/source/browse/trunk/vheap.cpp

http://code.google.com/p/kgui/source/browse/trunk/vheap.h

По существу он работает следующим образом:

1) Определите размер блока и количество оставшихся блоков в памяти и имя файла для кэширования в файловой системе. В моем случае использования у меня есть 200 блоков 1 МБ в памяти в любое время.

2) Затем вызовите Allocate, чтобы зарезервировать кусок "виртуальной памяти". Вам возвращается 8-разрядный "дескриптор" в память. При желании вы можете выделить куски размером, превышающим размер блока.

3) Для записи в "виртуальную кучу" есть функция записи, в которой вы передаете "дескриптор" , указатель на данные и размер данных.

4) Для чтения из "виртуальной кучи" есть функция чтения, в которой вы передаете "дескриптор" , указатель на пункт назначения и размер данных для чтения.

Код автоматически обрабатывает обмен между тем, что находится в памяти, и тем, что хранится на диске. Это довольно просто.

Ответ 5

Для встроенных устройств я бы, конечно, выполнил простую реализацию вместо использования базы данных. Прямой файл IO позволяет избежать некоторых издержек баз данных. И ресурсы часто ограничены во встроенных средах.

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

Ответ 6

Я бы определенно использовал mmap для ввода-вывода. Это упростит прямой доступ к данным и при необходимости очистку на диске. Единственное, что вам нужно было бы контролировать, это то, где файл отображается в адресном пространстве, поэтому вы можете перемещать его.

Одной из возможностей управления памятью является создание другого файла для каждого объекта и использование дефрагментации уровня файловой системы, а не ее реализация самостоятельно. Вы никогда не говорили о том, какую ОС/файловую систему вы используете, но если у нее уже есть дефрагментация в сети, я бы это использовал. Если вы используете Linux и можете использовать XFS, вы можете использовать xfs_fsr. Я ожидал бы, что дефрагментация файловой системы будет сильно оптимизирована, и это потребует намного меньше усилий, чем реализовать самостоятельно в одном большом файле.

Ответ 7

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

Файловая система будет заниматься как распределением пространства, так и проблемами с плохими секторами. FAT обычно используется во встроенных устройствах. Хотя производительность фрагментации FAT довольно плохая, это не помешало использовать ее во многих встроенных устройствах. Большинство флэш-устройств действительно используют FAT.

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

Ответ 8

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

Ответ 9

Взгляните на HDF5 http://www.hdfgroup.org/HDF5/whatishdf5.html

Это должно служить вашей цели.

Ответ 10

Я собираюсь эхо kgiannakakis - то, что вы описываете, - это файловая система, а не система управления памятью.

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

Ответ 11

Hmmh. Это звучит как очень распространенный вариант использования BDB (Berkeley DB). Это эффективная библиотека качественного качества, которая выполняет постоянные "базы данных" с ключевыми значениями (~ = таблицы с другими БД), открытый источник и все.

Я не думаю, что реляционные (SQL) DB имеют много смысла, но bdb и др. (gnu db и я уверен, что есть другие), безусловно.

Ответ 12

Вы можете посмотреть возможности, предоставляемые Boost.Interprocess, в частности, взглянуть на объекты с файлами с управляемой памятью.