Здравствуйте, TailWind, Вы писали:
AG>>Или как сделать самому такой аллокатор?
TW>Да, как самому сделать
Есть разные типы куч памяти.
Одна стратегия: блоки на каждую аллокацию, объединяются в связные списки, со служебной информацией, сколько выделенно, или блок свободен.
При освобождении также можно объединять свободные блоки в блоки большего размера.
Другая: распеделять разные размеры аллокаций по разным блокам. Например аллокации до 16 байт, до 32 байт, до 64 байт и т.д. Т.е. аллокация 17 байт будек как 32 байта.
На каждую выделен блок самих для данных плюс битовый массив, какой блок занят/свободен. Ну и предусмотрена возможность выделения ещё одного большого блока для такого же размера, когда текущий заполнится.
Да, если есть необходимость, чтобы всё было в конкретном файле, думаю, идея в том, чтобы пережить перезапуск программы.
Это можно добиться:
* Пытаясь спроецировать файл в то же место каждый раз. Так себе идея, хотя в MSVC precompiled headers используется
* Смириться с тем, что фалй будет проецироваться в разные области и не иметь абсолютных указателей. Все указатели или заменены индексами, или относительно начала области памяти, или относительно себя.
Здравствуйте, TailWind, Вы писали:
TW>Или что забить в гугле чтобы найти известные подходы?
Да, не так просто искать.
При попытке найти по "Heap", попадается Heap, который Data Structure.
При попытке найти по "Dynamic Memory Allocation", попадается использование, а не написание.
Боль-мень релеватные результаты по запросам по memory pool, вроде how to implement memory pool.
Здравствуйте, TailWind, Вы писали:
TW>Есть у меня файл в котором я хочу хранить блоки данных разного размера
TW>Как реализовать getmem, freemem?
TW>Так чтобы если блок данных больше не нужен, то getmem задействовала бы освобождённые блоки?
Спроецировать файл в память, завернуть это в std::pmr::memory_resource, и подсунуть его в std::pmr::synchronized_pool_resource или std::pmr::unsynchronized_pool_resource
Если без С++17 — pmr есть в boost.
Смысл всего этого, правда, под вопросом. Система и так будет выделять обычные malloc / free с использованием page file.
Здравствуйте, TailWind, Вы писали:
TW>Есть у меня файл в котором я хочу хранить блоки данных разного размера
TW>Как реализовать getmem, freemem?
TW>Так чтобы если блок данных больше не нужен, то getmem задействовала бы освобождённые блоки?
Sqlite.
Если не нравится — Berkeley DB (по постановке вопроса 1.85 хватит с головой и у неё лицензия BSD, брать из современной FreeBSD), tokyocabinet, LMDB, другое хранилище ключ-значение с укладыванием произвольно толстых блобов — тысячи их.
Зачистку делают сами.
AG>Спроецировать файл в память, завернуть это в std::pmr::memory_resource, и подсунуть его в std::pmr::synchronized_pool_resource или std::pmr::unsynchronized_pool_resource AG>Если без С++17 — pmr есть в boost.
Не не не
Вот без всяких этих извращений
AG>Смысл всего этого, правда, под вопросом. Система и так будет выделять обычные malloc / free с использованием page file.
AG>Другая: распеделять разные размеры аллокаций по разным блокам. Например аллокации до 16 байт, до 32 байт, до 64 байт и т.д. Т.е. аллокация 17 байт будек как 32 байта. AG>На каждую выделен блок самих для данных плюс битовый массив, какой блок занят/свободен. Ну и предусмотрена возможность выделения ещё одного большого блока для такого же размера, когда текущий заполнится.
Да, вот что-то вроде этого нужно
Может есть какая-то литература на эту тему?
Или что забить в гугле чтобы найти известные подходы?
AG>Да, если есть необходимость, чтобы всё было в конкретном файле, думаю, идея в том, чтобы пережить перезапуск программы.
С одной стороны нужен save, load
С другой стороны в память 32-bit C++ application это не лезет
Плюс файл формируется не последовательно, а заполняется постепенно
Выделенные блоки увеличиваются в размере
С>Вам это наверное для какой-то более утилитарной задачи нужно?
Ничего сложного
Мне нужно сформировать файл на диске
Где для каждого ID от 0 до 0x5000000 хранится небольшой блок данных (от 0 до 80 байт, но может быть и больше)
Проблема в том, что блоки данных для каждого ID дополняются (увеличиваются в размерах) в случайном порядке
Скорость поиска и добавления должна быть максимальной
Что-то вроде обращения по индексу в массив
B-дерево не подходит
После завершения создания файла, больше ничего добавляться не будет
То есть промежуточные временные структуры (битмапы) можно хранить в памяти, а потом удалить
---
Количество ID известно заранее
Вероятность что у ID блок данных умеет столько записей:
0 = 20%
1 = 40%
2 = 20%
3 = 10%
4 = 5%
5 = 2%
...
Здравствуйте, TailWind, Вы писали:
С>>Вам это наверное для какой-то более утилитарной задачи нужно?
TW>После завершения создания файла, больше ничего добавляться не будет
TW>Есть у меня файл в котором я хочу хранить блоки данных разного размера TW>Как реализовать getmem, freemem? TW>Так чтобы если блок данных больше не нужен, то getmem задействовала бы освобождённые блоки?
ну вот же https://pmem.io/vmem/manpages/linux/v1.0/libvmem.3.html
Как много веселых ребят, и все делают велосипед...
AG>Одна стратегия: блоки на каждую аллокацию, объединяются в связные списки, со служебной информацией, сколько выделенно, или блок свободен. AG>При освобождении также можно объединять свободные блоки в блоки большего размера.
В принципе мне нужны две функции
Put_Data(ID, data)
Get_Data(ID)
То есть не обязательно, чтобы данные в файле лежали одним куском
Здравствуйте, TailWind, Вы писали:
TW>Есть у меня файл в котором я хочу хранить блоки данных разного размера
TW>Как реализовать getmem, freemem?
TW>Так чтобы если блок данных больше не нужен, то getmem задействовала бы освобождённые блоки?
Здравствуйте, рекомендую поискать на codeproject там периодически появляются статьи на эту тему memory allocator memory pool
Здравствуйте, TailWind, Вы писали:
TW>Где для каждого ID от 0 до 0x5000000 хранится небольшой блок данных (от 0 до 80 байт, но может быть и больше)
Что значит "до 80 байт, но может быть и больше"? До чего все-таки? 256?
Можно сделать большой файл, оставив максимальный размер записи. Обращаться по индексу.
Готовый файл можно обработать, выкинув свободные куски. Первые 0x5000000 четырехбитных слов — индекс.
TW>>Где для каждого ID от 0 до 0x5000000 хранится небольшой блок данных (от 0 до 80 байт, но может быть и больше) VF>Что значит "до 80 байт, но может быть и больше"? До чего все-таки? 256?
Хотелось бы предусмотреть неограниченное увеличение
Давайте заложим 10% накладных расходов на всякие списки
Раз уж я решил не хранить блок данных одним куском
VF>Можно сделать большой файл, оставив максимальный размер записи. Обращаться по индексу.
Я хочу сделать в начале файла таблицу длинной N (макс ID)
На каждый ID одна запись
Если для этого ID нет данных, там -1
Если для этого ID есть только одно число (8 байт) пишем его в таблицу
Если больше 1го числа, то в таблице указывается индекс больше размера таблицы и там уже хранятся связные списки, которые сейчас нужно продумать
VF>Готовый файл можно обработать, выкинув свободные куски. Первые 0x5000000 четырехбитных слов — индекс.
ммм
Для данной задачи пост обработка после, чтобы уменьшить объём, не имеет смысла
Лучше не допускать, чтобы файл слишком сильно раздувался в процессе (в рамках 10%)
Здравствуйте, TailWind, Вы писали:
AG>>Да, если есть необходимость, чтобы всё было в конкретном файле, думаю, идея в том, чтобы пережить перезапуск программы. TW>С одной стороны нужен save, load TW>С другой стороны в память 32-bit C++ application это не лезет