N^2 Comparisons in MapPins leads to severe performance drops

[Reag]

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

Environment (please complete the following information):

• Unity version: [2021.3.4f1]
• Maps SDK Package version: [0.11.0]

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]

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.