Well, I tried it. No O(n), but the result is quite interesting.

For small dictionaries, it seems that there's almost no difference between imap and fdict. Indeed dict is optimized for size equal or smaller than 8. As expected the difference grows with the size of the dictionary.

About mutate(), in theory fdict could return simply a dict, and dict could have a freeze() method that returns a frozendict. Since dict is quite fast on writing, it's difficult to compare the performances.

This is the source code of the benchmark:

This is the diff:

Maybe immutables.Map can be further optimized. For example, "set()" could use METH_FASTCALL. The only problem is that METH_FASTCALL is not part of the limited API.

I think that a frozenmap is quite interesting, but a frozendict could have the advantage to be fast as dict on reading, and could also have not-so-slow methods to modify itself for common cases. Furthermore, since it has the same struct of dict, it can be accessed by the internal optimized functions.

I also remembered another possible use-case: kwargs in CPython. In C code, kwargs are PyDictObjects. I suppose they are usually not modified; if so, fdict could be used, since it seems to be faster at creation.