Оптимизируем систему обнаружения коллизий

Во время рефакторинга системы обнаружения коллизий, я сделал несколько замеров производительности, чтобы выявить наиболее медленные места. Ранее я ни разу этим не занимался, как написал систему, так она и работала все это время. Честно говоря, тогда я даже слабо понимал за счет чего выбранные алгоритмы работают эффективно, поэтому легко мог что-то проглядеть и накосячить.

Оказалось, что самая медленная часть системы была не в тестировании пар и не в широкой фазе, а на этапе подготовки данных. При изменении координат объекта, нужно внести изменения во все структуры данных, которые используются под капотом системы коллизий для представления объекта. В частности, нужно обновить границы объекта в отсортированных списках, которые используются на широкой фазе. Тут я видимо устал, когда писал эту логику несколькими годами ранее и не придумал ничего лучше, чем проходиться по всему списку и искать запись, соответствующую объекту и вносить изменения. Отсюда вылез N^2 на такой простой задаче. Для устранения проблемы я завел мапу, в которой, по идентификатору актора, дублируется запись из сортировочного списка. Ссылка на запись в мапе и в списке одна и та же, поэтому перебирать список больше не надо, достаточно обновить нужное поле с координатами.

В дополнение к этому, я решил больше не использовать стандартную функцию сортировки и написал собственную сортировку вставками. Как я рассказывал ранее, в данном случае она подходит очень хорошо, поскольку отрабатывает за линейное время на почти отсортированном массиве. Завязываться при этом на сортировку, которая используется в конкретном браузере не хочется, поскольку в браузерном движке может быть реализация, которая здесь не очень подходит.

Последняя деталь, которая, пожалуй, еще сильнее смахивает на микрооптимизацию, но тем не менее дала небольшой прирост — это доработка массива для хранения пересекающихся пар. Каждую итерацию движка я создавал новый массив и пушил в него пересекающиеся пары, которые прошли все тесты. Чтобы сократить время на выделении памяти, я избавился от нового массива и начал перезаписывать значения по индексу. Если длина массива в конце итерации отличается от того, что было в прошлый раз, то записываю актуальный размер в поле length чтобы избавиться от лишних объектов.

Наибольший прирост в производительности, ожидаемо, дала именно первая правка, но и последующие две также внесли свой вклад. На душе стало немного спокойнее, я освежил в памяти детали устройства системы коллизий, лучше стал понимать некоторые нюансы используемых алгоритмов, и более сознательно все протестировал. Ранее я скорее полагался на то, что так надо делать, потому что так написано в учебниках. Ну а теперь можно перейти от оптимизаций к новым фичам, к примеру надо уже научиться поворачивать коллайдеры, ведь для этого все необходимое уже есть.