amarao_san

Category:

производительность enum'ов

Добавление байта (enum'а) к элементу дерева приводит к потере производительности на 19-24% (!) в зависимости от типа теста (в глубину или в ширину).

В сравнении с этим, расширение числа вариантов ноды дерева с 3 до 5 (собственно, добавление того же enum'а в качестве вариантов первого) даёт изменения в 12-14%.

Прям обидно как-то. В целом, попытку перехода с 2x2 квадрантов на 2 половинки с ротацией можно сделать и в рантайме фунций (передачей флага в рекурсивном вызове), но что увличение числа вариантов enum'а так сильно задевает производительность — для меня необъяснимо.

Для пары вариантов (Vertical) просто затыки unimplemented, в остальном чистое переименование. И — и 12% деградация.

Чисто для спортивного интереса я попробвал добавить пустые варианты (без содержимого)

На вставку почти без изменений, а поиск почему-то так же провис на 12%.

Для сравнения — передача направления в райнтаме поменяла показатели в пределах шума (2%).

... Я добавил «поворот»:

let new_dir = match dir{
    Direction::Vertical => Direction::Horizontal,
    Direction::Horizontal => Direction::Vertical
};

И всё просело по сравнению с вариантом без поворота вообще на примерно 2-3%. Теперь надо попробовать добавить поддержку поворота при «нарезании» на куски.

Если кто пропустил, Олег предложил в QuadTree на каждом уровне вместо деления на 4 квадранта, делить на 2 половинки, сначала по X, потом по Y. Это увеличит «древесность» и уменьшит число операций с плавающей запятой, потому что вместо проверки по обоим осям, в каждом случае будет проверка только по одной оси.

А я сейчас пытаюсь придумать, как этот поворот закодировать без последствий для производительности самого дерева.

(Ещё одна фича, которую я думаю попробовать — это резать  узел не на 2 поддерева, а на большее число — например, на 3 или 10, но это потом).


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.