Did you study PEP 416 (frozendict) and PEP 603 (frozenmap)?
Yes. About frozenmap, at the very start I added to the benchmarks also immutables.Map, but I removed it when I realized that it was slower than frozendict in every bench. Maybe this is because immutables.Map is a C extension and not a builtin type.
About PEP 416, yes, I tried to follow it. Indeed hash is calculated using the strategy described in the PEP. I also take a look to frozenset and tuple code.
Frankly I must admit that the rejection of PEP 416 was a good idea. Indeed I started to implement an immutable dict only for a symmetry reason, and because I am somewhat fascinated by functional programming and immutables, without a rational reason.
I suppose I would have given up and admitted that a frozendict is quite useless in Python, if I did not see that the constructor speed can be faster.
I'm not sure 100% of the result. This is why I'm suggesting to try to implement the speed optimizations to the constructor of dict first:
1. the optimizations could be not safe. Indeed recently I got a segfault that I have to investigate
2. maybe dict can be really optimized further. After that, the difference between dict and frozendict performance could be minimal
That said, maybe there are four good use cases for a frozendict:
1. they could be used for __annotations__ of function objects, and similar cases
2. they could be used to implement "immutable" modules or classes
3. frozendict can be easily cached, like tuples.
4. as I said, as an alternative to MappingProxyType, since it's very slow and it's used also in the C code of CPython and in the Python stdlib. This maybe is not useful because:
a. the speed of MappingProxyType can be improved
b. MappingProxyType can't be replaced because you *really* want and need a proxy