Very poor JIT performance with const Map<Type, ..>

[dnys1]

Consider the following program:

const typeMap = <Type, ...>{
  String: ...,
  bool: ...,
  // ...a lot of types
};

void main() => print(typeMap[String]);

My expectation would be for this to run very quickly. And with a small number of types it does. But this balloons in runtime as the number of types increases.

However, this only appears to happen in JIT mode (using 100,000 types).

$ time dart type_map.dart
dart type_map.dart  4.79s user 0.39s system 149% cpu 3.455 total
$ dart compile exe type_map.dart
$ time ./type_map.exe
./type_map.exe  0.01s user 0.01s system 50% cpu 0.041 total

It gets worse, though. If we introduce a wrapper class, like https://pub.dev/packages/typer for example, it is close to impossible to run with any meaningful size of the map.

class Typer<T> { const Typer(); }

const typeMap = <Typer, ...>{
  Typer<String>(): ...,
  Typer<bool>(): ...,
  ...
};

void main() => print(typeMap[const Typer<String>()]);

Calling dart run with this program results in 😱

$ dart type_map.dart
dart type_map.dart  176.61s user 0.51s system 99% cpu 2:57.64 total

And having this map in a project also completely stalls the analyzer.

Again, though, only for JIT it seems.

$ dart compile exe type_map.dart # This takes forever, too
$ time ./type_map.exe
./type_map.exe  0.04s user 0.01s system 71% cpu 0.069 total

Here's a small script to reproduce the problem:

import 'dart:io';

void main() {
  final buf = StringBuffer()..writeln('const typeMap = {');
  final types = <String>[];
  for (var i = 0; i < 100000; i++) {
    final type = 'Type$i';
    types.add(type);
    buf.writeln('  Typer<$type>(): $i,');
  }
  buf.writeln('};');

  buf.writeln('class Typer<T> { const Typer(); }');

  for (final type in types) {
    buf.writeln('class $type {}');
  }

  buf.writeln('void main() => print(typeMap[const Typer<Type42>()]);');
  File('type_map.dart').writeAsStringSync(buf.toString());
}

dart info

#### General info

- Dart 3.3.4 (stable) (Tue Apr 16 19:56:12 2024 +0000) on "macos_arm64"
- on macos / Version 14.4.1 (Build 23E224)
- locale is en-US

#### Process info

|  Memory |   CPU | Elapsed time | Command line                                                                           |
| ------: | ----: | -----------: | -------------------------------------------------------------------------------------- |
|   74 MB |  0.0% |        01:01 | dart compile exe type_map.dart                                                         |
|   29 MB |  0.0% |  01-19:50:43 | dart devtools --machine --allow-embedding --port 9102                                  |
| 1838 MB |  0.0% |  01-01:21:48 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
| 1578 MB | 98.4% |        26:08 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
|   60 MB |  0.0% |  01-17:48:06 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
|  352 MB |  0.0% |        13:09 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
|   64 MB |  0.0% |  02-00:15:56 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
|   67 MB |  0.0% |  01-19:50:43 | dart language-server --protocol=lsp --client-id=VS-Code --client-version=3.89.20240501 |
|   60 MB |  0.0% |  01-19:50:43 | flutter_tools.snapshot daemon                                                          |

[dnys1]

A few more observations:

• Adding a simple bound seems to make the problem worse, e.g. class Typer<T extends Object>

# JIT
dart type_map.dart  247.04s user 0.58s system 99% cpu 4:09.16 total

# AOT
./type_map.exe  0.05s user 0.01s system 23% cpu 0.244 total

• A final map with const Typer keys has the same performance characteristics

• A final map and non-const Typer's (e.g. with overridden == and hashCode) performs much better:

dart type_map.dart  5.70s user 0.48s system 135% cpu 4.561 total

[lrhn]

IIRC, the VM's constant maps are no longer linear lookup (yep, found it).
Any chance that only affected AoT?

Probably not the issue, but could be the cause.
I think it's the compilation that's atrociously slow, and for the JIT, that makes it look slow to run, when it's actually slow to start.

If I generate the type_map.dart file above, and try to compile it with dart compile exe, it, well, is still running in the time I took to copy the file, change all the Typer<Type\d+> to be strings instead, run that as JIT, compile it as exe and run it. And then some.
And now it completed, and running is quick.

If I take the same file and reduce the number of map entries (by commenting out all but the first ten entries, classes are kept in), then the compile time drops.

Elements	Compile-time
10	4.5 s
100	4.7 s
1000	4.8 s
10000	7.3 s
25000	24.5 s
35000	38.3 s
42000	53.1 s
50000	135.8 s
55000	157.6 s
60000	191.0 s

Does seem to grow very non-linearly.

[mraleph]

The issue with const Typer<X>() constants is the following: they all seems to get the same canonicalization hash which causes bad performance when reading them from the Kernel file. The reason this happens is because they have no fields of their own and differ only in type arguments, but we seem to define TypeArguments::CanonicalizationHash to be 0 - so all const Typer<X>() hash to the same value.

Using appropriate hash to type arguments fixes this - but it is not entirely clear to me why TypeArguments::CanonicalizationHash was defined to be 0. Maybe @rmacnak-google who added that code remembers.

[mraleph]

FWIW, I am unable to reproduce the problem by using just Map<Type, ...> only with Map<Typer, ...> @dnys1 are you sure you saw any nonlinear behavior with Map<Type, ...>?

[dnys1]

@mraleph, you're correct. The non-linear behavior was only seen with Typer.

I should've been more clear. With Type keys, I saw degraded performance compared to, for example, ints.

Map<int, int>

dart type_map.dart  0.83s user 0.12s system 122% cpu 0.780 total

Map<Type, int>

dart type_map.dart  4.84s user 0.58s system 152% cpu 3.543 total

Thanks for looking into it!

[mraleph]

The Typer<T> issues is now fixed, i will take a look at Map<Type, int> now.

[mraleph]

@dnys1 I don't really see drastic performance difference between Map<int, ...> and Map<Type, ...>: what I see is that it takes 15% more time to compile and there is around 1.7x slow down when running that Kernel. Which is not that surprising given that type objects are more complex then integers - so there is naturally more work to be done.

In your experiment did you actually emit any Type$i classes into the file with Map<int, ...>? Because if you omit class declarations then naturally parsing such file becomes much faster (and loading resulting Kernel would also be much faster).