Mapbox-gl-js: Defer shaping and glyph/icon quad construction as late as possible

[ChrisLoer]

Currently, when we prepare the symbol buckets for a tile, we do text shaping for all of the labels, prepare "glyph quads" for them, and store the results as "symbol instances". Then, when it comes time to do placement, we run the collision detection algorithm to determine the subset of symbol instances to show (also we choose whether to show the "upside down" version of each label based on the orientation).

It's common that only a small subset of the labels in a tile are actually showing at any given time^{[citation needed]}, so we're doing a lot of extra work building glyph quads that won't be used. I don't know how much of a performance bottleneck this is, but I remember when I was profiling the arabic shaping changes that this area of code got hot.

Shaping is mostly a pre-requisite for collision detection, but I think it should be possible to do shaping in-line with collision detection. For any given label, we can first test to see if its anchor point would collide with an existing label. If so, there's no need to do shaping. If not, we would do the shaping for that label (and cache the result until the next SymbolBucket::prepare call), and then try to place it.

Glyph and icon quads aren't used by collision detection at all, so we could also defer quad creation until the labels were definitely placed (and again, cache the results so that subsequent calls to place get quicker and quicker as the incremental number of quads to create gets smaller and smaller).

Time to first-render for a tile would ideally be faster because of the avoided work, and in the worst case (every label is fully displayed), it wouldn't be any slower.

SymbolBucket::place could get slower, but only because it was doing work that would have previously been done in SymbolBucket::prepare. This might be a small problem in some cases. If you had a tile displaying upright (and with lots of rotation-alignment: map labels) and then you quickly rotated the map 180 degrees, place would have to make a bunch of new quads, and the slowdown might mean your labels would take longer to be flipped back to "right side up". If the same work had happened in prepare, the tile would have taken longer to show, but you'd never get the "delayed flip" effect.

/cc @anandthakker @1ec5 @mourner

[mollymerp]

Interesting idea @ChrisLoer! I'm not familiar enough with the placement algorithm and its costs to substantively add to discussion, but it would be interesting to see how a change like this would make the implementation of #2703 easier / more complicated.

[ChrisLoer]

Hmm... I'm not sure, but what I have in mind wouldn't change the interface of SymbolBucket and would store data basically the same place it's already being stored -- so my best guess is "slightly more complicated".

[Scarysize]

Nice idea. In the end you probably have to weight the performance improvement against the increased complexity of the bucket code. And from what I've seen it's one of the most complicated parts of the code base already. Though @anandthakker is doing a great job simplifying it 👍

[ChrisLoer]

I decided to poke at this a little -- and it was pretty easy to implement deferred quad creation (I didn't experiment with deferred shaping yet). Before the changes, I profiled a thread loading 11.02/31.1194/121.4547/169.8/9, and on three runs found that prepare and place would take ~165ms, with quad creation being about 30ms of that time. After the changes, running the same profile, I saw the total prepare/place time come down to ~145ms, w/ quad creation being about 10ms.

That seems like a nice little improvement, but it's too small to even reliably measure at the level of total time to map render... so maybe there's some small power consumption benefit of having the worker threads do a little less work, but nothing too exciting.

[ChrisLoer]

No immediate plans to do anything with this, but I pushed the deferred creation code to https://github.com/mapbox/mapbox-gl-js/tree/cloer_defer_quad_creation. It's failing on a single test where a curved label oriented vertically flips orientations (probably need to replace a "<=" with a "<" or something).

I don't think the changes actually add much complexity. The biggest refactoring is inverting the logic for choosing symbol orientations -- instead of filtering out glyphs that don't have the right orientation (vertical/horizontal and right-side-up/upside-down), I figure out the orientation and then choose the glyphs. I think it's a bit easier to understand the orientation logic when it's done in this order.

[ChrisLoer]

The proposed optimization is no longer possible with the architectural changes introduced in #5150. Shaping happens once per tile at layout time and then never again. Because placement is done in the foreground and shaping is relatively expensive, it wouldn't work to defer shaping until placement time.