» pyperf timeit -s 'import msgspec; s = msgspec.defstruct("s", [("x", dict[str, int])]); d = {"x": {str(x): x for x in range(10000)}}' 'msgspec.convert(d, type=s)'
.....................
Mean +- std dev: 454 us +- 7 us
» pyperf timeit -s 'import msgspec; s = msgspec.defstruct("s", [("x", frozendict[str, int])]); d = {"x": {str(x): x for x in range(10000)}}' 'msgspec.convert(d, type=s)'
.....................
Mean +- std dev: 499 us +- 23 us
As you can see just changing the data type from dict to frozendict (the code is identical inside, just +1 PyFrozenDict_New call for the frozendict branch) will inrease the total app timings by 10%
Currently, if you want to create a frozendict object from the C-API, you would have to:
Create a regular PyDict_New() object first
Then fill it with keys / values with PyDict_SetItem / etc
Then convert it to frozendict with PyFrozenDict_New
Why? Because PyDict_SetItem does not allow PyFrozenDict_Type objects and raises an exception. There are no other ways to build a frozendict.
Why is it not ideal?
Because we have to use create an intermediate structure, it consumes n * 2 amounts of memory
Because we have to reset all keys / values from this intermidate structre to the final one in PyFrozenDict_New with total operation O(n * 2) complexity. This would be especially noticable for big dict objects
What can we do instead?
Add new C-API function PyFrozenDict_FromDictSteal which would modify a PyDict_Type object in-place. It would require that this dict would be owned by the same thread and only have ob->refcount of 1. In this case we would just change the object type and reset the hash, it would take O(1) to do that
I prefer 3, then 1. The builder adds too much burden, and it is less convenient.
But before adding PyFrozenDict_FromDictSteal we should look what other reference stealing API already exist, and what benefit of adding new stealing APIs. For example, there are private functions with Take suffix that steal references for tuple or list, they are used in tight code. Should we make them public? We should design the convention and the name scheme for new stealing functions.
Looking at this from other point, how do you create the dict? Is the size or the set of keys fixed? Then it may be more beneficial to you to add a specialized function that takes the size and two arrays of keys and values. This will allow to preallocate the frozendict data and use the same keyword array with different values. We should compare this variant with stealing API, especially if we add the stealing variant of PyDict_SetItem.
I was thinking along those same lines as @storchaka regarding turning arrays of keys and values into a frozen dict.
And just to bike shed about the name if you go with the “stealing” option, it’s less about stealing than about mutating the original dicts type. I don’t know if we have other APIs that morph an objects type.
We’ve already debated making users handle native arrays of refcounted objects in the CAPI-WG discussion linked by Stefan, and basically not enough of us liked it or agreed on a design to see it as viable (my main objection is the ambiguity of refcounts in the face of errors, and the amount of code we force users to write to handle it, rather than a SetItem API that handles it - but read the thread before you argue this here, I left out details so I’ll know if you’re using my summary instead of catching up properly!)
I very much lean towards the builder or the “steal” API here, which are basically going to be the same thing. Our builder would probably be a regular dict, with separate interfaces to make it impossible (within C’s permissiveness) for it to escape into regular code, and then an O(1) “conversion” as the final build step. It’s more APIs, and I wouldn’t want them in the stable ABI for bloat reasons[1], but it’s the safest design for directly constructing a specific type of object that doesn’t put undue preparation steps onto the user’s code.
If 10% performance hit makes it not worth it, then you don’t care about stability enough to make the tradeoff, sorry. We can’t guarantee every single API forever, so we must be selective about which get labelled as such. Otherwise, we’ll have to make more breaking changes to the “stable” ABI, and if that’s okay for you then you don’t care about stability enough, which was my original point ↩︎
Another way to think about it is “draining” the original container. Rust vectors have a drain method that mutably “drains” a slice of a vector by removing the subslice and returning it.
Maybe PyFrozenDict_DrainFromDict is a little nicer than “steal”?
Of course you’d have to implement that without the 1 mutable view XOR many immutable views semantics of Rust, but I think the refcount of 1 semantics work out to the same thing.
I’d be okay with an API that explicitly leaves the original dict alive but empty. If we make it steal the reference, we can keep any last-reference optimisations fully internal. For uses that know they have the sole reference, it’s basically the same as a “more efficient” API, but we also get to have deterministic behaviour (if perhaps not so useful).
Leaving the original dict alive but in a “throws if used” error state might make more sense, but it doesn’t currently exist, and adding it might be too big.
I agree. Changing an object type if its refcount is 1 sounds fragile and can lead to nasty bugs.
It sounds safer to create a new frozendict object, move the contents from the dict, and then clear the dict. It would work even if the refcount is 2 or higher.
During PEP 814 discussion, it was discussed to add a (public) dict method to create a frozendict with O(1) complexity. The idea was added to PEP 814 Deferred Ideas. If such method is added, it can have the same behavior: clear the dict.
We already have a similar internal C API to convert a list to a tuple: _PyList_AsTupleAndClear() creates a new tuple from a list and clears the list. It avoids an inefficient Py_INCREF() / Py_DECREF() dance on items thanks to the usage of _PyTuple_FromArraySteal() function.
I created the discussion Add a dict method to convert to a frozendict? to propose adding methods to dict, list and set for effecient conversions to immutable frozendict, tuple and frozenset.
