Global collision detection (>0.42.0) regresses performance of rendering very dense symbol layers

[averas]

Based on initial discussion in #5865

Steps to Trigger Behavior

1. Render a fairly dense symbol layer with icons/images
2. Zoom in/out

Demo at https://codepen.io/anon/pen/YYwoKx (change version to 0.41.0 to see how it should work)

Expected Behavior

That performance and visual rendering is similar to that in 0.41.0.

Actual Behavior

Performance is significantly worse in 0.42.0 and later versions. The visual representation is also quite different, even with icon-allow-overlap and icon-ignore-placement set to true which ought to avoid collision detection.

[jfirebaugh]

cc @ChrisLoer

[ChrisLoer]

The visual representation is also quite different, even with icon-allow-overlap and icon-ignore-placement set to true which ought to avoid collision detection.

What's happening here is that when icons are allowed to overlap, we sort them based on their y-position. The architectural changes in #5150 required us to do symbol sorting on the foreground, but the approach we used is limited to sorting within a single segment (see SymbolBucket#sortFeatures). Because this example has so many icons, it overflows a single segment and we have to give up on sorting.

Performance is significantly worse in 0.42.0 and later versions.

Tiles with very high feature density were always expensive for collision detection, but prior to #5150 the expensive work happened on the background, and during zooming in the lower zoom tiles could be used until collision detection finished on higher zoom tiles -- so the effect was to "overzoom" for a while rather than to make "collision detection" frames take a long time to load.

I'm actually getting high frame rates running this codepen (mostly 60 FPS, with some long frames going out to 40-50ms), but I see the gif from #5865 (comment). The long/janky frames in that recording might be "full placement" happening on the foreground. @ansis is working on changes at #5890 that should reduce some of that cost. Hopefully that will help -- and we'll keep looking for other performance improvements in that code. Unfortunately, some of this is built into architectural decisions we made in order to support global collision detection.

For the best performance, ideally you'd generate tiles (or with geojson, use clustering) so that the feature density at any given zoom level isn't that high. I know that may not always be straightforward, though...

[averas]

I'm actually getting high frame rates running this codepen (mostly 60 FPS, with some long frames going out to 40-50ms)

That's odd. It does not perform well at all on my machine, and my users (on less performant computers) had me downgrade faster than quick. I mean, on an i7 Macbook Pro I get:

[Violation] 'requestAnimationFrame' handler took 498ms
[Violation] 'requestAnimationFrame' handler took 257ms
[Violation] 'requestAnimationFrame' handler took 492ms
[Violation] 'requestAnimationFrame' handler took 264ms
[Violation] 'requestAnimationFrame' handler took 490ms
[Violation] 'requestAnimationFrame' handler took 259ms
[Violation] 'requestAnimationFrame' handler took 495ms
[Violation] 'requestAnimationFrame' handler took 273ms
[Violation] 'requestAnimationFrame' handler took 508ms
[Violation] 'requestAnimationFrame' handler took 320ms

Even decreasing the amount of features from 20000 to 5000 keeps it on the slow/judder side for me:
https://codepen.io/anon/pen/mpPbPE

For the best performance, ideally you'd generate tiles (or with geojson, use clustering) so that the feature density at any given zoom level isn't that high. I know that may not always be straightforward, though...

In the example I provided in #5865 the purple layer actually is vector tiles. I only made an artificial GeoJSON layer for the demo since I can't really share that data. Almost all my production use cases make use of heavily cached vector tile sources. Making clusters wouldn't really make sense in this case since we're talking zoom levels where the user expects to see the discrete data (again, look at the example provided in #5865).

If this is an architectural decision and things don't pick up with other improvements (such as #5890) I am in big trouble. Most of my maps with a symbol density similar to the one demonstrated in #5865 are hardly useable on my high end Macbook Pro and with a performance hit like the one from 0.41.0 to 0.42.X I won't be able to upgrade at all.

[ChrisLoer]

Most of my maps with a symbol density similar to the one demonstrated in #5865 are hardly useable on my high end Macbook Pro and with a performance hit like the one from 0.41.0 to 0.42.X I won't be able to upgrade at all.

We definitely want to come up with a solution that will allow you to upgrade (performance fixes and/or workarounds) -- and sorry that it's a bumpy process 😅 . Let me try to make sure I understand your use case as well as possible since I'm guessing a little from the codepen and the gif.

1. Is sorting more than 16,384 symbols (that's one 2^16 vertex buffer segment with 4 vertices per symbol) in a single tile a requirement for you? Although it's related to the same changes, this is a fairly separate problem.
2. In your high-density tiles, the majority of the icons actually have room to display? From the gif it looks like the individual icons might be very small, and that would explain why you can fit so many on the screen at one time. From the codepen, I was assuming that the majority of icons would be "collided" at low zoom, which would be a good opportunity to thin out feature density on lower zoom tiles, but it sounds like that's not actually the case.
3. What "symbol"-like properties do you need to take advantage of for these layers? Do you need collision detection? If not, it might (?) make sense to get the same visual effect using a fill layer with a texture?

[ChrisLoer]

@ansis is working on changes at #5890 that should reduce some of that cost.

I looked a little closer and unfortunately those changes probably won't make that big a difference at least for the codepen use case here. That PR will replace "full placement" with "per-bucket (layer/tile) placement" in order to avoid blocking the foreground, but in your case it's often a single layer on a single tile that's so expensive to place. The PR will still leave us better positioned for further improvements.

[stevage]

FWIW, the example at the top performs fine for me, on my mid-2014 i7 Macbook Pro, Intel Iris Pro (Sierra), in both Firefox and Chrome (slightly better in FF I think). No render warnings.

[ChrisLoer]

Thanks for the extra data point, @stevage!

That PR will replace "full placement" with "per-bucket (layer/tile) placement" in order to avoid blocking the foreground, but in your case it's often a single layer on a single tile that's so expensive to place.

@averas, the changes from #5890 have merged to master now. Although we don't expect that change to make a huge difference as long as all your symbols are in a single layer, it's now possible for you to split the symbols up into multiple layers in order to split the cost of symbol placement across multiple render frames. Splitting into multiple layers could partially address the sorting issue (by getting under 16,384 symbols per layer), but would also introduce the new challenge that the layers would have to be strictly sorted relative to another (so items from layer 1 would always be drawn in front of items from layer 2, regardless of y-position).

[santinogue]

Related to symbols rendering, if I have one symbol layer with several features, does the order of the features in the source should be used used to place the symbols in order? I don't see that the order in the geo-json source is being respected, it looks like a random ordering.

[ChrisLoer]

@santinogue The order of symbols within a layer is determined based on the y-position of the symbol at render time (although ordering is only done per-tile, so the order may shift a little bit at tile boundaries). Also as @averas saw, we have a limit of 16,384 symbols per-tile-per-layer for sorting. If you go over that limit, the sort order is undefined (it's not actually random, but there aren't any good ways to control it).

[santinogue]

The order of symbols within a layer is determined based on the y-position of the symbol at render time

@ChrisLoer so ..., supposing I don't go over the limit, the order in the geojson source should be respected? Sorry but I don't know what is the y-position that you mentioned.

[ChrisLoer]

@santinogue The y-position is where on the screen the symbol gets rendered (so higher symbols go on top of lower symbols). Order in the GeoJSON source doesn't control order of rendering.

[santinogue]

@ChrisLoer thanks, so I don't have a way to control the rendering order apart from grouping the symbols in different layers where I can choose the order. I guess that's the only workaround.

[ChrisLoer]

That's right. We do have an issue open tracking support for user-controlled ordering within a layer, but we don't have a specific strategy for implementing it yet: #1349.