Разница в производительности Boost r-дерева по сравнению с отображаемым файлом
Мне нужно создать 3D R * -дерево, возможно, для длительного хранения, но производительность также будет проблемой.
Чтобы создать дерево, я решил использовать spacialindex Boost и нашел два возможных метода.
Либо я создаю это непосредственно, используя объекты, поскольку это здесь: Индекс многоугольников, хранящихся в векторе, однако это не позволяет мне хранить и загружать его без повторного создания R * -дерева.
Или я мог бы использовать сопоставленный файл, как описано здесь: Индекс хранится в сопоставленном файле с использованием Boost.Interprocess, однако я не уверен, что производительность запросов в этом случае достаточно высока.
Мое r-дерево будет содержать несколько тысяч записей, но, скорее всего, менее 100 000. Теперь мой вопрос: есть ли какие-либо серьезные проблемы с производительностью при использовании сопоставленных файлов по сравнению со стандартными объектами? Кроме того, если создание R * -дерева приблизительно из 100 000 значений не занимает значительного времени (у меня могут быть все ограничивающие блоки и соответствующие ключи / данные, хранящиеся в файле), тогда может быть лучшим вариантом пропустить сопоставленный файл и просто создавать дерево каждый раз, когда я запускаю программу?
Надеюсь, кто-нибудь может помочь мне здесь, так как документация на самом деле не дает много информации (хотя она все еще лучше, чем документация libspacialindex).
Решение
Сопоставленный файл будет вести себя в основном как обычная память (фактически, в Linux, выделение памяти с new или же malloc буду использовать mmap [с резервным хранилищем «без файла»] в качестве основного метода выделения). Однако, если вы делаете много небольших записей «повсеместно» и отображаете РЕАЛЬНЫЙ ФАЙЛ, ОС ограничит количество буферизованных записей перед записью в файл.
Я провел несколько экспериментов, когда тема поднималась некоторое время назад, и, отрегулировав настройки того, как ОС справляется с этими «отложенными записями», я добился разумной производительности даже при отображении памяти с файловым резервированием со случайным шаблоном чтения / записи [что-то, что, как я ожидаю, происходит когда вы строите свое дерево.
Вот вопрос «Производительность mmap со случайной записью», который, я думаю, очень тесно связан:
Плохая производительность сопоставленного файла памяти Linux с произвольным доступом C ++ & питон
(Этот ответ относится к Linux — другие ОС, в частности Windows, могут вести себя совершенно по-разному в отношении того, как они обрабатывают записи в сопоставленные файлы)
Конечно, довольно трудно сказать «что лучше», между отображенным в памяти файлом или перекомпоновкой при каждом запуске программы — это действительно зависит от того, что делает ваше приложение, запускаете ли вы его 100 раз в секунду или раз в день, сколько времени потребуется, чтобы восстановить [я понятия не имею!], и много других подобных вещей. Есть два варианта: создать простейшую версию и посмотреть, достаточно ли она быстра, или построить обе версии, измерить разницу между ними, а затем решить, какой путь выбрать.
Я склонен строить простую (ish) модель, и если производительность не достаточно хорошая, выяснить, откуда происходит медлительность, а затем исправить это — это сэкономит много времени, делая что-то, что занимает 0,01% от общего времени выполнения выполняйте на 5 тактов быстрее, и в конечном итоге вы получите большое размышление в другом месте, которое заставит его работать в 500 раз медленнее, чем вы ожидали …
Другие решения
Массовая загрузка индекса много быстрее, чем повторная вставка, и дает гораздо более эффективное дерево. Поэтому, если вы можете хранить все свои данные в основной памяти, я предлагаю перестроить дерево с помощью массовой загрузки STR. По моему опыту, это более чем достаточно быстро (время массовой загрузки значительно меньше времени ввода-вывода).
Стоимость STR примерно равна стоимости сортировки. O(n log n) теоретически, с очень низкими константами (менее эффективная реализация может быть O(n log n log n) но это все еще довольно дешево).