Repository: flutter
Issue: [google_maps_flutter_web] API performance bottleneck in custom tile overlays
Labels: c: new feature,c: performance,p: maps,platform-web,package,has reproducible steps,P3,found in release: 3.6,team-web,triaged-web

Custom tile overlays on web aren't supported yet, but there may be a significant performance bottleneck in the API where tile content is expected to be in encoded bytes ([`Tile.data`](https://pub.dev/documentation/google_maps_flutter_platform_interface/latest/google_maps_flutter_platform_interface/Tile-class.html)). If tile preprocessing is required on the Flutter app side, this incurs an expensive `Image.toByteData` call, which blocks the UI thread. On Android, we hit this bottleneck as well but it's less of an issue as it seems to happen off the UI thread, so the most that happens is tiles take longer to load than ideal.

To some degree, this can be mitigated by caching in the web tile overlay implementation, as my implementation does not cache on the web side yet. However, there would still be jank in the cache miss case, which would happen pretty often.

Ideally, I'd like it if the web implementation could insert flutter widgets as tiles so that we could avoid the extra encoding/decoding cycle. However, though I haven't looked too deeply into the Android/iOS APIs, I suspect that might be problematic there. Perhaps a middle ground could be to accept either raw bytes or `Image` objects and convert on the plugin side. I might try prototyping that on my fork. Please let me know whether such an API change is a direction you'd be open to. A related use case is placeholder images while tiles are loading from a network fetch, which is probably not possible with the current formulation (I'm using a styled base map for this purpose even though my previous [web implementation](http://34.83.198.158/trip_planner/) was compositing from available nearby mipmaps).

I might also look at ways to offload the tile processing to a web worker (e.g. [isolated_worker](https://pub.dev/packages/isolated_worker)?), though I do recall possibly seeing that canvas operations needed to happen on the UI thread (and as with the Android case, while that could remove the jank, tiles would still take longer to load than ideal).

Also in the meantime, using [image](https://pub.dev/packages/image) to encode as a bmp significantly improves performance over the stock png due to cheaper encoding, but it's still far from smooth. ([trip_planner_aquamarine/819e9c](https://github.com/AsturaPhoenix/trip_planner_aquamarine/commit/819e9c799ffcd868eccd3e030de0477547ad85e6))

Related: #98596

## Details

Live example:

1. http://34.83.198.158/trip_planner_aquamarine_slow
2. Zoom into/out of the map and scroll around
3. Observe frame drops during associated animations

<details>
<summary>Reduced example</summary>

```
chromedriver --port=4444 &
flutter drive -d chrome --driver test_driver/integration_test.dart --target integration_test/tile_overlay_performance_test.dart --profile
```

With the custom overlay commented out, observe a frame ratio of \~1 (no dropped frames). With the custom overlay, observe a significantly reduced frame ratio (\~.25 on my system, 75% dropped frames).

Dependencies:
```yaml
dependencies:
  ...
  equatable: ^2.0.5
  google_maps_flutter: ^2.2.1
  google_maps_flutter_web: ^0.4.0+3
  http: ^0.13.5
  image: ^3.2.2

dependency_overrides:
  google_maps_flutter_web:
    path: ../flutter/plugins/packages/google_maps_flutter/google_maps_flutter_web
```

Dependency overrides:
https://github.com/AsturaPhoenix/flutter-plugins/tree/dev (be sure to clone the `dev` branch)

`integration_test/tile_overlay_performance_test.dart`
```dart
import 'dart:async';
// ignore: avoid_web_libraries_in_flutter
import 'dart:html';
import 'dart:math';
import 'dart:typed_data';
import 'dart:ui' as ui;

import 'package:equatable/equatable.dart';
import 'package:flutter/material.dart';
import 'package:flutter_test/flutter_test.dart';
import 'package:google_maps_flutter/google_maps_flutter.dart';
import 'package:image/image.dart' as img;
import 'package:integration_test/integration_test.dart';
import 'package:http/http.dart' as http;

// import 'package:trip_planner_aquamarine/persistence/blob_cache.dart';
// import 'package:trip_planner_aquamarine/providers/wms_tile_provider.dart';

class FakeWmsClient extends Fake implements http.Client {
  final random = Random();

  int tilesGenerated = 0;

  Future<ui.Image> generateTile(Uri url) async {
    ++tilesGenerated;

    final width = int.parse(url.queryParameters['width']!);
    final height = int.parse(url.queryParameters['height']!);
    final buffer = await ui.ImmutableBuffer.fromUint8List(
      Uint8List.fromList([
        for (int y = 0; y < height; ++y)
          for (int x = 0; x < width; ++x) ...[
            random.nextInt(0x100),
            random.nextInt(0x100),
            random.nextInt(0x100),
            0xFF
          ]
      ]),
    );
    final imageDescriptor = ui.ImageDescriptor.raw(
      buffer,
      width: width,
      height: height,
      pixelFormat: ui.PixelFormat.rgba8888,
    );

    try {
      final codec = await imageDescriptor.instantiateCodec();
      try {
        return (await codec.getNextFrame()).image;
      } finally {
        codec.dispose();
      }
    } finally {
      imageDescriptor.dispose();
    }
  }

  @override
  Future<http.Response> get(Uri url, {Map<String, String>? headers}) =>
      generateTile(url)
          .then((image) => image.toByteData(format: ui.ImageByteFormat.png))
          .then(
            (data) =>
                http.Response.bytes(data!.buffer.asUint8List(), HttpStatus.ok),
          );

  @override
  void close() {}
}

class FakeBlobCache extends Fake implements BlobCache {
  final data = <String, Uint8List>{};

  @override
  Uint8List? operator [](String key) => data[key];
  @override
  void operator []=(String key, Uint8List value) => data[key] = value;
  @override
  void close() {}
}

Future<void> watchTiles(int minCount) {
  final completer = Completer<void>();
  final watched = <ImageElement>{}, loading = <ImageElement>{};

  void awaitLoad(ImageElement img) {
    loading.add(img);
    img.decode().whenComplete(() {
      loading.remove(img);

      if (watched.length >= minCount && loading.isEmpty) {
        completer.complete();
      }
    });
  }

  void scan() {
    watched.removeWhere((img) => !img.isConnected!);
    loading.removeWhere((img) => !img.isConnected!);

    for (final ImageElement img
        in document.querySelectorAll('img[src^="blob:"]')) {
      if (watched.add(img)) {
        awaitLoad(img);
      }
    }
  }

  final observer = MutationObserver((_, __) => scan())
    ..observe(
      document,
      childList: true,
      subtree: true,
      attributes: true,
      attributeFilter: const ['src'],
    );

  scan();

  return completer.future.whenComplete(() => observer.disconnect());
}

/// Uses timeouts to probe whether web animations are happening smoothly.
/// (Integration test timelines don't work on web because they need isolate
/// support.)
class WebPerformanceMonitor {
  WebPerformanceMonitor({required this.fps}) : t0 = DateTime.now() {
    timer = Timer.periodic(
      const Duration(seconds: 1) * (1 / fps),
      (_) => ++_frames,
    );
  }
  final DateTime t0;
  final num fps;
  late final Timer timer;
  int _frames = 0;
  // The ratio of frames recorded : frames expected.
  double get frameRatio =>
      _frames * 1000 / (fps * DateTime.now().difference(t0).inMilliseconds);

  void close() => timer.cancel();
}

///  ```
/// chromedriver --port=4444 &
/// flutter drive -d chrome --driver test_driver/integration_test.dart --target integration_test/tile_overlay_performance_test.dart --profile
/// ```
void main() {
  IntegrationTestWidgetsFlutterBinding.ensureInitialized();

  testWidgets('Tile overlay performance test', (tester) async {
    final mapControllerCompleter = Completer<GoogleMapController>();
    final onCameraIdleController = StreamController<void>.broadcast();

    final wmsClient = FakeWmsClient();

    await tester.pumpWidget(
      MaterialApp(
        home: Scaffold(
          body: Center(
            child: SizedBox.fromSize(
              size: const Size.square(0x300),
              child: GoogleMap(
                initialCameraPosition: const CameraPosition(
                  target: LatLng(37.8331, -122.4165),
                  zoom: 12,
                ),
                tileOverlays: {
                  TileOverlay(
                    tileOverlayId: const TileOverlayId('test'),
                    tileProvider: WmsTileProvider(
                      client: wmsClient,
                      cache: FakeBlobCache(),
                      tileType: 'test',
                      url: Uri(path: 'test'),
                      fetchLod: 2,
                      levelOfDetail: 14,
                      params: WmsParams(),
                    ),
                  )
                },
                onCameraIdle: () => onCameraIdleController.add(null),
                onMapCreated: mapControllerCompleter.complete,
              ),
            ),
          ),
        ),
      ),
    );

    // This is needed to kick-off the rendering of the JS Map flutter widget
    await tester.pump();
    final controller = await mapControllerCompleter.future;
    final onCameraIdle = onCameraIdleController.stream;

    await watchTiles(9);
    // Zoom in from 12 with target LOD 14 and max oversample 2 should not
    // require new tiles
    final tilesGenerated = wmsClient.tilesGenerated;

    final perf = WebPerformanceMonitor(fps: 60);
    const iterations = 16;
    for (int i = 0; i < iterations; ++i) {
      controller.animateCamera(CameraUpdate.zoomIn());
      await onCameraIdle.first;
      await watchTiles(9);

      controller.animateCamera(CameraUpdate.zoomOut());
      await onCameraIdle.first;
      await watchTiles(9);
    }

    tester.printToConsole('Frame ratio: ${perf.frameRatio}');
    expect(perf.frameRatio, greaterThan(.24));
    assert(wmsClient.tilesGenerated == tilesGenerated);
  });
}

// blob_cache.dart

abstract class BlobCache {
  void close();
  Uint8List? operator [](String key);
  void operator []=(String key, Uint8List value);
}

// wms_tile_provider.dart

class WmsParams {
  // unused
}

extension on Point<int> {
  ui.Offset toOffset() => ui.Offset(x.toDouble(), y.toDouble());
  Point<int> operator <<(int z) => Point(x << z, y << z);
  // On web, >> is limited to int32.
  // https://github.com/dart-lang/sdk/issues/15361
  // This is fine since the max zoom level for maps is 22.
  Point<int> operator >>(int z) =>
      Point((x >> z).toSigned(32), (y >> z).toSigned(32));
}

extension on ui.Image {
  ui.Size get size => ui.Size(width.toDouble(), height.toDouble());
}

class AreaLocator extends Equatable {
  const AreaLocator(this.zoom, this.coordinate);

  final int zoom;
  final Point<int> coordinate;

  @override
  get props => [zoom, coordinate];

  /// Derives a descendant [AreaLocator] in the quadtree. Descendants have
  /// coordinates in the top left.
  ///
  /// The `>>` symbol is chosen to represent shifting rightwards towards
  /// children in a left-to-right hierarchy representation.
  AreaLocator operator >>(int z) => AreaLocator(zoom + z, coordinate << z);

  /// Derives an ancestor of [AreaLocator] in the quadtree.
  ///
  /// The `<<` symbol is chosen to represent shifting leftwards towards
  /// ancestors in a left-to-right hierarchy representation.
  AreaLocator operator <<(int z) => AreaLocator(zoom - z, coordinate >> z);

  AreaLocator operator +(Point<int> offset) =>
      AreaLocator(zoom, coordinate + offset);

  TileLocator withLod(int lod) => TileLocator(zoom, coordinate, lod);
}

class TileLocator extends AreaLocator {
  /// The LOD delta from [zoom]. The effective zoom level of the referenced
  /// tiles is `zoom + lod`.
  final int lod;

  @override
  get props => [...super.props, lod];

  const TileLocator(super.zoom, super.coordinate, this.lod);
  @override
  String toString() => 'zoom: $zoom / coordinate: $coordinate / lod: $lod';

  @override
  TileLocator operator >>(int z) => (super >> z).withLod(lod - z);

  @override
  TileLocator operator <<(int z) => (super << z).withLod(lod + z);

  @override
  TileLocator operator +(Point<int> offset) => (super + offset).withLod(lod);
}

class TileKey extends TileLocator {
  const TileKey(this.type, super.zoom, super.coordinate, super.lod);
  TileKey.forLocator(TileLocator locator, String type)
      : this(type, locator.zoom, locator.coordinate, locator.lod);
  final String type;

  @override
  get props => [type, ...super.props];

  @override
  String toString() => '$type@$zoom:(${coordinate.x},${coordinate.y})+$lod';
}

// Derived from js-ogc
class WmsTileProvider implements TileProvider {
  /// This is determined by the Maps API, but doesn't seem to be a constant
  /// provided there.
  static const logicalTileSize = 256;

  static const _defaultWmsParams = {
    'request': 'GetMap',
    'service': 'WMS',
    'srs': 'EPSG:3857',
  };

  static const _epsg3857Extent = 20037508.34789244;
  static const _origin = ui.Offset(
    -_epsg3857Extent, // x starts from left
    _epsg3857Extent,
  ); // y starts from top

  static final _imagePaint = ui.Paint();

  static Future<ui.Image> decodeImage(Uint8List data) async {
    final buffer = await ui.ImmutableBuffer.fromUint8List(data);
    final ui.ImageDescriptor imageDescriptor;
    try {
      imageDescriptor = await ui.ImageDescriptor.encoded(buffer);
    } finally {
      buffer.dispose();
    }

    try {
      final codec = await imageDescriptor.instantiateCodec();
      try {
        return (await codec.getNextFrame()).image;
      } finally {
        codec.dispose();
      }
    } finally {
      imageDescriptor.dispose();
    }
  }

  /// Convert xyz tile coordinates to mercator bounds.
  static ui.Rect _xyzToBounds(AreaLocator xyz) {
    final wmsTileSize = _epsg3857Extent * 2 / (1 << xyz.zoom);
    return _origin + xyz.coordinate.toOffset().scale(1, -1) * wmsTileSize &
        ui.Size(wmsTileSize, -wmsTileSize);
  }

  WmsTileProvider({
    required this.client,
    required this.cache,
    required this.tileType,
    required this.url,
    this.levelOfDetail = 0,
    this.maxOversample = 2,
    this.fetchLod = 0,
    this.preferredTileSize = 256,
    required this.params,
  });

  http.Client client;
  BlobCache cache;
  String tileType;

  /// The base URL supplying tile data. For simplicity, any query paremeters
  /// also specified in [WmsParams] or [DEFAULT_WMS_PARAMS] are overwritten.
  Uri url;

  int levelOfDetail;
  int maxOversample;

  /// The level of detail above natural at which to fetch and cache. Higher
  /// values will fetch larger tiles from the server, by powers of 2, and window
  /// them into the expected logical tile size of 256 x 256. The web API allows
  /// for custom logical tile sizes, but mobile does not.
  final int fetchLod;

  /// The tile standard tile size multiplied by the device pixel ratio.
  int preferredTileSize;
  WmsParams params;

  void dispose() {
    cache.close();
    client.close();
  }

  Uri _getTileUrl(TileLocator locator) {
    final bbox = _xyzToBounds(locator);
    final tileSizeParam = (logicalTileSize << locator.lod).toString();

    return url.replace(
      queryParameters: {
        ..._defaultWmsParams,
        ...url.queryParametersAll,
        // ...params.toJson().map((key, value) => MapEntry(key, value.toString())),
        'bbox': '${bbox.left},${bbox.bottom},${bbox.right},${bbox.top}',
        'width': tileSizeParam,
        'height': tileSizeParam,
      },
    );
  }

  Future<Uint8List> fetchImageData(TileLocator locator) async {
    final url = _getTileUrl(locator);

    final response = await client.get(url);
    if (response.statusCode == HttpStatus.ok) {
      return response.bodyBytes;
    } else {
      throw response;
    }
  }

  final _activeDecodes = <TileLocator, Future<ui.Image>>{};

  Future<Uint8List> getImageData(TileLocator locator) async =>
      cache[TileKey.forLocator(locator, tileType).toString()] ??=
          await fetchImageData(locator);

  Future<ui.Image> getImage(TileLocator locator) => _activeDecodes[locator] ??=
          getImageData(locator).then(decodeImage).whenComplete(() {
        // Caution: This can't be a => because we must discard the return value
        // or else the async becomes circular and never completes.
        _activeDecodes.remove(locator);
      });

  /// Windows a tile from a larger tile at a higher LOD.
  Future<void> _tileFromLarger(ui.Canvas canvas, TileLocator locator) async {
    final levelsAbove = min(fetchLod - locator.lod, locator.zoom);
    final ancestor = locator << levelsAbove;
    final image = await getImage(ancestor);

    final size = image.size / (1 << levelsAbove).toDouble();
    final offset = (locator.coordinate - (ancestor.coordinate << levelsAbove))
        .toOffset()
        .scale(size.width, size.height);

    canvas.drawImageRect(
      image,
      offset & size,
      ui.Offset.zero & const ui.Size.square(1),
      _imagePaint,
    );
  }

  /// Assembles a tile from smaller tiles at a lower LOD.
  Future<void> _tileFromSmaller(ui.Canvas canvas, TileLocator locator) async {
    final levelsBelow = locator.lod - fetchLod;
    final descendantBasis = locator >> levelsBelow;
    final sideLength = 1 << levelsBelow;

    canvas
      ..save()
      ..scale(1 / sideLength);

    for (int j = 0; j < sideLength; ++j) {
      for (int i = 0; i < sideLength; ++i) {
        final offset = Point(i, j);
        final descendantLocator = descendantBasis + offset;

        final image = await getImage(descendantLocator);
        canvas.drawImageRect(
          image,
          ui.Offset.zero & image.size,
          offset.toOffset() & const ui.Size.square(1),
          _imagePaint,
        );
      }
    }

    canvas.restore();
  }

  /// Gets a tile image, composited from cached or fetched resources.
  ///
  /// The caller is responsible for calling `dispose` on the image.
  Future<ui.Image> getTileContent(TileLocator locator) async {
    final pictureRecorder = ui.PictureRecorder();
    final canvas = ui.Canvas(pictureRecorder);

    // Keep the natural resolution afforded by the LOD if we want to display at
    // a higher resolution, but don't waste bytes beyond the preferred size to
    // minimize encoding time.
    //
    // Also go ahead and normalize the tile size to 1.
    final tileSize = min(logicalTileSize << locator.lod, preferredTileSize);
    canvas.scale(tileSize.toDouble());

    if (locator.lod <= fetchLod) {
      await _tileFromLarger(canvas, locator);
    } else {
      await _tileFromSmaller(canvas, locator);
    }

    final picture = pictureRecorder.endRecording();
    try {
      return picture.toImage(tileSize, tileSize);
    } finally {
      picture.dispose();
    }
  }

  final _encoder = img.BmpEncoder();

  @override
  Future<Tile> getTile(int x, int y, int? zoom) async {
    final locator = TileLocator(
      zoom!,
      Point(x, y),
      max(min(levelOfDetail - zoom, maxOversample), 0),
    );
    final content = await getTileContent(locator);
    try {
      final data = await content.toByteData(
        format: ui.ImageByteFormat.rawStraightRgba,
      );
      final image = img.Image.fromBytes(
        content.width,
        content.height,
        data!.buffer.asUint8List(),
      );
      return Tile(
        image.width,
        image.height,
        Uint8List.fromList(_encoder.encodeImage(image)),
      );
    } finally {
      content.dispose();
    }
  }
}
```

`test_driver/integration_test.dart`
```dart
// https://docs.flutter.dev/testing/integration-tests#running-in-a-browser

import 'package:integration_test/integration_test_driver.dart';

Future<void> main() => integrationDriver();
```

`web/index.html'
```html
<!DOCTYPE html>
<html>
<head>
  <base href="$FLUTTER_BASE_HREF">

  <meta charset="UTF-8">
  <meta content="IE=Edge" http-equiv="X-UA-Compatible">
  <meta name="description" content="Repro">

  <!-- iOS meta tags & icons -->
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="apple-mobile-web-app-title" content="repro">
  <link rel="apple-touch-icon" href="icons/Icon-192.png">

  <!-- Favicon -->
  <link rel="icon" type="image/png" href="favicon.png"/>

  <title>Repro</title>
  <link rel="manifest" href="manifest.json">

  <script>
    // The value below is injected by flutter build, do not touch.
    var serviceWorkerVersion = null;
  </script>
  <!-- This script adds the flutter initialization JS code -->
  <script src="flutter.js" defer></script>
  <script src="https://maps.googleapis.com/maps/api/js?key="></script>
</head>
<body>
  <script>
    window.addEventListener('load', function(ev) {
      // Download main.dart.js
      _flutter.loader.loadEntrypoint({
        serviceWorker: {
          serviceWorkerVersion: serviceWorkerVersion,
        }
      }).then(function(engineInitializer) {
        return engineInitializer.initializeEngine();
      }).then(function(appRunner) {
        return appRunner.runApp();
      });
    });
  </script>
</body>
</html>
```
</details>

<img width="865" alt="image" src="https://user-images.githubusercontent.com/13222934/204358946-c2c89da4-8eff-41a6-9866-bb2f9d71ad58.png">

[Profile-20221128T110059.json.txt](https://github.com/flutter/flutter/files/10106663/Profile-20221128T110059.json.txt)

**Target Platform:** Web
**Target OS version/browser:** Chrome
**Devices:** LG gram / x64 / Windows 11 Home

## Logs

<details>
<summary>Logs</summary>

```
Analyzing trip_planner_aquamarine...                                    
No issues found! (ran in 42.0s)
```

```
[√] Flutter (Channel master, 3.6.0-1.0.pre.3, on Microsoft Windows [Version 10.0.22621.674], locale en-US)
    • Flutter version 3.6.0-1.0.pre.3 on channel master at C:\Users\imagi\flutter
    • Upstream repository https://github.com/flutter/flutter.git
    • Framework revision 8e5439c89e (3 weeks ago), 2022-11-09 14:33:45 -0500
    • Engine revision c76035429c
    • Dart version 2.19.0 (build 2.19.0-377.0.dev)
    • DevTools version 2.19.0

[√] Windows Version (Installed version of Windows is version 10 or higher)

[√] Android toolchain - develop for Android devices (Android SDK version 33.0.0)
    • Android SDK at C:\Users\imagi\AppData\Local\Android\sdk
    • Platform android-33, build-tools 33.0.0
    • Java binary at: C:\Program Files\Android\Android Studio\jre\bin\java
    • Java version OpenJDK Runtime Environment (build 11.0.13+0-b1751.21-8125866)
    • All Android licenses accepted.

[√] Chrome - develop for the web
    • Chrome at C:\Program Files\Google\Chrome\Application\chrome.exe

[!] Visual Studio - develop for Windows (Visual Studio Community 2019 16.11.16)
    • Visual Studio at C:\Program Files (x86)\Microsoft Visual Studio\2019\Community
    • Visual Studio Community 2019 version 16.11.32602.291
    • Windows 10 SDK version 10.0.16299.0
    X Visual Studio is missing necessary components. Please re-run the Visual Studio installer for the "Desktop development with C++" workload, and include these components:
        MSVC v142 - VS 2019 C++ x64/x86 build tools
         - If there are multiple build tool versions available, install the latest
        C++ CMake tools for Windows
        Windows 10 SDK

[√] Android Studio (version 2021.3)
    • Android Studio at C:\Program Files\Android\Android Studio
    • Flutter plugin can be installed from:
       https://plugins.jetbrains.com/plugin/9212-flutter
    • Dart plugin can be installed from:
       https://plugins.jetbrains.com/plugin/6351-dart
    • Java version OpenJDK Runtime Environment (build 11.0.13+0-b1751.21-8125866)

[√] VS Code (version 1.73.1)
    • VS Code at C:\Users\imagi\AppData\Local\Programs\Microsoft VS Code
    • Flutter extension version 3.52.0

[√] Connected device (3 available)
    • Windows (desktop) • windows • windows-x64    • Microsoft Windows [Version 10.0.22621.674]
    • Chrome (web)      • chrome  • web-javascript • Google Chrome 107.0.5304.107
    • Edge (web)        • edge    • web-javascript • Microsoft Edge 107.0.1418.56

[√] HTTP Host Availability
    • All required HTTP hosts are available

! Doctor found issues in 1 category.
```

</details>