Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: Add viewport versions #640

Merged
merged 2 commits into from
Jul 27, 2023
Merged

feat: Add viewport versions #640

merged 2 commits into from
Jul 27, 2023

Conversation

mwaddell
Copy link
Contributor

@mwaddell mwaddell commented May 23, 2023

I am seeing the same issue as @leighhalliday with respect to performance degradation with very large datasets when using the SuperCluster algorithm and also with the Grid algorithm when beyond maxZoom.

This PR adds a new SuperClusterViewportAlgorithm which extends AbstractViewportAlgorithm and is "viewport aware" (like GridAlgorithm).

Fixes #136, #417, #419

Replaces #570 (I recreated this in my personal repo instead of my corporate to allow edits by the maintainers).

Copy link
Contributor

@vicb vicb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hey,

That's a great PR.
I'm a new user of this repo (not affiliated to the project) and I would like to see this move forward.
I have added some inline comments - hopefully some of them are relevant.

Do you think there should be different commits or that they are not independent and should be merged into a single one?

Thanks!

src/algorithms/core.ts Outdated Show resolved Hide resolved
src/algorithms/core.ts Outdated Show resolved Hide resolved
src/algorithms/noop.ts Outdated Show resolved Hide resolved
src/markerclusterer.ts Outdated Show resolved Hide resolved
@mwaddell
Copy link
Contributor Author

I addressed @vicb's comments and rebased everything into a single commit

@vicb
Copy link
Contributor

vicb commented May 31, 2023

If my understanding is correct clustering might change with SuperClusterAlgorithm when panning (because the viewport changes).

This would cause flickering that does not exist today on panning.

If I am right then we should fix the flickering issue before merging this PR.

I have the flickering fixed for single cluster locally. I hope I can fully fix the flickering issue by next week (single + group clusters).

@kevgrig
Copy link

kevgrig commented Jun 1, 2023

Yes, there is flickering. It's better than the extreme performance delays before this solution, but I had also been thinking about potential fixes to the flickering. One idea includes increasing the bounding box when calculating beyond the viewport and then only re-calculating if panning outside the calculated bounds. The amount to expand the bounding box could be inversely proportional to zoom level to make the performance impact relatively independent of zoom.

Personally, I don't see myself going back to the old behavior as any flickering is vastly better than terrible performance, but it might be worth adding a configuration switch to use the old behavior in case someone doesn't like the new behavior or it can't be tuned sufficiently.

@vicb
Copy link
Contributor

vicb commented Jun 1, 2023

I have just created #660 to reduce flickering.

It would be nice if someone can try it on top of this PR and report if it improves the situation.

Thanks.

@vicb
Copy link
Contributor

vicb commented Jun 1, 2023

The amount to expand the bounding box could be inversely proportional to zoom level to make the performance impact relatively independent of zoom.

If I understand correctly the viewport padding used by this library is expressed in screen pixels so independent of the zoom level.

Copy link
Contributor

@vicb vicb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I added some review comments.

It's taking me some time/effort to wrap my head around this PR.

It seems like it's solving 2 different issues:

  1. Filtering individual markers when the zoom >= max,
  2. Filtering the markers taking into account to create the clusters when zoom < max.

Why I understand that those are linked I think it would be useful to tackle them in different commits.

I'm thinking that 1 might not be needed with advanced markers that look to be faster when they are off screen.

For 2 filtering the source markers will change the stats and how the clusters are rendered. Maybe that's what you want but maybe not - at least the behavior is different from the current one. So it would make sense to have an option.

Probably the first things to add to this PR are examples for both 1 and 2 so that it's easier to see effect of the changes?

I also have the feeling that forceRecalculate is a hack that should not be needed.

Another feeling that I have is that the Viewport algo should rather use composition than inheritance.

src/algorithms/core.ts Outdated Show resolved Hide resolved
src/algorithms/core.ts Outdated Show resolved Hide resolved
src/algorithms/core.ts Outdated Show resolved Hide resolved
src/algorithms/supercluster.ts Outdated Show resolved Hide resolved
@mwaddell
Copy link
Contributor Author

It's taking me some time/effort to wrap my head around this PR.

It seems like it's solving 2 different issues:

  1. Filtering individual markers when the zoom >= max,
  2. Filtering the markers taking into account to create the clusters when zoom < max.

The goal of this PR is to address the performance issue that makes markercluster unusable for any application where you have more than a few thousand points.

For example...

Here is a jsfiddle for leaflet's 10,000 point clustering example dataset:
https://jsfiddle.net/mjwaddell/2z6xju5q/2/

Here is a jsfiddle for js-markerclusterer using the exact same example dataset:
https://jsfiddle.net/mjwaddell/e6btkgp3/29/

They both render just fine at their initial resolution, but if you zoom all the way in to see individual points and then try to pan around or zoom back out, the leaflet one remains responsive while the markerclusterer one quickly hangs the browser and/or crashes the page entirely.

I don't believe that this is an issue with supercluster, since it clearly handles millions of points - https://blog.mapbox.com/clustering-millions-of-points-on-a-map-with-supercluster-272046ec5c97

Therefore, I believe the cause of this that the markercluster Algorithm implementations are not viewport aware, so when the user zooms way in, the browser is trying to render every individual point even those which are well outside of the viewport.

The GridAlgorithm is the only one which is currently "viewport aware", so the goal of this PR was to make the "noop" algorithm and the "supercluster" algorithm each "viewport aware." That way, if you're beyond the maximum zoom level for clustering, the "noop" algorithm won't try to display all 10,000 points and if you're just inside that maximum zoom level (where supercluster's tree hierarchy might contain thousands of small clusters), it similarly won't try to display all of those outside of the viewbox.

I had initially tried to address this issue solely by creating a new SuperClusterViewportAlgorithm so that this change would be entirely optional and could be enabled just for use cases where there are lots of points. However, this doesn't work when you go beyond the max zoom because then it uses the "noop" algorithm which is not viewport aware. So that would need to be changed too.

I suppose this could be better broken into 2 PRs. The first one makes the "noop" algorithm viewport aware and the second one either modifies the existing SuperCluster algorithm or creates an entirely separate viewport aware version.

Which would you prefer?

@vicb
Copy link
Contributor

vicb commented Jun 13, 2023

Check this version using advanced markers:

https://jsfiddle.net/vicber/fm1awqL4/5/

And you'll see it's much faster.

Legacy markers are slow especially when you use a label.

I still think that we should add:

  • An example using legacy markers (from your fiddle),
  • An example using advanced markers (from the fiddle above + need to re-add some the labels),
  • An example using leaflet as a benchmark (@amuramoto I think this should be ok?)

In my opinion grid and super cluster should not be viewport aware.

What we should do is create a viewport aware algo which then delegate to another algo. It would first filter the marker in the padded viewport and forward the results to the algo passed as an option.

This would be much more flexible.

I definitely think this.state.zoom > this.maxZoom && state.zoom > this.maxZoom is a bug. It can be handled in a separate commit or PR.

Thoughts?

@mwaddell
Copy link
Contributor Author

Check this version using advanced markers:

https://jsfiddle.net/vicber/fm1awqL4/5/

And you'll see it's much faster.

Legacy markers are slow especially when you use a label.

Wow, I didn't realize that the advanced markers made that much of a difference. Since the whole point of markerclusterer is to support dynamically grouping large numbers of markers, I think that all of the examples and documentation for markerclusterer should recommend using those. I had assumed that using "advanced markers" would have made the map less efficient than using "plain" markers, so I hadn't considered trying them.

I still think that we should add:

  • An example using legacy markers (from your fiddle),
  • An example using advanced markers (from the fiddle above + need to re-add some the labels),
  • An example using leaflet as a benchmark (@amuramoto I think this should be ok?)

I agree that showing an example using advanced markers and recommending them when you have a very large number of points is a great idea.

In my opinion grid and super cluster should not be viewport aware.

What we should do is create a viewport aware algo which then delegate to another algo. It would first filter the marker in the padded viewport and forward the results to the algo passed as an option.

This would be much more flexible.

That was my original idea when I first started poking at this back in March, but it ended up being far worse for performance when using supercluster because supercluster runs in a hierarchy, so it's actually more efficient to let it build out the whole hierarchy initially and then just ask it for the clusters within a viewport rather than forcing it to rebuild the entire hierarchy every time you pan/zoom around.

However, note that grid is already viewport aware.

I definitely think this.state.zoom > this.maxZoom && state.zoom > this.maxZoom is a bug. It can be handled in a separate commit or PR.

Yes, I agree - that's how it was in grid and I was trying to migrate that viewport awareness that was unique to grid into the other algorithms.

@vicb
Copy link
Contributor

vicb commented Jun 13, 2023

I think that all of the examples and documentation for markerclusterer should recommend using those.

I sent CL to upgrade all the examples over the past weeks.
Agreed that it would be nice to update the docs too.

I agree that showing an example using advanced markers and recommending them when you have a very large number of points is a great idea.

Yes that + it would be helpful to be able to see the effects of the current CL before merging the changes (with legacy + advanced markers and compare with leaflet).

That was my original idea when I first started poking at this back in March, but it ended up being far worse for performance when using supercluster because supercluster runs in a hierarchy

Oh I overlooked that. Thanks for the clarification.
What about documenting that in the source code of the algo?

Also see #677 for grid max zoom

@mwaddell
Copy link
Contributor Author

Closing in favor of #678 and using advanced markers.

@mwaddell mwaddell closed this Jun 15, 2023
@mwaddell mwaddell deleted the AddViewportVersions branch June 15, 2023 14:00
@vicb
Copy link
Contributor

vicb commented Jun 15, 2023

I think this PR still has valuable changes - at least for people using legacy markers.

@mwaddell mwaddell restored the AddViewportVersions branch June 15, 2023 15:10
@mwaddell mwaddell reopened this Jun 15, 2023
@mwaddell
Copy link
Contributor Author

I think this PR still has valuable changes - at least for people using legacy markers.

I'll give some thought to how this PR could be done as a separate algorithm implementation that doesn't require changes to core functionality then.

@mwaddell mwaddell requested a review from a team as a code owner June 15, 2023 16:45
@mwaddell mwaddell requested a review from wangela June 15, 2023 16:45
@mwaddell
Copy link
Contributor Author

I think this PR still has valuable changes - at least for people using legacy markers.

I'll give some thought to how this PR could be done as a separate algorithm implementation that doesn't require changes to core functionality then.

Okay - I consolidated all of my changes into a separate "SuperClusterViewportAlgorithm" that is entirely optional and doesn't require any other changes to any core functionality.

@mwaddell mwaddell requested a review from vicb June 16, 2023 03:07
@mwaddell
Copy link
Contributor Author

mwaddell commented Jun 17, 2023

I have added some comments.

I addressed your comments - let me know if you have additional feedback.

Maybe we should run some quick perf tests before merging this PR.

I've been testing this in my own application with ~50,000 locations and when using SuperClusterAlgorithm, it's barely usable (virtually the same performance as GridAlgorithm). When using SuperClusterViewportAlgorithm, it's a bit slower than I'd like, but entirely usable.

My understanding is that the main boost comes from the fact that we do not add too many markers (single or cluster) to the map but only the ones that are ~in the viewport.

Correct

Would filtering the visible markers in MarkerClusterer.render() have the same effect? (i.e. call bounds.contains(marker.position) for visible markers). The implementation of that would be really simple.

Also my guess is that the speed boost is significant only for legacy markers. So it might be worth making this code conditional.

What are you thoughts Michael?

I think that the SuperClusterViewportAlgorithm would be slightly faster because it's passing the viewport directly to SuperCluster and then only receiving the relevant clusters instead of receiving all of them every time and having to filter them out later. It also ensures that this viewport implementation is entirely optional.

@vicb
Copy link
Contributor

vicb commented Jun 23, 2023

I addressed your comments - let me know if you have additional feedback.

I've been testing this in my own application with ~50,000 locations and when using SuperClusterAlgorithm ...

I think you should add an example of ~50k marker barely usable as a starting point. Then we can see what needs to be improved (legacy marker vs advanced markers, ...)

let me know if you have additional feedback.

viewportPadding = 60,

I don't think this is a reasonable default.
You will not see any markers when panning the map over 60px which sounds quite low.
I think a good default value would be the viewport dimension.
You then should be able to pan / zoom out a full level without seeing new marker appearing.

I think that the SuperClusterViewportAlgorithm would be slightly faster ...

I think creating more clusters & filtering by lat/lon (viewport + padding) should be a pretty cheap operation.
Back to my first comment of the post it would be an easy thing to try if there is an example.
It is often hard to guess what is best for perf without actually trying on a real use case.

@wangela wangela assigned wangela and unassigned amuramoto Jun 26, 2023
@findhumane
Copy link

@vicb

Check this version using advanced markers:

https://jsfiddle.net/vicber/fm1awqL4/5/

And you'll see it's much faster.

I tried switching to google.maps.marker.AdvancedMarkerElement (using @googlemaps/markerclusterer@2.3.1) and it's about 10X slower than google.maps.Marker. I'm coming from Expo so the reproduction is a bit different but should be straightforward:

  1. git clone https://github.com/findhumane/testexpogmaps
  2. cd testexpogmaps/
  3. npm install
  4. npm run web
  5. Observe loading takes about 10 seconds.
  6. Ctrl^C in the npm window
  7. Restart in legacy mode to use google.maps.Marker instead:
    LEGACY=true npm run web
    
  8. Observe loading takes about 1 second.

Relevant source is here: https://github.com/findhumane/testexpogmaps/blob/70232f22960ad54faf12e59cb7b99b97ad3dce18/App.js#L33-L47

Loading ~21K locations from here: https://github.com/findhumane/testexpogmaps/blob/70232f22960ad54faf12e59cb7b99b97ad3dce18/locations.json

@vicb
Copy link
Contributor

vicb commented Jul 4, 2023

First thing to try would be a standalone site only creating markers (ie do not even use the clusterer).
This would help root causing why it is slow.
I think some of the examples use 10k markers and they definitely do not take 10s.

Also a bit of digging in the performance from the dev console would help if you're familiar with that.

But that's definitely something wrong with 10s for 20k markers.

@findhumane
Copy link

findhumane commented Jul 4, 2023

First thing to try would be a standalone site only creating markers (ie do not even use the clusterer).

Much worse performance. Probably because I'm setting the map zoom to continent level (5).

Also a bit of digging in the performance from the dev console would help if you're familiar with that.

I find it hard to control the Chrome profiler start and stop but here's about 4 seconds captured during the delay in Chrome and the largest chunk is bIjs and below are the top 4 heaviest functions it calls. The second column is Total Time.
 

373.5 ms  7.3 % | 4156.4 ms 81.7 % | bIjs?libraries=marker&v=beta&callback=google.maps.__ib__:136:273 |  
36.7 ms   0.7 % | 1890.6 ms 37.2 % |   set contentjs?libraries=marker&v=beta&callback=google.maps.__ib__:141:288 |  
31.8 ms   0.6 % | 713.2 ms  14.0 % |   set positionjs?libraries=marker&v=beta&callback=google.maps.__ib__:145:326 |  
11.1 ms   0.2 % | 598.3 ms  11.8 % |   set mapjs?libraries=marker&v=beta&callback=google.maps.__ib__:143:425 |  
19.1 ms   0.4 % | 144.4 ms   2.8 % |   _.Mjjs?libraries=marker&v=beta&callback=google.maps.__ib__:393:143 |  

Chrome profiler export: Trace-20230703T221601.json.zip

Firefox profiler output flame graph shows similar symptoms: https://share.firefox.dev/3PJwvTO

Screenshot_20230703_220811

@vicb
Copy link
Contributor

vicb commented Jul 4, 2023

I'm not in front of a computer but from what you say it looks like the problem is not from the clusterer but from trying to display a lot of markers.

From the top of my head I think not setting the map property on the markets would help. It would not add them to the map. But then the clusterer should add isolated markers and clusters to the map that would be much less than 21k markers and should be significantly faster.

@findhumane
Copy link

findhumane commented Jul 4, 2023

I'm not in front of a computer but from what you say it looks like the problem is not from the clusterer but from trying to display a lot of markers.

Makes sense.

From the top of my head I think not setting the map property on the markets would help. It would not add them to the map.

Same results after removing map from the marker constructor: ~10s for AdvancedMarkerElement and nearly instantaneous for Marker.

But then the clusterer should add isolated markers and clusters to the map that would be much less than 21k markers and should be significantly faster.

Right, MarkerClusterer is usable with Marker and unusable with AdvancedMarkerElement.

This is orthogonal to the original problem of poor performance at a high zoom. I was in the process of trying to reproduce that issue but I started by simply baselining the two different markers, and AdvancedMarkerElement is much slower in this test.

@vicb
Copy link
Contributor

vicb commented Jul 4, 2023

Oh one last thing you can try is to patch in #660 that has only been merged in the beta branch.

@findhumane
Copy link

Oh one last thing you can try is to patch in #660 that has only been merged in the beta branch.

Still ~10 seconds for AdvancedMarkerElement with @googlemaps/markerclusterer@2.2.0-beta.2

@vicb
Copy link
Contributor

vicb commented Jul 5, 2023

@findhumane could you please create another issue to track that.

I have updated the bench-advanced example to create 20k markers.

Creating the markers takes ~4.5s when the map is set or ~3.2s when the map is null on my machine.

That seems to be similar to what your observe and be linked to the Google Maps JS API, not this clusterer library.

I would encourage you to report the issue where indicated here. I think it would help if you can come with standalone pages showing the perf for legacy and advanced markers.

Thanks

@kevgrig
Copy link

kevgrig commented Jul 6, 2023

could you please create another issue to track that.

Yes, I'll try to reproduce standalone and create an issue with the Maps JS API. My goal in bringing it up here is that there was an earlier suggestion of changing Marker to AdvancedMarkerElement and it seems the premise of that is flawed, so I hope work continues on this PR to help with Marker usage. I'm currently successfully using an older version of this PR. Thanks!

@mwaddell
Copy link
Contributor Author

mwaddell commented Jul 6, 2023

I addressed your comments - let me know if you have additional feedback.

I've been testing this in my own application with ~50,000 locations and when using SuperClusterAlgorithm ...

I think you should add an example of ~50k marker barely usable as a starting point. Then we can see what needs to be improved (legacy marker vs advanced markers, ...)

I pulled together an example of ~25k markers from my data which are completely unusable using standard markers. It's deployed here: https://brave-pond-09433df10.3.azurestaticapps.net/

  • With standard markers it finishes rendering in 10-15 minutes (if at all)
  • With advanced markers it takes 8 seconds
  • With the code from this PR and standard markers it takes 2 seconds
  • With the code from this PR and advanced markers it takes 6 seconds

So, with this dataset, the viewport-aware supercluster algorithm is the clear winner.

let me know if you have additional feedback.

viewportPadding = 60,

I don't think this is a reasonable default. You will not see any markers when panning the map over 60px which sounds quite low. I think a good default value would be the viewport dimension. You then should be able to pan / zoom out a full level without seeing new marker appearing.

I used 60 because that's the viewportPadding default from the existing GridClusterer which was the only algorithm that used a viewport. If we change it for this, we should probably change it there too for consistency.

I think that the SuperClusterViewportAlgorithm would be slightly faster ...

I think creating more clusters & filtering by lat/lon (viewport + padding) should be a pretty cheap operation. Back to my first comment of the post it would be an easy thing to try if there is an example. It is often hard to guess what is best for perf without actually trying on a real use case.

That is a good point, however, I'm not sure that implementing a viewport filter inside of markerclusterer is the right approach since that would make it universally applied to all algorithms including GridClusterer which already has its own viewport filtering which cannot be done after-the-fact the way that supercluster's can. I think having the flexibility to algorithms to do their own viewport filtering (or not) might be a good thing.

Copy link
Contributor

@vicb vicb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this PR is great and should be merged.
It adds a faster option on top of the existing stuff.
What I would like to see is an added example with/without using the viewport version.

(Sorry for the delay in reviewing).

...options,
});

this.state = { zoom: -1, view: [0, 0, 0, 0] };
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

move that l 51?

@amuramoto amuramoto changed the title Add viewport versions feat: Add viewport versions Jul 27, 2023
@amuramoto amuramoto merged commit fc8e8dd into googlemaps:main Jul 27, 2023
googlemaps-bot pushed a commit that referenced this pull request Jul 27, 2023
## [2.4.0](v2.3.2...v2.4.0) (2023-07-27)

### Features

* Adding viewport aware version of SuperCluster algorithm for use with legacy markers ([#640](#640)) ([fc8e8dd](fc8e8dd))

### Miscellaneous Chores

* **deps-dev:** bump @babel/preset-env from 7.22.7 to 7.22.9 ([#701](#701)) ([496ae06](496ae06))
* **deps-dev:** bump @rollup/plugin-commonjs from 25.0.2 to 25.0.3 ([#707](#707)) ([d004a3a](d004a3a))
* **deps-dev:** bump eslint from 8.44.0 to 8.45.0 ([#703](#703)) ([12ac633](12ac633))
* **deps-dev:** bump eslint-plugin-jest from 27.2.2 to 27.2.3 ([#702](#702)) ([68ff918](68ff918))
* **deps-dev:** bump word-wrap from 1.2.3 to 1.2.4 ([#705](#705)) ([0ba3e66](0ba3e66))
github-actions bot pushed a commit that referenced this pull request Jul 27, 2023
@googlemaps-bot
Copy link
Contributor

🎉 This PR is included in version 2.4.0 🎉

The release is available on:

Your semantic-release bot 📦🚀

@mwaddell mwaddell deleted the AddViewportVersions branch July 27, 2023 18:17
@amuramoto
Copy link
Member

Thanks a ton for all the work and iteration on this @mwaddell and @vicb

@davidpadych
Copy link

How can I use the new options including the bounding box? With standard use and the new version 2.4.0, it still shows me only zoom in the state... thank you

@mwaddell
Copy link
Contributor Author

@davidpadych See #709 for an example using this.

@oawebdev
Copy link

oawebdev commented Mar 5, 2024

Hello!
With SuperClusterViewportAlgorithm cluster icons are flickering on drag and if I change marker icon on mouseover event or click.
https://brave-pond-09433df10.3.azurestaticapps.net/25k-viewport.html flickering on drag is visible here.
Please, suggest how to fix it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Option for SuperClusterer algorithm bounding box
9 participants