amarao_san

Category:

растовое

Догнав своё дерево до 65 µs на 400 точек (165 ns на точку)  я задумался о математике. У меня есть довольно мерзкая функция, которая вычисляет по прямоугольнику и точке в нём, в каком «квадранте» оно находится, и его точные границы.

Это дорогая фукнция. 19.7 ns на вызов. Если у меня дерево с глубиной хотя бы 5, это три вызова на 100 ns (считай, больше половины всего времени добавления точки). Вероятнее всего, после её оптимизации мне придётся заново пересчитывать 'list/tree' отношение, потому что хождение по дереву станет сильно дешевле.

Сейчас она реализована крайне халтурно — сначала генерируются все квадранты в виде массива, потом по ним идёт поиск с помощью функции is_inside, и тогда возвращается индекс найденного и границы этого квадранта. Соответственно, если у нас рандомное распределение точек, то в общем случае половина вычислений делается зря (рассчёт квадрантов).

Очевидное - сохранять эти данные внутри ноды для кеширования (границы каждого квадранта), но это дорого (16 f64).

Я переписал эту функцию, если верить criterion, улучшил до 10ns (я не думаю, что можно сильно быстрее).

После этого бенчмарк для дерева улучшился на 13% (инсерт), 17 и 20% (положительный и отрицательный поиск). В целом, вставление происходит за 53ns на 400 точек (132ns на точку), а поиск за 100ns.

100 ns это примерно 250 тиков. С учётом, что на каждой ноде в дереве надо посчитать разницу и деление в f64, а потом в финале ещё и cmp между флоатами сделать, я не думаю, что тут есть сильно много путей для улучшения.

При этом надо более пристально посмотреть на бенчмарки. Всё-таки 400 точек — это далеко от продакшена, где ожидается порядка 20 миллионов.  Что превращается в грустнейшие 20 секунд (!) на обход всего дерева. Даже с поправкой на 4 ядра — это всё равно 5 секунд. 0.2 fps.

Для боевого кода придётся злобно кешировать ответы где-то в top-level'ах дерева...

У меня есть ещё одна идея для оптимизации. Дерево почему-то quadtree. А кто сказал, что 4 оптимально? У меня, вообще, vec.len() == 11 показало наилучший результат. Может быть, 9tree будет лучше? Или, даже, 15tree?

(На этом отведённое на выходных время Шахеризады заканчивается...)

Error

default userpic

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.