Provide a C-API to efficently convert `dict` into `frozendict`

Core Development C API
21

So sadly, it seems like d.__class__ = frozendict idea doesn’t work on practice (at least, in the current code).

We are talking about the C API here. It is as simple as Py_SET_TYPE(d, &PyFrozenDict_Type).
We can make it work. The debate is what should we do.

You and Steve have convinced me that mutating a dict that may still be live is too risky,

Give that, I think PyDict_AsFrozenDictSteal is the way to go. It provides a safe and the most efficient way to create frozendicts.

To clarify the semantics of PyDict_AsFrozenDictSteal is:

def PyDict_AsFrozenDictSteal(d: dict) -> frozendict:
      return frozendict(d)

and stealing the reference allows in-place conversion when the argument is provably the only reference to the dict.

2 Likes
22

This would require us to track the refcount of the passed dict object, wouldn’t it? Making it work for objects with refcount > 1 can lead to different bugs.

In my opinion current PyDict_AsFrozenDictAndClear has better semantics. It does not require any complex semantic rules and just mutates the passed dict as regular .clear() call does. Which seems pretty clean?

23

I would argue that the semantics of PyDict_AsFrozenDictSteal are simpler than PyDict_AsFrozenDictAndClear and is safer.

I’ll state the semantics again:

def PyDict_AsFrozenDictSteal(d: dict) -> frozendict:
    return frozendict(d)

Plus the reference d is stolen.

Compare to PyDict_AsFrozenDictAndClear:

def PyDict_AsFrozenDictAndClear(d: dict) -> frozendict:
    res = frozendict(d)
    d.clear()
    return d

If the program holds another reference to d, then it will be unchanged by PyDict_AsFrozenDictSteal, but PyDict_AsFrozenDictAndClear will clear d, with possibly surprising side effects.

If the program does not hold another reference to d, both functions have the same effect, but PyDict_AsFrozenDictSteal is a bit faster.

24

If the program holds another reference to d, then it will be unchanged by PyDict_AsFrozenDictSteal

But how can we do that? I might be missing something, but right now we just take existing ->ma_keys and ->ma_values from the existing dict object. Transfer them to a new frozendict object. Set empty keys and values to the existing dict. The same way .clear() does.

But, if we want to keep other reference to d unchanged with PyDict_AsFrozenDictSteal. This way we would have to:

  • create new frozendict object,
  • copy keys and values,
  • set them to this new object

right? I am not sure that we can reuse them as-is, because they have their own refcounting and explicit invariants that we must hold. What would be the benefit of this approach in terms of performance?

Probably, I just miss something obvious :slight_smile:

1 Like
25

To be clear, our AndClear function also steals the reference that is passed in, but it leaves the object itself valid (though it would be immediately deallocated if there are no other references).

The “stealing” version we rejected was to steal the contents and leave it invalid - in essence, a null internal pointer - which would assume that it was the only reference to the object and require that it be immediately deallocated. This isn’t actually either of your examples (your first is a copy, and your second is a copy+clear, and neither is actually just moving the internal data pointers from one type to the other, which is the O(1) operation that’s desired).

So the “Clear” part is referring to the effect on any remaining references to the same dict. If we know that there’s only one reference (which we can check inside the function, but can’t rely on the user to check before they call it), we can be more efficient. But because the user is not required to guarantee that condition, it’s safe for them to just use and the behaviour is well-defined.

I fully expect (and hope) that it’s only ever going to be used by code that is intending to construct a frozen dict and won’t have shared the temporary dict anywhere. But with multiple millions of users, the only thing we can really assume is that every possible variation will exist, so we design our code not to fail. And for Python’s C API, “failure” is inconsistent C state (i.e. segfaults), and not inconsistent Python state (i.e. empty dicts).

5 Likes
26

Somewhat coincidentally, and independently of the current discussion, I drafted this PEP: PEP 839: PyFrozenSetWriter and PyFrozenDictWriter C API by corona10 · Pull Request #5041 · python/peps · GitHub

Given the current state of the CPython codebase, I personally believe that the right way to construct truly immutable frozendict and frozenset objects is to use the existing Writer pattern, or more generally, a builder pattern.

I have also included several concrete cases in CPython that could be migrated to the proposed API. I would appreciate it if you could take a look.

1 Like
27

It is important that the construction of an immutable object be observable atomically from other threads. This makes it easier to access immutable objects concurrently from multiple threads.
And PyDict_AsFrozenDictAndClear() satisfies this condition. The frozendict constructed by PyDict_AsFrozenDictAndClear() is not accessible from other threads during construction.

I agree that it is preferable for the dict passed to PyDict_AsFrozenDictAndClear() not to be observed by other threads through the GC, but that is not a necessary condition. It does not result in a TSan error, nor does it cause Python to segfault.

Regarding the Writer (or Builder) API, I am concerned about whether it can achieve performance at least as good as PyDict_AsFrozenDictAndClear(), and whether losing the ability to use APIs such as PyDict_ContainsString() and PyDict_SetDefault() would limit its use cases.

For example, a JSON parser might want to report an error immediately when it encounters a duplicate key, and create a frozendict only after successfully reaching the end of the object.
An HTTP header parser might want to concatenate the value strings when it encounters duplicate keys.
Also, when constructing a Python dict from a mapping type in a language other than Python, an API such as PyDict_FromItems() might provide better performance if calls to the Python/C API introduce overhead.

In any case, I still do not know enough about the actual use cases for frozendict. I would like to hear requests from multiple projects besides msgspec as well.

2 Likes
28

Well, considering what people expect from frozendict or frozenset, can we really call them immutable if other threads can observe them in different states during construction? I do not think so. During that small window, they can effectively be treated as mutable objects, even if the window is very short.

but that is not a necessary condition. It does not result in a TSan error, nor does it cause Python to segfault.

No, this is not the truth.
See:

1 Like
29

There might be some misunderstanding.

Using PyDict_AsFrozenDictAndClear(), you build a regular temporary mutable dict. So it’s fine if this one is tracked by the GC. It’s being modified by PyDict_SetItem(), PyDict_Update() and other regular PyDict functions.

Then PyDict_AsFrozenDictAndClear() creates a new frozendict and moves items from the dict to the frozendict. When the frozendict is initialized, it’s tracked by the GC. The dict is cleared. Again, regular dict operation.

You cannot see the frozendict being modified by the GC. There is no (known) TSAN issue.

See the PR for the implementation: gh-153410: Add `PyDict_AsFrozenDictAndClear` C-API by sobolevn · Pull Request #153413 · python/cpython · GitHub

4 Likes
30

Yeah I am not a big fan for this detail (since we can avoid temporal object if we use writer pattern). But if other things are guaranteed. It’s okay-sh for me :slight_smile:

31

The main reason we don’t need a writer pattern here is because a [frozen]dict fundamentally deals in Python objects (unlike say a string, which deals in native char’s). So the difference between the existing dict API and a hypothetical builder API would be so minimal as to be redundant - you’d have the ability to assign a PyObject value with a PyObject key. Maybe we’d offer a const char * key as well, but that’s still only matching the dict API.

An advantage of the conversion is that code that wants to use it and also be compatible with earlier versions of Python can just #if-away the call. Practically everything you might do to a frozendict would be done the same way to a dict, so provided your code is correct then it will still be correct on earlier versions without modification. Particularly if you’ve already got helper functions for filing a dict with some data, it’s now much easier to fill it and then freeze it without a massive rewrite to use a builder.

So on balance, nobody really benefits from a builder here, at least in our API. I could definitely imagine a higher-level wrapper (such as nanobind or PyO3) wanting to have a native building API that wraps up a mutable dict and the conversion, but there’s nothing for us to gain by baking that in at our level.

32

So on balance, nobody really benefits from a builder here, at least in our API.

Okay, I agree that the currently proposed API is sufficient for the existing uses of frozendict.

However, if we also look at how frozenset is used, there are cases where elements need to be added one by one from external objects. In those cases, creating a temporary mutable set first would be inefficient. This is one of the reasons why PySet_Add() it currently allows adding elements to a frozenset.

However, semantically, allowing a mutation API to operate on an immutable container seems wrong. It could also set a precedent for exposing similar APIs for frozendict.

For this reason, I would prefer to introduce Writer APIs for both frozenset and frozendict, and then begin soft-deprecating the use of PySet_Add() with frozenset.

PyDict_AsFrozenDictAndClear() could perhaps also be implemented as a use case of the Writer API.

I acknowledge that this is broader than the API currently under discussion, as it also involves frozenset.

33

I for one am quite happy to take past/future designs into account when we’re making choices here. Consistency is one of the main reasons we set up a CAPI working group, after all.

This works? Yeah, we should probably do it anyway.

Perhaps, but it’s also entirely unavoidable. You should not mutate an immutable set, therefore, you need to mutate the mutable set first and then copy its values in.

For cases where we have the same internal representation, the As*AndClear metaphor lets us transfer the internal state without an O(N) copy. If the frozen version has a different internal state from the mutable one[1], we must copy, because we must recalculate the new internal state. At that point, simple construction is by far the best metaphor.

If I had to generalise, then I’d say you’ll get better lookup behaviour when it’s calculated from all the values in one go than by adding them one at a time (think of choosing dict buckets, but when you know it’s immutable then you can do even more efficient bucketing based on the values, like a trie).

Plus when we use our own data structure for the temporary storage, everything stays safe enough during construction. Code can be reused (e.g. a helper function that uses PyObject_SetItem or even PyDict_SetItem), and our API stays smaller and more learnable. Constructing an immutable value in Python is a specialist activity - it’s never strictly necessary (except where the value is only immutable, such as strings and integers) - and so it doesn’t need ten of its own APIs when a single conversion from an equivalent value can exist and be efficient.

All of that to say, if we had a builder API here or for frozenset, it would have exactly the same shape, behaviour and characteristics as the existing API for dict and set, just with different names, and we’d be forcing users to learn and use a set of new APIs rather than a single conversion that they don’t really need.

  1. Which I hope it should, since we should be able to optimise the representation for more expensive construction and cheaper lookups, compared to a mutable structure. ↩︎

4 Likes
34

In summary, I also shared my view with @vstinner at EuroPython that the PyDict_AsFrozenDictAndClear() is good enough to be added.

To clarify, I participate in all DPO discussions in my individual capacity, not as a Steering Council representative, unless I explicitly state otherwise.

1 Like
35

To echo others from my point of view: the question is whether set and dict themselves are good enough as builders.

Given the optimizations wee need anyway (e.g. for “dict that’s uniquely owned by the thread that created it”), and ones that would be nice in general (like “build a dict from C arrays”, if we figure out the details), it looks that the unneeded overhead is just the PyObject header.
That’s not worth special API, which makes the AndClear functions the right way to go.

1 Like