Marker calulations are heavy

[TheLastGimbus]

Hi there!
For quite a time, I'm reaserching performance of flutter_map when throwing a lot of markers at it

Recently, I created a library for drawing markers on Canvas instead of widgets, and it's performing pretty well. You can check it out at dev branch (tho it uses flutter_map fork for now 😬 ) https://github.com/KanarekApp/flutter_map_fast_markers/tree/dev

But it turns out, that, even if you don't draw makers at all, the calulations that translate LatLng to X Y position on the screen are taking me to <30 fps @5k markers (when not drawing them at all!)

I copy-pasted the calulations from original markers, but I can modify them - however, I have no idea how.

Does anyone have an idea how they could be optimized?

[ibrierley]

First pondering would be to see if anyone has done similar with Leaflet.js maybe ?

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[TheLastGimbus]

No dear bot, they are still heavy indeed

[aytunch]

Would using clustering help since it would decrease the number of markers being rendered on the screen?
Also if a marker is not in bounds, they are not rendered right?

[TheLastGimbus]

using clustering

Yeah I need to check it out. Tho the existing library for them looks complicated 👉 👈

not in bounds, they are not rendered right?

Yup. Tho:

the calulations that translate LatLng to X Y position on the screen are taking me to <30 fps @5k markers (when not drawing them at all!) ~Me

The caluculations that are required to know if marker is visible are heavy themselves

[ibrierley]

Thinking out loud, a few random bits....I have no idea if this makes sense yet to me, let alone others... :D. Suppose you were to take the highest tile zoom level eg 17, and calculate at first time only which level 17 tile it would be contained within (I guess be careful of markers that overlap tiles though..).

If we know a marker belongs to tile x/y/z = 1024/30/17 we should be able to calculate "fairly" fast if that tile is contained within a certain range at zoom level 12 (eg 356-358/12-14/16) or whatever (as each tile zoom just raises a power of 2)?

I'm not quite sure if it makes sense, and if it would be faster than the projection calcs, but I think you'd only need to figure it out on a tile change (ie panning within same set of tiles wouldn't need "any" recalculations at all).

Basically like a grid eliminator, similar to geohashing (eg https://www.ibm.com/docs/en/db2/11.5?topic=concepts-geohashes-geohash-covers ). I guess I'm trying to figure if a tile is sort of like a geohash (or are the tiles redherrings and could simply use geohashing ?) Something a bit like this... https://stackoverflow.com/questions/36705355/finding-geohashes-of-certain-length-within-radius-from-a-point.

Again, sorry it's a bit random, just prodding a few thoughts.

[ibrierley]

In fact, I think the tile stuff is indeed a redherring...and maybe geohashing the markers at first, then on an geohash area change, recheck them which could eliminate a lot. It's not trivial, but could be interesting, just depends if it's worth the effort to investigate. There's a dart geohash lib https://pub.dev/packages/dart_geohash...

So for example if we look at the pic on https://gis.stackexchange.com/questions/231719/calculating-optimal-geohash-precision-from-bounding-box

lets say we have a point which is geohash "gce46hy7" and we are looking roughly at a map of the UK, you may test points that start with the strings gf or gc or gb or u0, u1, u4.... so "gce46hy7" starts with "gc" so is inside and passes the test. If we have a point "eg5qr5y" it starts with "eg" which isn't part of that set, so would be excluded.

Not sure if I'm barking up the wrong tree, or if its slower, but again, I think you would only need to do a test when the map moves across to a new set of geohash strings.

Clear as mud I hope :D

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[TheLastGimbus]

Still an issue 😕

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[TheLastGimbus]

Can someone disable this bot...

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[Y0ngg4n]

can i use the https://github.com/KanarekApp/flutter_map_fast_markers/tree/dev allready or is it under development currently?

[TheLastGimbus]

@Y0ngg4n We use it at Canary app and so far been very satisfied - if you avoid heavy drawings like shadows and stick to simple shapes like circles etc you can have ~4k markers on most phones without bigger problems 👍

The API of how you do the drawing may change, but will still rely on canvas (99% same)

[Y0ngg4n]

@TheLastGimbus the fork seems to be some commits behind. is it possible to update it to the latest?
Can i use it with the cluster plugin?

[Y0ngg4n]

I have tried with clustering. But it seems to make no difference if using clustering or not 🤔.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[TheLastGimbus]

I will kill you. No, do not close this.

[ibrierley]

So where is this currently, doesn't the fast_markers get around the problem by caching and not having to recalculate every frame ? Just trying to remember what's outstanding on the issue.

[TheLastGimbus]

I think everything what i said above stands. All cache optimizations that I made were already merged here in #826 - everything is sitll heavy even with them

[Y0ngg4n]

I use clustering, but clustering does not reduce the lag.

[ibrierley]

So how many markers would typically be displayed on your screen with clustering ?

It feels like there's 2 things here, so trying to be careful not to get them mixed up....calculations which a plugin may use (eg cluster plugin, and really that's down to the plugin to resolve) and the flutter_map markers which can use caching.

[ibrierley]

Just to clarify a bit that. I think the key is, the calculations aren't likely to change much. The key imo is not to do the calculations in the first place (by caching, grouping, breaking down into areas etc, well you probably need to do them once at least, but not every frame).

[Y0ngg4n]

With clustering around 200-500. But clustering did not helped. It lagged the same as before.

[ibrierley]

Do you have some example test data for the 100k or so markers ?

[ibrierley]

So, out of interest, I hacked up an example I did with a tile slicing proof of concept plugin I did, and tiled clusters. I just wanted to get an idea of what could be possible if energy was put into it. It's not production ready (there are some flaws in this method), and probably never will be if it's just left to me :D, but I would be happy to help out with the concept if anyone gets interested.

This uses 100,000 markers saved into a geojson map (it fell over at 1 million, but there may be optimisations to be done). Note, it's a bit slow for the first few seconds whilst calculating and downloading new tiles, and icons aren't properly centred etc.

https://youtube.com/shorts/mI9g-Kvkv64

[Y0ngg4n]

no i fetch them from the database.
I have done a workaround to only fetch the points that are in a certain range to fix it. but i am not quite happy with it.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 5 days.

[JaffaKetchup]

@TheLastGimbus Chatting to the bot again I see :D.

We haven't forgotten about this, we're just not sure what to do! Also I think @ibrierley has those projects he mentioned above, but not sure how far along those are?

[JaffaKetchup]

Bot says:

My vacation is going stale because it has also been raining here for 30 days. If it doesn't stop within 5 days, I might have to stop the vacation, and come and visit you (:)). Children are doing very well thank you.

Enjoy yourself!

Anyone reading in on this, don't worry about it. None of us have gone insane.

[ibrierley]

If anyone has a specific problem they want to create a minimal example of, I suspect it will get more traction. Currently it's hard to know who is using clusters, who is trying to get 100,000 widgets (of what?) displayed on zoom level 0, who is trying to get 200 displayed spread across the map. Are the markers static or dynamic (i.e how much caching can be used etc). So realistically as I've said before, I don't think this issue is really going anywhere without more focus (as it currently is). If they are using FM Markers and it's using caching, how are the calculations heavy etc.

[mootw]

I did some performance benchmarks on this branch #1333 and my conclusion is that out of the rendering time, bounds checking is small. On my Note 20 on the example app projecting and bounds checking the 5,000 points takes only 5ms total (200 fps), often less, out of a 17ms frame time (55 fps).
Basically by far the heaviest part of displaying 5000 markers is rendering them to the screen, not checking if they are there. Your issue is most likely the markers you are trying to render are simply too heavy. That isn't something that can be optimized other than not rendering all of them.

If you need to render more than 5k or so markers then you need to cluster them. I cannot say anything about the clustering plugin performance, but my guess is if it is properly optimized it could handle in the range of 50k points on mobile.

This issue should be closed and re-opened on the clustering plugin if you are having performance issues with clustering.

[JaffaKetchup]

Ok, I'm going to close this for now. There might be some improvements coming from #1333 in the near future.

[rorystephenson]

@Y0ngg4n and @TheLastGimbus I'm not sure where you ended up with these performance issues but I just wanted to let you know that I've been working on a new clustering layer which is, at least in my testing, very fast. I'm currently working with around 10,000 points and they are reasonably clustered so I'd be curious to know how this performs for you with more points.

If there are still performance issues then the next step would be using a painter to render the markers rather than using widgets. There would be a couple of tradeoffs like not being able to maintain state for markers and needing to add some hit-testing code for marker taps but I think there would be a pretty big difference in performance.

I should also mention that the indexes which are used to make the clustering package fast could be used for a plain marker layer asa well if you are not interested in clustering. I'm happy to share an example if you like.

[aytunch]

@rorystephenson thanks for this plugin.

There would be a couple of tradeoffs like not being able to maintain state for markers and needing to add some hit-testing code for marker taps

For my usecase, dynamic widget markers are a must. So I hope the performance is good even without custom paint.

[rorystephenson]

@rorystephenson thanks for this plugin.

There would be a couple of tradeoffs like not being able to maintain state for markers and needing to add some hit-testing code for marker taps

For my usecase, dynamic widget markers are a must. So I hope the performance is good even without custom paint.

Let me know how it goes! If it's still not performing well I'd be happy to try to figure out why.

[TheLastGimbus]

using a painter to render the markers rather than using widgets

Yesss, that's what https://github.com/KanarekApp/flutter_map_fast_markers/ are for. We didn't migrate the library for new version yet, but once we do we'll let know how it performs!

[Pepslee]

using a painter to render the markers rather than using widgets

Yesss, that's what https://github.com/KanarekApp/flutter_map_fast_markers/ are for. We didn't migrate the library for new version yet, but once we do we'll let know how it performs!

Thank you for this awesome feature, it really helpful, because I`m using a lot of markers ~10K.

When you migrate library to flutter_map version 3.0, do you plan to make it as a plugin for flutter_map ?
And how it can interact with cluster plugins ? Seems like it would be needed to remake cluster plugins to render the markers rather then using widgets too.
And what about animated markers using canvas drawing ?

[JaffaKetchup]

Hey @TheLastGimbus 👋. Would you like me to add your plugin to the docs?

[TheLastGimbus]

@JaffaKetchup it would be great!! However, this plugin is currently not migrated to 3.0 at all :/ i will get in touch when I figure it out, okay?

@Pepslee yes, i want it to be a plugin in future. Yes, it would need some custom stuff for clusterization :/

[JaffaKetchup]

Ok @TheLastGimbus. For now I will set it as Beta until everything is sorted :)

[rorystephenson]

@Pepslee yes, i want it to be a plugin in future. Yes, it would need some custom stuff for clusterization :/

The clustering algorithms/logic behind my flutter_map_supercluster plugin is contained in my supercluster plugin which may be useful for you.