Add a dict method to convert to a frozendict?

[vstinner (Victor Stinner)]

Python 3.15 adds bytearray.take_bytes(n=None) method to convert a bytearray to bytes and clear the bytearray. It has a complexity of O(1). See the related discussion.

Would it make sense to add a similar function to convert a dict to a frozendict and clear the dict? For example, add dict.as_frozendict_and_clear() method. In CPython, it should be possible to implement this method with O(1) complexity which makes it interesting for performance.

For example, there is a function with complex code filling a mutable dict, and then use return frozendict(dict) to return a frozendict. The dict is only used to build the frozendict, then it’s discarded anyway. frozendict(dict) conversion is inefficient since it has to copy all items. The idea would be to replace it with dict.as_frozendict_and_clear() to make it efficient.

If we add such method, it would also be interesting to add a similar list.as_tuple_and_clear() and set.as_frozendset_and_clear() methods. In the internal C API, there is already a _PyList_AsTupleAndClear() function. For example, this code:

def tuple_from_iterable(iterable):
    return tuple(list(iterable))

would become:

def tuple_from_iterable(iterable):
    return list(iterable).as_tuple_and_clear()

Note: internally, tuple(iterable) is already implemented as list(iterable).as_tuple_and_clear()

See also the related discussion in the C API: Provide a C-API to efficently convert dict into frozendict.

---

I implemented these method to run two benchmarks.

Benchmark 1 on dict to frozendict conversion:

Code

import pyperf

LARGE = 10 ** 5

def func1():
    large_dict = {str(key): key for key in range(LARGE)}
    return frozendict(large_dict)
    # discard large_dict

def func2():
    large_dict = {str(key): key for key in range(LARGE)}
    return large_dict.as_frozendict_and_clear()
    # large_dict is empty

runner = pyperf.Runner()
runner.bench_func('frozendict(dict)', func1)
runner.bench_func('as_frozendict_and_clear()', func2)

Result:

• frozendict(dict): Mean ± std dev: 27.6 ms ± 2.1 ms
• as_frozendict_and_clear(): Mean ± std dev: 21.5 ms ± 1.6 ms

dict.as_frozendict_and_clear() is 1.28x faster than frozendict(dict).

Benchmark 2 on list to tuple conversion:

Code

import pyperf

def func1():
    large_list = list(range(10 ** 6))
    return tuple(large_list)
    # discard large_list

def func2():
    large_list = list(range(10 ** 6))
    return large_list.as_tuple_and_clear()
    # large_list is empty

runner = pyperf.Runner()
runner.bench_func('tuple(list)', func1)
runner.bench_func('as_tuple_and_clear()', func2)

Result:

• tuple(list): Mean ± std dev: 41.0 ms ± 1.9 ms
• as_tuple_and_clear(): Mean ± std dev: 32.1 ms ± 0.3 ms

list.as_tuple_and_clear() is 1.28x faster than tuple(list).

Well, the exact speedup depends on the dict/list size.

[MRAB (Matthew Barnett)]

The name as_frozendict_and_clear is rather long, much longer than take_bytes, and is named very differently. How about something like take_as_frozen or take_and_freeze?

[sobolevn (Nikita Sobolev)]

Or take_frozen

[encukou (Petr Viktorin)]

Or take_frozendict :‍)

[encukou (Petr Viktorin)]

I like the “take”/As*AndClear semantics, but we should be mindful the concept is rather new in Python – precedented by the rather fresh bytearray.take_bytes.

In C, this is IMO much better API than _Steal functions (where the user hopes that the object is uniquely referenced so that CPython can optimize by mutating the type instead of deallocating the old object and creating a new one). I’m +1 on the C API side.

But if we go down this path, it won’t be just bytearrays and now dicts, and it won’t be just C code. The pattern of consuming mutable input will start being used more, and perhaps preferred (for efficiency), in Python code as well.
This is a “function colouring” problem: if there’s a “take” function at the end of the call chain, any non-“take” caller need to copy the input. And crucially, in most existing Python code, functions tend to preserve their input.

This worries me. Adding take_frozendict would encourage new code to bake destroying their input into their API. We might get a better Python ecosystem if we instead encourage users to build a frozendict once, at a boundary of a system, and then passing that around.
Copying – frozendict(d) – is usually fast enough for this case, and IMO should remain the idiom to reach for if you need a frozendict and you don’t have special needs. Of course, json or other deserializers have the special needs; perhaps they should be taught to hand out frozendicts.

So, I’m currently strong -1 to making it a dict method.

And -0 for making this a function in some stdlib module – I think that’s ultimately the way to go, but adding it right now feels premature.

[ferdnyc (FeRD (Frank Dana))]

@encukou

This is a “function colouring” problem: if there’s a “take” function at the end of the call chain, any non-“take” caller need to copy the input. And crucially, in most existing Python code, functions tend to preserve their input.

This worries me. Adding take_frozendict would encourage new code to bake destroying their input into their API. We might get a better Python ecosystem if we instead encourage users to build a frozendict once, at a boundary of a system, and then passing that around.
Copying – frozendict(d) – is usually fast enough for this case – and IMO should remain the idiom to reach for if you need a frozendict and you don’t have special needs. Of course, json or other deserializers have the special needs; perhaps they should be taught to hand out frozendicts.

Hm! That’s an interesting point.

We have a (janky, not-very-robust) FrozenDict implementation in pydot (we needed it to use those objects as graph endpoints, meaning they had to be dict keys), and we create them by instantiating it with a dict argument to freeze… but that’s done in our parser, and the original dict it’s built from is discarded. (I had to check that was true, first. For a second I was worried we might’ve also kept the unfrozen dict around which would’ve been BAAAAD.)

Maybe what we need is another type, not a dict (it can be a subclass of dict, and of course it should have dict semantics) that’s explicitly a “MutableMapping for the express purpose of populating a future frozendict” type… which could serve as a signal to anyone handling those that they should not keep a copy of it, but instead copy.deepcopy() its contents if they want to hang on to them.

[encukou (Petr Viktorin)]

@ferdnyc

We have a (janky, not-very-robust) FrozenDict implementation in pydot (we needed it to use those objects as graph endpoints, meaning they had to be dict keys), and we create them by instantiating it with a dict argument to freeze… but that’s done in our parser, and the original dict it’s built from is discarded.

That is the way. (Well, until you can switch to frozendict, to join the rest of the ecosystem.)

According to Victor’s benchmarks, the proposed method would give you a 1.28× speedup – a few milliseconds – on that one call. And if you have less than 100_000 or 1_000_000 elements, the speedup is likely smaller.
If your library is written in Python, that’s seems very unlikely to be a bottleneck. Adding a special type smells like premature optimization.

[jacopoabramo]

Not sure if it applies, but I think I read in another thread that dict.freeze() was also suggested (or maybe I’m even misremembering what the thread was about anyway). Is the intention to maintain consistency with bytearray.take_bytes() that this option is not being considered? Or is it because freeze() might be misinterpreted somehow?

[hprodh]

The numpy, pandas, jax frameworks and co. generally use the methods prefixes with the conveyed meanings :
“to_type” for conversion, “as_type” for casting, “take_part” for extraction/subsetting…
I guess to_frozendict would thus be more coherent here.

[steve.dower]

I’m also -1 on making it a Python function, for the same reasons that Petr set out, but also because it sends a message that we expect and want Python developers to make premature micro-optimizations in their code. And I think we don’t.

[dpdani (Daniele Parmeggiani)]

Just throwing this out there: maybe the JIT would do it? It certainly could observe the built-in dict being converted into a built-in frozendict and the dict be discarded. With proper escape analysis it could make the optimization of using the stealing mechanism instead of the normal constructor.

(I’m hopeful the JIT will not go away.)

[barry (Barry Warsaw)]

I don’t particularly like all the long and bespoke method names, so I think if we go down this route, we should reconsider PEP 351.

[vstinner (Victor Stinner)]

@encukou

The pattern of consuming mutable input will start being used more, and perhaps preferred (for efficiency), in Python code as well.
This is a “function colouring” problem: if there’s a “take” function at the end of the call chain, any non-“take” caller need to copy the input. And crucially, in most existing Python code, functions tend to preserve their input.

I don’t see why such code should call .as_frozendict_and_clear() method. This method doesn’t fit all use cases. It fits well in some specific use cases. Also, I didn’t talk about modifying inputs.

@encukou

This worries me. Adding take_frozendict would encourage new code to bake destroying their input into their API. We might get a better Python ecosystem if we instead encourage users to build a frozendict once, at a boundary of a system, and then passing that around.

I didn’t give examples where inputs are modified. The typical usecase is a function creating a temporary dict, converts the dict to frozendict, returns the frozendict, and discards the dict.

Maybe it’s easier to understand with examples from the stdlib.

Example: copy.deepcopy()

Extract of the Lib/copy.py code:

def _deepcopy_frozendict(x, memo, deepcopy=deepcopy):
    y = {}  # dict local to the function
    for key, value in x.items():
        y[deepcopy(key, memo)] = deepcopy(value, memo)
    ...
    return frozendict(y)
    # discard dict 'y'
d[frozendict] = _deepcopy_frozendict

See the last return frozendict(y) instruction converting the dict to a frozendict.

Example: json.loads()

Another example is the object_pairs_hook parameter of json.loads() used to create frozendict instead of dict:

>>> json.loads('{"x": [1, 2, 3]}', object_pairs_hook=frozendict, array_hook=tuple)
frozendict({'x': (1, 2, 3)})

For better performance, object_pairs_hook=frozendict could be replaced with object_pairs_hook=dict.as_frozendict_and_clear. Again, the dict is discarded anyway, the dict is a fresh object created by json.

The function creates a dict, fill the dict, converts the dict to a frozendict, and then discards the dict.

Example: pickle.loads()

To (re)create a frozendict, the pickle protocol first creates a mutable dict, converts it to a frozendict, and then discards the dict.

>>> fd = frozendict(x=1, y=2)
>>> fd.__reduce_ex__(4)
(<function __newobj__ at 0x7f25714fd610>, (<class 'frozendict'>, {'x': 1, 'y': 2}), None, None, None)

>>> import pickle
>>> s=pickle.dumps(fd)
>>> import pickletools
>>> pickletools.dis(s)
    0: \x80 PROTO      5
    2: \x95 FRAME      47
   11: \x8c SHORT_BINUNICODE 'builtins'
   21: \x94 MEMOIZE    (as 0)
   22: \x8c SHORT_BINUNICODE 'frozendict'
   34: \x94 MEMOIZE    (as 1)
   35: \x93 STACK_GLOBAL
   36: \x94 MEMOIZE    (as 2)
   37: }    EMPTY_DICT
   38: \x94 MEMOIZE    (as 3)
   39: (    MARK
   40: \x8c     SHORT_BINUNICODE 'x'
   43: \x94     MEMOIZE    (as 4)
   44: K        BININT1    1
   46: \x8c     SHORT_BINUNICODE 'y'
   49: \x94     MEMOIZE    (as 5)
   50: K        BININT1    2
   52: u        SETITEMS   (MARK at 39)
   53: \x85 TUPLE1
   54: \x94 MEMOIZE    (as 6)
   55: \x81 NEWOBJ
   56: \x94 MEMOIZE    (as 7)
   57: .    STOP

Example: marshal.loads()

An example in C, from Python/marshal.c (simplified code):

    case TYPE_DICT:
    case TYPE_FROZENDICT:
        v = PyDict_New();
        for (;;) {
            key = r_object(p);
            val = r_object(p);
            if (PyDict_SetItem(v, key, val) < 0) {
                ...
                break;
            }
            ...
        }
        if (type == TYPE_FROZENDICT && v != NULL) {
            Py_SETREF(v, PyFrozenDict_New(v));
        }
        retval = v;
        break;

Py_SETREF(v, PyFrozenDict_New(v)) replaces the dict with a frozendict and discards the dict.

---

Cody Maloney conducted a great analysis of functions of the io module, to see which functions create a temporary bytearray, and has to return a bytes since the API return type is bytes. He found multiple functions using this pattern in the _pyio module. The idea would be similar, but for dict and frozendict.

Well, right now, there are less functions using the return frozendict(dict) pattern since frozendict was just added to Python 3.15 I expect to see this pattern more often in new code.

Adding bytearray.take_bytes() doesn’t mean that all functions using bytearray must now call it. It depends on the usecase. For example, the method should not be used if the bytearray is a function argument.

[steve.dower]

@vstinner

@encukou

This worries me. Adding take_frozendict would encourage new code to bake destroying their input into their API. We might get a better Python ecosystem if we instead encourage users to build a frozendict once, at a boundary of a system, and then passing that around.

I didn’t give examples where inputs are modified.

No, but the API would add the possibility (and the apparent endorsement) of modifying them. There’s no easy way to set up syntax or linter rules to prevent it, and so our second best option is to make it really obvious that you’re modifying someone else’s dict (the best option is to disallow it).

Basically, if any random code could destroy the dict you thought you were keeping, you’ll have to start copying it before you pass it. That spoils all the performance benefit being proposed here - we may as well have let the function copy it itself.

Your examples would all benefit from a new constructor for frozendict that allows it to be mutated until freeze is called. That doesn’t make dict worse, whereas allowing random library code that’s supposed to only be reading the dict to actually consume/destroy it does make using dict worse.

[vstinner (Victor Stinner)]

@jacopoabramo

Not sure if it applies, but I think I read in another thread that dict.freeze() was also suggested (or maybe I’m even misremembering what the thread was about anyway). Is the intention to maintain consistency with bytearray.take_bytes() that this option is not being considered? Or is it because freeze() might be misinterpreted somehow?

Proposed dict.as_frozendict_and_clear() method only does two things: (1) create a frozendict and (2) clear the dict.

Usually, .freeze() refers to a more complex process where keys and values are also converted to immutable types. For example, {'key': [1, 2, 3]}.freeze() with list value would become frozendict({'key': (1, 2, 3)}) with tuple value.

There are multiple projects on PyPI implementing such “deep freezing” protocol with various options and behaviors.

@barry

I don’t particularly like all the long and bespoke method names, so I think if we go down this route, we should reconsider PEP 351.

Again, I’m not proposing to touch keys or values in my proposed method. Only to create a frozendict with the same keys and values.

PEP 351 is a different protocol for a different use case. There is a need for that, since multiple PyPI projects implement it

[vstinner (Victor Stinner)]

@vstinner

If we add such method, it would also be interesting to add a similar list.as_tuple_and_clear() and set.as_frozendset_and_clear() methods.

I created a draft pull request adding dict.take_frozendict(), list.take_tuple() and set.take_frozenset() methods (first commit), and modifying the stdlib to use these new methods (second commit), to see how it can look alike: PR: Add dict.take_frozendict() method.

Note: Don’t use this PR to run benchmarks, the implementation is naive (not O(1)). For my benchmarks, I used a different efficient implementation (O(1)).

Some examples using this new methods.

Function converting a temporary list to a tuple:

    @property
    def args(self):
        args = []
        for param_name, param in self._signature.parameters.items():
            ...
            if param.kind == _VAR_POSITIONAL:
                # *args
                args.extend(arg)
            else:
                # plain argument
                args.append(arg)

-        return tuple(args)
+        return args.take_tuple()

Function converting a temporary dict to a frozendict:

def _deepcopy_frozendict(x, memo, deepcopy=deepcopy):
    y = {}
    for key, value in x.items():
        y[deepcopy(key, memo)] = deepcopy(value, memo)
    ...
-    return frozendict(y)
+    return y.take_frozendict()

Convert a list-comprehension to a tuple:

-        return tuple([_asdict_inner(v, dict_factory) for v in obj])
+        return [_asdict_inner(v, dict_factory) for v in obj].take_tuple()

Convert a set-comprehension to a frozenset:

-_ATTRIB_DENY_LIST = frozenset({
+_ATTRIB_DENY_LIST = {
     name.removeprefix("assert_")
     for name in dir(NonCallableMock)
     if name.startswith("assert_")
-})
+}.take_frozenset()

Frozendict literal, when frozendict(key=value, ...) syntax cannot be used:

-_capability_names = frozendict({
+_capability_names = {
     _curses.KEY_A1: 'ka1',
     _curses.KEY_A3: 'ka3',
     _curses.KEY_B2: 'kb2',
     ...
-    })
+    }.take_frozendict()

Frozenset literal:

-    _ID_KEYWORDS = frozenset({"True", "False", "None"})
+    _ID_KEYWORDS = {"True", "False", "None"}.take_frozenset()

[Dutcho]

I’d be interested in the type annotations, but I think those weren’t part of the commit yet, were they?
Esp. list.take_tuple, that would need to be varying length list[T] → tuple[T, …] probably.

[BrenBarn (Brendan Barnwell)]

@encukou

And -0 for making this a function in some stdlib module – I think that’s ultimately the way to go, but adding it right now feels premature.

I agree that all of this seems premature to me. Frozendict isn’t even in a released version of Python yet! I’d say it makes sense to wait a bit and see what kinds of situations people bump up against where they feel the need to do such a conversion, and then we will have more concrete ideas of how to meet that need.

[cmaloney (Cody Maloney)]

I want to add two specific cases that aren’t just performance bytearray.take_bytes helped solve. The changes did speedup microbenchmarks and some pyperformance cases over 10%. They also made some long standing issues solvable and enabled cleaner, simpler solutions to common I/O code patterns.

1. Building values inside functions that must return immutable objects.

   gh-60107 “Remove copy from bytearray to bytes in rawiobase_read() implementation” from 2012 shows this pattern well. The generic method .read() needs to have a mutable buffer internally which is passed to a provided .readinto but return an immutable bytes. In FileIO for efficiency this used a mutable bytes directly until a recent conversion to PyBytesWriter. For RawIOBase.read a bytearray + copy to bytes was used which made the generic method significantly slower.

2. Having a “working set” then taking/freezing once you hit a marker.

   gh-141863 “Use bytearray.take_bytes to speed up asyncio.streams”. A lot of code wants to process data until some marker / indicator such as end of line or end of file. That tends to mean building up a temporary changing working set before “freezing” it into the value returned. Removing the copies simplified the code which previous had to do copy and clear separately.

There’s a third case that I think applies a lot to dict that I didn’t encounter with bytearray because the default is immutable bytes: Building out “default” arguments and loading “constant” configuration that is passed through an application. That the empty dictionary shouldn’t be used as a default argument is fairly well known. With frozendict there’s now a safe option. A program could read from a file what the default value should be and build a frozendict which will be used as the default for the argument on every invocation of a function for the runtime of a program.

[sobolevn (Nikita Sobolev)]

I don’t see any semantical differences between proposed .take_frozendict API and existing .clear API in terms of mutability. They both mutate the object the same way. Is it something that python devs currently take special care of? No. People just know that clearing the dict - does clear the dict.

The same is true for existing .take_bytes. Does it cause any real problems? No, in my opinion it really helps to solve them by providing efficient and clean API to convert the type into an immutable counterpart.

In my opinion any addition to the language that makes immutable structures easier / more efficient to use is a good thing.

+1 from me