search

microsoft / MapsSDK-Unity

This repository contains samples, documentation, and supporting scripts for Maps SDK, a Microsoft Garage project.
MIT License
648 stars 127 forks source link

N^2 Comparisons in MapPins leads to severe performance drops #183

Closed Reag closed 6 months ago

Reag commented 2 years ago

Describe the bug MapRenderer.UpdateChildrenMapPins() can cause severe slowdows in scenes with a large amount of pinned or dynamic objects. This is caused by a N^2 comparison somewhere in its source.

To Reproduce

  1. Create a new map renderer
  2. Create a set of map pins (Say, 100)
  3. Sample frame rate via Unity Profiler
  4. Increase map pin count to a larger number (Say, 700)
  5. Sample frame rate via Unity Profiler, observe the non linear slowdown

Expected behavior While technically within expected behavior, it would be nice if this drop wasn't exponential. This would allow for more pins to be managed.

Screenshots Sample taken from my test enjoinment with Deep Profiling on. This unity scene contains some 780 map pins. Note the total number of List.Contains() is N^2/2 of the total pin size image

Environment (please complete the following information):

Additional context While this is not technically a bug, it is a slowdown that can occur on complicated scenes. Having a fix for this would be quite nice :D

EDIT Upon further investigation, this issue is caused by the MapRenderer.cs script on lines 394 and 445. Both of these are N^2/2 worst case operations. I attempted to create my own extension to MapRendererBase to test this, and on that run, said slowdown vanished (Though my created script was non functional in other ways). Might I recommend moving these Lists to Sets and using .Intersect? I believe that should attain the same functionality in O(N)ish time.

kircher1 commented 2 years ago

Thanks for the analysis. There's definitely a couple of n^2 loops that could be improved here.

As an alternative to this approach, there is the MapPinLayer component. It is better suited for working with many pins and provides clustering functionality too.