Add `PyDict_AsFrozenDictAndClear` public API

[sobolevn]

Discussion: https://discuss.python.org/t/provide-a-c-api-to-efficently-convert-dict-into-frozendict/107754/10
Issue: python/cpython#153410
PR: python/cpython#153413

Discussion summary:

• Currently, there's no clean way to create a frozendict instances from C code. We faced this in msgspec: Add frozendict support for 3.15+ msgspec/msgspec#1052 Since this is a project focused on performance, we don't quite like to use PyFrozenDict_New for this. Because it copies the dict we already have once again. It works for O(n) and uses more memory than it actually needs to
• New proposed API solves this by coping existing keys and values from any dict with O(1) complexity. Which is much faster
• All people in the discussion agreed that such API would be nice to have
• Most people in the discussion agreed that the taking an existing dict and transforming it to frozendict seems like a way to go

So, here it is :)
Looking forward to hearing your feedback!

• @encukou
• @erlend-aasland
• @serhiy-storchaka
• @vstinner
• @zooba

[vstinner]

API: PyObject* PyDict_AsFrozenDictAndClear(PyObject *dict)

The function fails with SystemError if the argument type is not dict or a dict subclass.

I'm fine with this API, but just the "O(1) complexity" part should be documented as an implementation detail (which was done in the PR).

By the way, there is a similar private _PyList_AsTupleAndClear() function. Maybe we should also promote it as a public function?

[sobolevn]

@vstinner

By the way, there is a similar private _PyList_AsTupleAndClear() function. Maybe we should also promote it as a public function?

Yes, this would also be a good idea for us. Here's how we parse tuple from json now (coping the list items manually and mutating a tuple instance):

static PyObject *
json_decode_vartuple(JSONDecoderState *self, TypeNode *type, TypeNode *el_type, PathNode *path) {
    PyObject *list, *item, *out = NULL;
    Py_ssize_t size, i;

    list = json_decode_list(self, type, el_type, path);
    if (list == NULL) return NULL;

    size = PyList_GET_SIZE(list);
    out = PyTuple_New(size);
    if (out != NULL) {
        for (i = 0; i < size; i++) {
            item = PyList_GET_ITEM(list, i);
            PyTuple_SET_ITEM(out, i, item);
            PyList_SET_ITEM(list, i, NULL);  /* Drop reference in old list */
        }
    }
    Py_DECREF(list);
    return out;
}

Source: https://github.com/msgspec/msgspec/blob/e1c6f23040583b43be58fd6d8c2362ff572ed501/src/msgspec/_core.c#L18103-L18122

But, I propose to discuss this separately. I will open a new discussion for this :)

[zooba]

The function fails with SystemError if the argument type is not dict or a dict subclass.

It should really be a TypeError.

By the way, there is a similar private _PyList_AsTupleAndClear() function. Maybe we should also promote it as a public function?

Agreed, and we should make sure the APIs match between them. Consistency is the important part here.

Are there any other types where this kind of thing might be useful in the future? Not so we add them now, but so we invent a design now that could extend to them later on (not that I foresee any issues with the As*AndClear model).

[sobolevn]

Are there any other types where this kind of thing might be useful in the future?

• dict and frozendict
• tuple and list
• set and frozenset maybe as well? However, I am not really sure. Currently some PySet_* functions like PySet_Add also work with frozenset objects and mutate them. In my opinion creating a set, mutating it and them converting it to frozenset efficently would be better?

That's everything I can remember right now :)

It should really be a TypeError.

In most cases were tend to use a pattern like:

int
PyDict_GetItemRef(PyObject *op, PyObject *key, PyObject **result)
{
    if (!PyAnyDict_Check(op)) {
        PyErr_BadInternalCall();
        *result = NULL;
        return -1;
    }
    // ...
}

and

PyObject *
PyDict_GetItemWithError(PyObject *op, PyObject *key)
{
    Py_ssize_t ix; (void)ix;
    Py_hash_t hash;
    PyDictObject*mp = (PyDictObject *)op;
    PyObject *value;

    if (!PyAnyDict_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // ...
}

which all raise SystemError. How do we decide on error type here?

[ngoldbaum]

There's also bytes and bytearray. I think that's it in the standard library though. array doesn't have an immutable counterpart and str doesn't have a mutable counterpart.

[zooba]

In most cases were tend to use a pattern like:

Most of PyDict_* is implementations of the mapping API, not intentional public APIs in themselves. They're only meant to be called indirectly, by PyObject_* functions that look up the actual function from the type object. In that context, we have an internal consistency error if the type doesn't match.

This new function is standard public API, and so it should use standard errors for "you passed the wrong type of object". (Arguably since everyone treats the concrete API as the "standard public API" now, we should change them, but that's a breaking change nobody is really interested in doing. Doesn't mean we should continue to make incorrect decisions.)

There's alsobytes and bytearray.

Yeah, these are good examples. bytearray has a bunch of locking problems already, so probably would never really be suitable for a stealing conversion function, but in theory stealing its contents as read-only makes sense, and we shouldn't need anything more complicated than this API for it.

Possibly a function PyIter_AsListAndClear[^1] could have some useful fast paths in it, but it doesn't quite fit the same naming. Nobody's actually proposing it, but I think we'd have a pretty serious argument about whether to name it consistently with the equivalent functions or make it something different (I'd be on the "internal consistency, even if the name is weird" side initially).

Also could hit similar arguments around PyList_FromArrayAndClear to steal all the references from a native PyObject * array. It's the same kind of operation in concept, but differs just enough that we'd likely have to argue about whether it's a "from-andclear/as-andclear" function or not.

Again, nobody's proposing these, but if anyone looks at these other ideas and goes "oh hey, if we do it this way now, those won't be an issue at all in the future", it'd be great to hear that idea now and not after we've committed to this design.

[vstinner]

There's also bytes and bytearray. I think that's it in the standard library though.

In Python 3.15, a public .take_bytes() method was added to byterray to convert byterray to bytes without memory copy:

$ python3.15
>>> b=bytearray(b'abc')
>>> b2=b.take_bytes()
>>> b2
b'abc'
>>> b
bytearray(b'')

It's similar design than PyDict_AsFrozenDictAndClear() and _PyList_AsTupleAndClear(): it converts a mutable type to an immutable type and clears the mutable type.

array doesn't have an immutable counterpart and str doesn't have a mutable counterpart.

Python 3.14 got a new PyUnicodeWriter() API which is more specialized to the str type.

[vstinner]

Possibly a function PyIter_AsListAndClear[^1] could have some useful fast paths in it, but it doesn't quite fit the same naming.

There are PySequence_Tuple() and PySequence_List() which need interesting allocation strategies, since the output length is not known in advance.

Also could hit similar arguments around PyList_FromArrayAndClear to steal all the references from a native PyObject * array.

There is a private _PyTuple_FromArraySteal() function doing that tuple.

For list, there is _PyList_FromStackRefStealOnSuccess() which takes an array of stack references, but stack references are only part of the internal C API.

[zooba]

Ah yeah, I forgot about the PySequence functions.

_PyTuple_FromArraySteal() // _PyList_FromStackRefStealOnSuccess()

Seems like we use "steal" often for internal functions - should we be sticking with that name? (I lean towards the "AndClear" naming, but am fairly neutral and open to counterarguments.)

[da-woods]

The function fails with SystemError if the argument type is not dict or a dict subclass.

Is there a reason to allow dict subclass? I don't think there's a proposal to have a Python API equivalent for this so it seems like you could go for the most restrictive form until someone has a convincing need for subclasses.

[vstinner]

I like/prefer PyDict_AsFrozenDictAndClear name, than using Steal suffix.

Is there a reason to allow dict subclass?

For me, it's fine to accept dict subclasses.

Other PyDict functions accept dict subclasses. For example, PyDict_Copy() accepts subclasses but always return a dict:

$ python3.16
>>> import _testlimitedcapi
>>> class DictSubclass(dict):
...     def __getitem__(self, key):
...         raise RuntimeError('do not get evil')
...     def __setitem__(self, key, value):
...         raise RuntimeError('do not set evil')
...     def __delitem__(self, key):
...         raise RuntimeError('do not del evil')
... 

>>> d = DictSubclass(x=1, y=2)
>>> d['x']
RuntimeError: do not get evil
>>> d['x'] = 9
RuntimeError: do not set evil
>>> del d['x']
RuntimeError: do not del evil

>>> d2 = _testlimitedcapi.dict_copy(d)  # PyDict_Copy()
>>> d2
{'x': 1, 'y': 2}
>>> type(d2)
<class 'dict'>

>>> d3 = d.copy()
{'x': 1, 'y': 2}
>>> type(d3)
<class 'dict'>

__getitem__(), __setitem__() and __delitem__() methods of the subclass are not called. Another example with PyDict_GetItemRef() and PyDict_SetItem():

$ python3.16
>>> import _testlimitedcapi, _testcapi
>>> class DictSubclass(dict):
...     def __getitem__(self, key):
...         raise RuntimeError('do not get evil')
...     def __setitem__(self, key, value):
...         raise RuntimeError('do not set evil')
...     def __delitem__(self, key):
...         raise RuntimeError('do not del evil')
... 
>>> d=DictSubclass(x=1, y=2)
>>> _testcapi.dict_getitemref(d, 'x')  # PyDict_GetItemRef()
1
>>> _testlimitedcapi.dict_setitem(d, 'z', 3)  # PyDict_SetItem()
0
>>> d
{'x': 1, 'y': 2, 'z': 3}

See Lib/test/test_capi/test_dict.py for details.

[vstinner]

About the function name, Nathan wrote:

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”?

[vstinner]

I created https://discuss.python.org/t/add-a-dict-method-to-convert-to-a-frozendict/108102 discussion to propose adding dict.as_frozendict_and_clear() method. If we decide to add such method in Python, it would be nice to use a similar name in the C API.

[encukou]

Seems like we use "steal" often for internal functions - should we be sticking with that name? (I lean towards the "AndClear" naming, but am fairly neutral and open to counterarguments.)

That's not about naming. PyDict_AsFrozenDict_Steal(d) would steal a reference to d, but not clear it. (Hence, the optimization would only apply for uniquely referenced dict: instead of deallocating d, CPython would mutate its type and call it a new frozendict.)

Maybe PyFrozenDict_DrainFromDict is a little nicer than “steal”?

That's a nice name, but Python already has {}.clear. Let's go with the existing term.