-
Notifications
You must be signed in to change notification settings - Fork 89
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
Conversation
There was a problem hiding this 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!
I addressed @vicb's comments and rebased everything into a single commit |
If my understanding is correct clustering might change with 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). |
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. |
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. |
If I understand correctly the viewport padding used by this library is expressed in screen pixels so independent of the zoom level. |
There was a problem hiding this 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:
- Filtering individual markers when the zoom >= max,
- 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.
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: Here is a jsfiddle for js-markerclusterer using the exact same example dataset: 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 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? |
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:
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 Thoughts? |
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 agree that showing an example using advanced markers and recommending them when you have a very large number of points is a great idea.
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.
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. |
I sent CL to upgrade all the examples over the past weeks.
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).
Oh I overlooked that. Thanks for the clarification. Also see #677 for grid max zoom |
Closing in favor of #678 and using advanced markers. |
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. |
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, 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.
Correct
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. |
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 don't think this is a reasonable default.
I think creating more clusters & filtering by lat/lon (viewport + padding) should be a pretty cheap operation. |
I tried switching to
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 |
First thing to try would be a standalone site only creating markers (ie do not even use the clusterer). 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. |
Much worse performance. Probably because I'm setting the map zoom to continent level (
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
Chrome profiler export: Trace-20230703T221601.json.zip Firefox profiler output flame graph shows similar symptoms: https://share.firefox.dev/3PJwvTO |
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. |
Makes sense.
Same results after removing
Right, 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 |
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 |
@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 |
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 |
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/
So, with this dataset, the viewport-aware supercluster algorithm is the clear winner.
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.
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. |
There was a problem hiding this 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] }; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
move that l 51?
## [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))
🎉 This PR is included in version 2.4.0 🎉 The release is available on:
Your semantic-release bot 📦🚀 |
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 |
@davidpadych See #709 for an example using this. |
Hello! |
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 extendsAbstractViewportAlgorithm
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).