Removed Priority-Medium label.
Added Priority-Unassigned label.

Set owner to @kodandersson.

Now that they are efficiently serialized, we can simply reuse the _LinkedHashMapMixin that we use for the default (mutable) maps, but redefining all mutating operations to throw the appropriate error.

A long time ago we changed immutable maps to keep the entries ordered in source order, so a binary search (as suggested in the TODO comment in the code) does not work. Let's not make this more complicated than necessary.

As far as I understand Daniel was suggesting the use of the efficient ordered maps as an implementation of ImmutableMap. How best to do this is not entirely clear to me yet.

Yeah, the bug was more about the fact that key lookup is O(N), not the particular approach described in the TODO. O(N) doesn't match expectations about how Map lookup should work. The workaround is to avoid const maps and/or keep them small.

Correct, that is not only a workaround but also good practice. Constant maps get evaluated at compile-time. If you have a large map, load times may suffer. (There is another open bug that complains that load time for a script with a > 2000 entry const map is too long.)