frozendict: an experiment

[Inada Naoki]

On Fri, Jul 17, 2020 at 2:16 AM Marco Sulla
<Marco.Sulla.Python at gmail.com> wrote:
>
> On Thu, 16 Jul 2020 at 06:11, Inada Naoki <songofacandy at gmail.com> wrote:
> > On Thu, Jul 16, 2020 at 2:32 AM Marco Sulla
> > <Marco.Sulla.Python at gmail.com> wrote:
> > > Yes, but, instead of creating a view, you can create and cache the
> > > pointer of a "real" object, that implements the dict view API.
> > > For example, keys for a frozendict could be an "ordered" frozenset.
> > > This "oset" could be a frozendict
> > I am not sure about what are you saying.
> > Does it really solve the usage of dict views?
> > How about my example? (`assert d.keys() == {"spam", "egg"}`)
>
> Well, if the frozendict "views" will implement the full API of the
> dict views, your assert and all the existing code will continue to
> work.
> The difference will be that views *could* be faster.
>

Then, there is no reason to not support the view for frozendict?


> > > On Wed, 15 Jul 2020 at 08:07, Inada Naoki <songofacandy at gmail.com> wrote:
> About frozendict optimization
>
> an immutable dict could be optimized in different ways in Python:
> 1. as I said, views can be replaced with "real", cached objects. This
> will speed up subsequent calls to keys() etc.

I don't think it is an interesting optimization.

> 2. as tuples and strings, small frozendicts can be interned in a
> cache. The same cache can be used to return a cached frozendict
> instead of recreate it, as tuples.

I am not sure tuple is "internined" or just "merged". (I don't know precise
definition of the "interning").

Tuples are merged while compiling.

```
    for a in ["foo", "bar"]:  # compiler convert this list to tuple
        ...
    for b in ("foo", "bar"):  # and compiler merge same tuple
        ...
```

But when frozendicts are merged?
I think there is a very little chance.


> 3. many python internals uses a mapping proxy to a dict, to avoid its
> modification. A frozendict can be used instead.

Are they used frequently in performance critical path?
Could you point some concrete examples?

> 4. dicts can use a split table or a combined table. This is useful for
> maintaining insertion order upon deletion and insertion.
>    This is not required for frozendicts, since once created they can't
> be modified. frozendicts can be all split or all combined dicts

Key-sharing dict vs regular dict are not relating to insertion order.
Key-sharing dict is implemented before insertion order keeping dict.

And when I implemented order preserving dict, key-sharing dict is very
difficult to maintain.
I even wanted to drop key-sharing dict support.

I'm OK to all combined dict for frozen dict.  But I think key-sharing is still
interesting optimization for frozen dict. And supporting key-sharing dict
is much easier for frozendict than for mutable dict.


>
> About functional programming
>
> Well, pure functional programming requires no side effects:
> https://en.wikipedia.org/wiki/Functional_programming
> Object mutability is a side effect. Pure functional programming uses
> only immutable objects.
> In Python, pure functional programming is impossible, since even
> functions are (partially) mutable objects. But Python has a lot of
> functional programming features:
> https://docs.python.org/3/howto/functional.html
> Every builtin mutable data type has its immutable counterpart now,
> dict apart. And types.MappingProxyType is not usable in real world,
> since it's really slow.

I feel this motivation is too theorical.  And theorically, I don't think Python
should add bultin type for pure functional programming.  Python should
focus only Pytohnic programming.

Would you provide some concrete examples how frozendict can improve
Python code significantly?

-- 
Inada Naoki  <songofacandy at gmail.com>