Map gets super laggy when there are a lot of Markers

[TheLastGimbus]

Hi there!

I am currently making an app which will have a lot of markers - around 4000 spread across whole country. After some testing, it got obvious that all of this gets super laggy

When I use all 3.5k markers and zoom on area with no markers at all, and start dragging the map, I get ~12 fps, on phisical Android tablet in profile mode

After some debugging, print()ing and Stopwatch()ing, I traced which parts use the most time:

In lib/src/layer/marker_layer.dart -> MarkerLayer -> build(), there is a for-loop that iterates over all given Markerks:

flutter_map/lib/src/layer/marker_layer.dart

Line 130 in f09b193

for (var markerOpt in markerOpts.markers) {

The whole thing was taking ~25ms, and with Stopwatch(), I traced which parts of loop use the most time:

// I did it like this:
int sumStep = 0;
for(var i in list){
  var w = Stopwatch()..start();
  i.someStep();
  sumStep += w.elapsedMicroseconds();
  w.reset();
  // Of course, some precision is lost, because some steps take 1.something microsecond
}
print('Step: $sumStep');  // Summed microseconds

This was taking around 7500 us:

flutter_map/lib/src/layer/marker_layer.dart

Line 131 in f09b193

var pos = map.project(markerOpt.point);

This 3600:

flutter_map/lib/src/layer/marker_layer.dart

Lines 132 to 133 in f09b193

	pos = pos.multiplyBy(map.getZoomScale(map.zoom, map.zoom)) -
	map.getPixelOrigin();

And the rest around 0:

flutter_map/lib/src/layer/marker_layer.dart

Lines 140 to 152 in f09b193

	if (!_boundsContainsMarker(markerOpt)) {
	continue;
	}
	markers.add(
	Positioned(
	width: markerOpt.width,
	height: markerOpt.height,
	left: pixelPosX,
	top: pixelPosY,
	child: markerOpt.builder(context),
	),
	);

So I started to dig into .project():

flutter_map/lib/src/map/map.dart

Lines 417 to 420 in f09b193

	CustomPoint project(LatLng latlng, [double zoom]) {
	zoom ??= _zoom;
	return options.crs.latLngToPoint(latlng, zoom);
	}

flutter_map/lib/src/geo/crs/crs.dart

Lines 26 to 34 in f09b193

	CustomPoint latLngToPoint(LatLng latlng, double zoom) {
	try {
	var projectedPoint = projection.project(latlng);
	var scale = this.scale(zoom);
	return transformation.transform(projectedPoint, scale.toDouble());
	} catch (e) {
	return CustomPoint(0.0, 0.0);
	}
	}

this.scale() and transformation.transform() don't seem to be expensive - they are only some basic calculations...

So, projection.project:

flutter_map/lib/src/geo/crs/crs.dart

Lines 450 to 456 in f09b193

	@override
	CustomPoint project(LatLng latlng) {
	var point = epsg4326.transform(
	proj4Projection, proj4.Point(x: latlng.longitude, y: latlng.latitude));
	return CustomPoint(point.x, point.y);
	}

https://github.com/maRci002/proj4dart/blob/7eb11da840ce21c78c017e0a89ee0332ba5a60e3/lib/src/classes/projection.dart#L152

Okay... this ^ is big, and not even a part of this repo, so I don't think we can do anything about it...

Conclusions

While re-building MarkerLayer (which happens constantly while dragging the map), we are doing some expensive calculations, which slow down the whole map - that is, calculating some position from LatLng

// I didn't dig into pos.multiply (step which was taking 3600us), and I don't really know what it's doing...

I'm fresh into this project and I don't know much about mapping, but it seems like we could somehow cache just the projection, and apply only scale and transformations - since only them really change when you drag the map

(This generally seems related #768, but discussion there got kinda chaotic, not knowing what issue actually was, so I'm making this separate)

[robertpiosik]

My workaround to this issue was filtering markers based on current map boundaries.

[TheLastGimbus]

Wait, how couldn't I see this before:

In whole loop we:

flutter_map/lib/src/layer/marker_layer.dart

Lines 131 to 142 in f09b193

	var pos = map.project(markerOpt.point);
	pos = pos.multiplyBy(map.getZoomScale(map.zoom, map.zoom)) -
	map.getPixelOrigin();
	var pixelPosX =
	(pos.x - (markerOpt.width - markerOpt.anchor.left)).toDouble();
	var pixelPosY =
	(pos.y - (markerOpt.height - markerOpt.anchor.top)).toDouble();
	if (!_boundsContainsMarker(markerOpt)) {
	continue;
	}

1. Calculate some .project
2. Then some .multiplyBy
3. Then pixelPos - something // This one should be light
   /// Which, from my measurements, all of this can take even 30ms at 5000 makrers
   AND THEN
4. !_boundsContainsMarker:
   

   flutter_map/lib/src/layer/marker_layer.dart

   Lines 113 to 114 in f09b193

   	bool _boundsContainsMarker(Marker marker) {
   	var pixelPoint = map.project(marker.point);

Same .project that took us so long before - just to dismiss previous calculations if markers is not visible

@robertpiosik this diservers much more than a workaround 😳

Edit: Yes, I was able to go from 30->15ms just by moving !_boundsContainsMarker at the top (with 5k markers zoomed so that none visible). Will try also few more caching tricks, but I already open a PR with at least this

[ibrierley]

Yes, that's possibly a good optimisation. Thinking out loud, I'm actually wondering if that could be cached for each zoom level, as we're possibly doing the same map project for each point/zoom each frame ? (would need to verify and test that)

[TheLastGimbus]

@ibrierley a zoom level is a double, soooooo I don't know how this would go...

But, even caching it until zoom changes would be better than nothing...

[ibrierley]

Just thinking out loud a bit more on other optimisations (unfortunately I'm not near a PC I can test on flutter_map for a while), if bounds checking is optimally being done the wrong way around...currently we project every marker point, take the width/height, and do a basic boundary check. The slow bit being the project ?

Could we do the boundary checking on latlongs, not on screenprojected points. So unproject the map boundary corners (they may actually be already available as map.bounds?) to latlongs (so only has to be done once per frame). Figure out the marker delta latlongs to account for width/height for the marker, and calculate (if all the markers are the same, as an optional param that width/height latlong delta could be cached). Then you don't need to do any marker projections at all ?

Not entirely sure if I'm making sense and there's no flaws :D.

[ibrierley]

hmm maybe there's an issue with the calculation of the marker widths and height not taking into account the curvature or something, so maybe a good reason it's not done like that, but maybe it could be a useful custom pre-culling of points by someone when creating their marker lists.

[rorystephenson]

It's not an answer to your question directly but an alternative solution is to use marker clustering (see the clustering plugin listed in the README).

I have less markers (~1300) but it is very fast.

[TheLastGimbus]

The problem is that, even with markers clustering, map lags even when there are no markers visible at all

I currently fixed it in my fork and I'm temporary using it unitl it gets merged

[robertpiosik]

Indeed, clustering doesn't make any difference to perf.

@TheLastGimbus maybe providing a 60fps comparison gif might help gaining some attention

From my experience, original leaflet js deals with thousands of markers very well in the browser, though flutter_map lacks in this area significantly.

[TheLastGimbus]

60fps comparison gif

SEE? THIS IS HOW BAD THIS IS!!! MERGE THIS TO STOP THIS CIRCUS 🤡

I love this 😍 😆 will add soon

original leaflet js deals with thousands of markers very well

This keeps scratching my head. How do some web devs have their maps filled with markers, running 60fps in browser on my shitty phone, meanwhile "super native optimized Flutter cool framework" can't do >100 displayed at once 😖

Maybe doing some "direct Canvas painting magic" would help, but I have 0 motivation to try this now - maybe some day as extra plugin for this

[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 was closed because it has been stalled for 5 days with no activity.