Дисковое динамическое выделение памяти

Question

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

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

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

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

1. Доступ к памяти осуществляется только через функции ввода-вывода (чтение / запись), а не напрямую

2. Объекты (методы / указатели) не сохраняются, только данные.

3. Размер файла не является статичным, поэтому он должен увеличиваться при необходимости, а не быть большим и статичным

4. Для моих целей допустимо переназначить существующие указатели после дефрагментации

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

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

Для справки, я использую C ++ на встроенных устройствах.

---

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

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

---

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

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

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

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

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

Answer 1

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

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

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

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

...

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

Answer 4

Недавно я закодировал класс виртуальной кучи для проблемы с высоким использованием памяти, которая у меня была. Код LGPL и размещен на 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) Для чтения из «виртуальной кучи» есть функция чтения, в которой вы передаете «дескриптор», указатель на место назначения и размер данных для чтения.

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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

Я не думаю, что реляционные (SQL) БД имеют большой смысл, но bdb et al (gnu db, и я уверен, что есть другие) определенно это делает.