Разница в производительности Boost r-tree в памяти по сравнению с сопоставленным файлом

Мне нужно создать 3D R*-дерево, возможно, для длительного хранения, но производительность также будет проблемой. Чтобы создать дерево, я решил использовать spacialindex Boost и нашел два возможных метода.

Либо я создаю его напрямую, используя объекты, как здесь: Индекс полигонов хранится в векторе, однако это не позволяет мне сохранять и загружать его без повторного создания R*-дерева.

Или я мог бы использовать сопоставленный файл, как описано здесь: Индекс, хранящийся в сопоставленном файле с использованием Boost.Interprocess, однако я не уверен, достаточно ли хороша производительность запросов в этом случае.

Мое r-дерево будет содержать несколько тысяч записей, но, скорее всего, меньше 100 000. Теперь мой вопрос: есть ли серьезные проблемы с производительностью при использовании сопоставленных файлов по сравнению с использованием стандартных объектов? Кроме того, если создание R*-дерева примерно из 100 000 значений не занимает много времени (я мог бы хранить все ограничивающие рамки и соответствующие ключи/данные в файле), то лучше пропустить сопоставленный файл и просто создавать дерево каждый раз, когда я запускаю программу?

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


c++ performance ubuntu-14.04 r-tree boost-geometry
person philkark    schedule 30.01.2015    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Сопоставленный файл будет вести себя в основном как обычная память (фактически, в Linux выделение памяти с помощью new или malloc будет использовать mmap [с резервным хранилищем «без файлов»] в качестве основного метода выделения). Однако, если вы выполняете много небольших операций записи «повсеместно» и выполняете сопоставление с РЕАЛЬНЫМ ФАЙЛОМ, ОС ограничит количество буферизованных операций записи перед записью в файл.

Я провел несколько экспериментов, когда эта тема возникла некоторое время назад, и, изменив настройки того, как ОС обрабатывает эти «ожидающие записи», я получил приемлемую производительность даже для сопоставления памяти с файловой резервной копией со случайным шаблоном чтения / записи [что-то, что я ожидаю, произойдет когда вы строите свое дерево].

Вот вопрос «производительность mmap со случайной записью», который, я думаю, очень связан: random-access-c-python">Плохая производительность файла с отображением памяти в Linux при произвольном доступе C++ и Python (этот ответ относится к Linux - другие ОС, в частности Windows, вполне могут вести себя совершенно по-другому в отношении того, как это работает с записью в сопоставленные файлы)

Конечно, довольно сложно сказать, «что лучше», между файлом отображения памяти или перестроением при каждом запуске программы — это действительно зависит от того, что делает ваше приложение, запускаете ли вы его 100 раз в секунду или один раз в день, сколько времени уходит на перестройку [абсолютно не знаю!], и многое другое в этом роде. Есть два варианта: собрать самую простую версию и посмотреть, достаточно ли она «быстра», или собрать обе версии и измерить, насколько велика разница, а затем решить, по какому пути пойти.

Я склонен строить простую модель, и если производительность недостаточно высока, выяснить, откуда берется медлительность, а затем исправить это — это экономит много времени, делая что-то, что занимает 0,01% от общего времени выполнения. работать на 5 тактов быстрее, и заканчивая большим размышлением где-то еще, что заставляет его работать в 500 раз медленнее, чем вы ожидали...

person Mats Petersson    schedule 30.01.2015
comment
Спасибо за ваш быстрый ответ. Вы, конечно, правы, что это полностью зависит от использования программы, к сожалению, если вы работаете в более крупном проекте, и пока еще не ясно, как именно будет использоваться моя часть, и я, вероятно, не узнаю, прежде чем мне нужно будет это сделать. Спасибо, что указали на тест производительности, я посмотрю на него. Если никто (например, Адам Вулкевич, создавший эту библиотеку) не ответит, я приму ваш. Возможно, это не точный ответ на мой вопрос, но он охватывает тему в целом. - person philkark; 30.01.2015
comment
Этот ответ неплохой, но слишком конкретный, поскольку ОП не указывает его операционную систему, а весь реальный контент относится только к Linux. - person Puppy; 30.01.2015
comment
Я добавил свою операционную систему в теги! Спасибо, что указали на это. - person philkark; 30.01.2015
comment
@Puppy: указал, что этот анализ производительности относится только к Linux, но я не знаю какой-либо другой причины, кроме очистки записи, которая является причиной медлительности - конечно, Windows может не иметь настройки для этого .... Или вы действительно знаете причину, по которой сопоставленные файлы не ведут себя как обычная память в некоторых других ОС? - person Mats Petersson; 30.01.2015
comment
Кроме того, если вы создаете модуль, который нужно интегрировать в другую, более крупную программу, было бы благоразумно попытаться выяснить, является ли производительность вашего модуля сверхкритической, потому что он используется каждый раз, когда вы выполняете X, а X очень распространены в нашей системе или не так критичны, потому что это происходит примерно раз в день, и задержка в этой ситуации не слишком критична [обратите внимание, что случается редко, на самом деле не означает, что производительность не критична - в автомобильной системе -тормоза с блокировкой должны работать быстро, даже если это не часто, где запуск двигателя не имеет значения - person Mats Petersson; 30.01.2015

arrow_upward
0
arrow_downward

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

Стоимость STR примерно равна стоимости сортировки. O(n log n) теоретически, с очень низкими константами (менее эффективной реализацией может быть O(n log n log n), но это все равно довольно дешево).

person Has QUIT--Anony-Mousse    schedule 30.01.2015
comment
Спасибо за ваш ответ. Я изначально хотел реализовать алгоритм упаковки, но не нашел, как создать дерево. Кроме bgi::rstar, bgi::linear и bgi::quadratic больше ничего не нашел (bgi = boost::geometry::index). Кроме того, как именно это может решить мою проблему с хранилищем и т. д.? - person philkark; 30.01.2015
comment
Я не использовал bgi, поэтому не знаю, доступна ли эта функция. Но его проще реализовать, чем полное дерево R*, поэтому я был бы удивлен, если бы у них не было массовой загрузки. Массовая загрузка дешева, я не думаю, что вам нужно хранить дерево тогда. - person Has QUIT--Anony-Mousse; 30.01.2015
comment
Спасибо, я посмотрю на это и посмотрю, смогу ли я найти его. Да, если дерево все равно будет создаваться быстро, то мне не нужно будет его хранить, а просто каждый раз создавать, так тоже может быть проще обновлять данные, просто добавляя в файл дополнительные ограничительные рамки с ключами. - person philkark; 30.01.2015