Bad performance with many overlapping symbols

[rubengees]

maplibre-gl-js version: 5.6.1

browser: Any (tested on Firefox and Chromium)

Steps to Trigger Behavior

1. Add a layer with icon-allow-overlap and add many features to it.
2. Zoom out so they overlap.

Link to Demonstration

https://jsbin.com/cixafubugo/edit?html,output

Expected Behavior

Zooming is lag-free.

Actual Behavior

Zooming when many features overlap has heavy lag. The further zoomed out the worse it is. Moving the map or rotating it works good.

Here is a screenshot from the Firefox profiler:

Almost all time is spent in findMatches. Is optimization possible there?

[tonysmid]

We are experiencing the same issue. Indeed in the findMatches method, returning the symbols from a KDBush index is slow in this case. A lot of the same items at the same place is makes the index inefficient probably. Any chance updating the KDBush node-size would help?

[HarelM]

Thanks for taking the time to open this issue.
This is not new to recent versions, right?

[rubengees]

Thanks for taking the time to open this issue. This is not new to recent versions, right?

Thanks for answering! Yes, right, I can also reproduce on older versions like 4.7.1 that we are using.

[HarelM]

Thanks for looking into previous version. Since this is not a regression it probably means it was always like that. Feel free to take a stab at fixing it. Let me know if you need any help with setting up the project.

[HatulaPro]

I expermimented with it a bit. The findMatches function calls KDBush.range, which returns an array with all the matches. But we only need the first one that fits (i think?), so we're probably doing some extra work there.

I wrote a dirty range function that works with yield and it seemed to make a significant imrpovement.

Opened an issue in KDBush to see what we can do:
mourner/kdbush#49

[HarelM]

I would encourage to open a PR and see if it gets picked up.
You can also try and use patch-package on this repo and run the benchmarks to see if it creates overhead in a different place and also see if it solves the problem.
Let me know if you need help with anything I just mentioned.

[HatulaPro]

I would encourage to open a PR and see if it gets picked up. You can also try and use patch-package on this repo and run the benchmarks to see if it creates overhead in a different place and also see if it solves the problem. Let me know if you need help with anything I just mentioned.

@HarelM Opened a PR here, it seems to make it much better. Let me know what you think :) #6492

[HarelM]

Am I miss reading this or does the PR for kdbush causes a degradation in performance?
In any case, I've pinged the author and I hope this can be incorporated there. Let's see how it goes there. I'd like to avoid using patch-package in production although it's a valid option. I feel like we are forking too much of the dependencies lately, which is a bad sign... I'll see if I can define a plan forward for this.
Thanks for looking into this! I hope to have an answer soon.

[HatulaPro]

Note that there are 2 suggestions for improvement: the maxResults (opened in KDBush), and rangeSome (opened here with patch package).

The KDBush PR makes the general case slightly slower, but makes our case faster. That's why I had preferred adding a new API function (like the one I implemented with patch-package). Both are an improvement, but the rangeSome is a lot better for what we're trying to do

[HarelM]

Why not suggesting to add rangeSome to kdbush then?
If it's an additional call maybe it has a better change to be incorporated as it doesn't degrade existing functionality?

[bradymadden97]

Hey folks, wanted to hop in here since I saw this approach was getting some traction again. I have an alternative approach that doesn't require patches to kdbush and should be more efficient regardless. We're still doing some internal testing with, so I'm not ready to propose it upstream quite yet, but if you wanted to pull it down and give it a try here it is:

bradymadden97#1