support caching of VectorTileFeatures resolved for a ThemeLayer

[blaugold]

While doing some profiling, I found that around half of the time spent in Renderer.render is evaluating ThemeLayer filters to resolve the features to render for a ThemeLayer. Since themes and tile sets are immutable, it should be possible to cache the resolved features for a Tileset and ThemeLayer pair.

This PR adds a benchmark, which shows that rendering time of a Tileset is cut in half, when this new caching is used:

➜  dart-vector-tile-renderer git:(features-caching-merge) ✗ flutter test test/benchmark/rendering_test.dart 
00:01 +0: loading /Users/gabriel/Dev/dart-vector-tile-renderer/test/benchmark/rendering_test.dart                                                                                                                                                                                
Running benchmarks (repetitions: 100)
RenderPicture(zoom: 0.0, preprocessTile: false, cacheThemeLayerFeatures: false): 1101.84ms
RenderPicture(zoom: 0.0, preprocessTile: true, cacheThemeLayerFeatures: false): 696.50ms
RenderPicture(zoom: 0.0, preprocessTile: false, cacheThemeLayerFeatures: false): 825.19ms
RenderPicture(zoom: 0.0, preprocessTile: true, cacheThemeLayerFeatures: true): 364.88ms
RenderPicture(zoom: 12.0, preprocessTile: false, cacheThemeLayerFeatures: false): 907.45ms
RenderPicture(zoom: 12.0, preprocessTile: true, cacheThemeLayerFeatures: false): 732.52ms
RenderPicture(zoom: 12.0, preprocessTile: false, cacheThemeLayerFeatures: false): 885.24ms
RenderPicture(zoom: 12.0, preprocessTile: true, cacheThemeLayerFeatures: true): 385.51ms
RenderPicture(zoom: 24.0, preprocessTile: false, cacheThemeLayerFeatures: false): 982.47ms
RenderPicture(zoom: 24.0, preprocessTile: true, cacheThemeLayerFeatures: false): 826.22ms
RenderPicture(zoom: 24.0, preprocessTile: false, cacheThemeLayerFeatures: false): 994.00ms
RenderPicture(zoom: 24.0, preprocessTile: true, cacheThemeLayerFeatures: true): 449.70ms

Let me know what you think.

[greensopinion]

@blaugold this is very cool! Nice work. Great to see how a benchmark reveals the results of the improvement that you made!

I've been thinking about this problem but haven't come up with a great solution yet.

I've run the profiler with two different tilesets and two different themes, and found that the results are quite different:

1. Stadia Maps Tiles, Default Theme:

2. Open Zoomstack Tiles, Zoomstack Outdoor Theme

The highlighted (turquoise) stack element in both profiler snapshots is the selector function, i.e. the performance cost addressed in this PR.

My initial take on this is that the zoomstack theme attempts to render a lot more text - which is very expensive due to Paragraph.layout. More digging is needed to know that for sure. Something for a separate investigation.

The high cost of selecting tile features appears to be related to two issues:

1. getting a property from a tile feature (for filtering) is expensive, I'm not sure why (see EvaluationContext.getProperty)
2. the number of operations that occur when selecting tile features to render is a factor of the number of layers in the tile, the number of features in each tile layer, and the number of layers in the theme

The good thing about caching is that we can avoid performing these calculations more than once. The downside is that we have to calculate them once. From what I can gather from reading the code in this PR, that occurs in the preprocessor, which is really nice. Unfortunately preprocessing still runs on the UI thread (just not when rendering a frame).

Alternatives to caching include making getProperty faster, or some kind of indexing. I'm not sure if either are feasible.

Some thoughts about the implementation of this PR specifically:

How do you envision clients of this library managing the lifecycle of ThemeLayerFeatureResolver?

Did you consider reworking Tileset to implement caching directly? The cache could be built up in the preprocessor, and the lifecycle of the cache would be managed directly with the lifecycle of the Tileset. That would integrate well with usage of this library in vector_map_tiles which already manages the lifecycle of the Tileset.

There appears to be some boilerplate in here that could be avoided by using a benchmarking library such as benchmark_harness or benchmark. Any reason not to use one of those?

[blaugold]

My initial take on this is that the zoomstack theme attempts to render a lot more text - which is very expensive due to Paragraph.layout. More digging is needed to know that for sure. Something for a separate investigation.

Probably unrelated to this, but I noticed SymbolPointRenderer loops over points in two nested loops. Is that necessary?

dart-vector-tile-renderer/lib/src/features/symbol_point_renderer.dart

Lines 42 to 43 in b700a0f

	points.forEach((point) {
	points.forEach((point) {

The good thing about caching is that we can avoid performing these calculations more than once. The downside is that we have to calculate them once. From what I can gather from reading the code in this PR, that occurs in the preprocessor, which is really nice. Unfortunately preprocessing still runs on the UI thread (just not when rendering a frame).

As it is currently implemented, to make use of caching, you create a CachingThemeLayerFeatureResolver instance and use that to create a Renderer. The first time a tile is rendered, the resolved features are computed and cached. By creating a Tileset with a preprocessor, that has been created with the resolver instance, the computing and caching can be front loaded.

In general, everything that is not touching dart:ui could be offloaded to another isolate. The recent improvements to isolates have made it much cheaper to spin up isolates and support zero-copy message passing for the object passed to Isolate.exit. I'm not sure, though, if preprocessing (even of complex themes and tiles) eats up enough of the frame budget to cause dropped frames.

Alternatives to caching include making getProperty faster, or some kind of indexing. I'm not sure if either are feasible.

That's true, and getProperty is also used during rendering, but it only makes up ~ half of the time required to resolve features.

How do you envision clients of this library managing the lifecycle of ThemeLayerFeatureResolver?

Did you consider reworking Tileset to implement caching directly? The cache could be built up in the preprocessor, and the lifecycle of the cache would be managed directly with the lifecycle of the Tileset. That would integrate well with usage of this library in vector_map_tiles which already manages the lifecycle of the Tileset.

I expected a widget, for example, which is rendering one or more tiles to evict the cached data when it is disposed.
But it makes a lot of sense to tie the cached data to the Tileset. I'll change that.

There appears to be some boilerplate in here that could be avoided by using a benchmarking library such as benchmark_harness or benchmark. Any reason not to use one of those?

I'm always hesitant to add a dependency for something basic, but looking at benchmark_harness, that seems like a low risk/cost solution. I'll change that, too.

[greensopinion]

Looks great! A few comments inline.

[greensopinion]

is late needed?

[blaugold]

Yes, because we need to access this to initialize resolver. That means we cannot initialize before the constructor body.

[greensopinion]

Excellent work, thanks so much for the contribution.

[blaugold]

Glad I can contribute. Let me know if there is something I could help with.

[greensopinion]

Let me know if there is something I could help with.

you might want to take a look at this concurrency experiment

see the commit message - there's potentially more that could be done to improve the frame rate by offloading work to an isolate as you suggested previously

feel free to create issues to initiate a discussion or track any work that you take on.