Compile const Map<String, T> as jump tables for performance

[gaaclarke]

This tracker is for issues related to:

• Dart VM

For Flutter I just switched some const Map<String, String>s to jump tables and they performed 2x faster than Map<String, String> at lookup (flutter/engine#33123). This seems like an optimization we could do under the hood and it should always be faster and smaller code. Using const Map<String, T> seems a very common pattern inside of Google.

[mraleph]

switch is not implemented as a jump table in VM. It's just a linear search. In general it's also unclear how a jump table with string keys would look like. The most obvious implementations for switch would need either some form of hashing or a trie under the hood.

Map has predictable lookup performance for all keys.

switch currently would get slower the further into the switch you need to look.

You can check this benchmark, which on our favourite low power Android device yields:

I/flutter (10060): switch[a0]: 41.79 ps
I/flutter (10060): switch[a4]: 232.32 ps
I/flutter (10060): switch[a7]: 349.20 ps
I/flutter (10060): map[a0]: 233.70 ps
I/flutter (10060): map[a4]: 283.41 ps
I/flutter (10060): map[a7]: 233.82 ps

In general it is impossible for the compiler to know the distribution of the input data. So this seems like an optimisation that user could make. e.g. if you know that you are 10x more likely to lookup a specific key then you could use a combination of switch and Map to achieve good performance.

(That being said we could probably find ways to make Map lookup a bit faster).

[gaaclarke]

Thanks @mraleph. That means for my case I'd probably better off making a jump table like lex makes where it's a finite state machine in an array. I may have been running my benchmarks just looking at the first items.