On Wed, Jul 22, 2020 at 9:25 PM Marco Sulla Marco.Sulla.Python@gmail.com wrote: <...>
On Wed, 22 Jul 2020 at 18:26, Guido van Rossum guido@python.org wrote:
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.
Because you didn't benchmark the case that matters for PEP 603: mutation. E.g. for a regular dict that would be "d1 = d.copy(); d1[key] = new_value", meaning "I need to mutate my dict keeping its old version intact".
Here's the benchmark results for this operation for PEP 603: https://github.com/MagicStack/immutables/blob/master/README.rst (note that "regular dict" means "d[key] = new_value", i.e. without copying).
Maybe this is because immutables.Map is a C extension and not a builtin type.
frozenmap implements a fundamentally different data structure, that's the reason. Its data structure has O(log N) mutations as opposed to O(n) for a naive frozen dict. All other operations (like lookups) while also O(1) are slightly slower than Python dict's equivalent operations.
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.
If you're fascinated by functional programming then your version of the frozen dict should support efficient (not "O(n)") mutations. That's the defining characteristic of hashmaps in languages like clojure. Otherwise it doesn't take too much to freeze a dict (prohibit mutations), but such dicts are only useful because they are hashable. That's the reason why popular libraries like https://immutable-js.github.io/immutable-js/ implement data structures similar to PEP 603.
Yury