frozendict: an experiment

[Marco Sulla]

TL;DR: I tried to implement in CPython a frozendict here:
https://github.com/Marco-Sulla/cpython

Long explaining:

What is a frozendict? It's an immutable dict. The type was proposed in
the past but rejected: https://www.python.org/dev/peps/pep-0416/

So why did I try to implement it? IMO, apart the considerations in PEP
416, a frozendict can be useful:

- as a faster base for types.MutableMappingProxy
- as a substitute of namedtuple
- as set values
- as a faster dict. Indeed a frozendict does not need views. Keys,
values and items can be cached and could be a subclass of frozendict
that implements also the set API (values apart).

A possible problem is that frozendict requires more memory, since the
hash is cached.

My implementation is very naif. I tried to do the simplest thing,
without any speed improvement. I haven't added frozendict in marshal,
and the pickle implementation is very raw... Furthermore, I didn't
touch the AST parser at all, and I did not add any test for Python or
the C API in the battery, but I've done my tests apart, in pytest.

PS: I used for tests and benchmarks a little modified version of the
tests for my Python implementation of frozendict:
https://github.com/Marco-Sulla/python-frozendict/tree/master/test .
The results are interesting. A CPython builtin frozendict is faster in
every bench that immutables.Map, that uses the HAMT algorithm. and was
proposed as alternative in PEP 603:
https://www.python.org/dev/peps/pep-0603/ . Maybe because I
implemented it in CPython and immutables.Map is a C extension.