Make `dict` objects thread-safe in `--disable-gil` builds

[colesbury]

We are going to need a variety of techniques to make dictionaries thread-safe in --disable-gil builds. I expect this to be implemented across multiple PRs.

For context, here is the change from the nogil-3.12 fork, but things might be done a bit differently in CPython 3.13: colesbury/nogil-3.12@d896dfc8db

1. Most operations should acquire the dictionary object lock using the critical section API.
2. Dictionary global version counter should use atomic increments
3. PyDictKeysObject needs special handling (see below)
4. PyDictOrValues needs special handling (see below)
5. Accessing a single element should optimistically avoid locking for performance

In general, we want to avoid making changes which hurt the performance of the default build. The "critical sections" are no-ops in the default build, but we will need to take care with other changes. Some may be behind #ifdef guards.

PyDictKeysObject

Note that PyDictKeysObject is NOT a PyObject subclass.

We need a mutex in PyDictKeysObject because multiple threads may concurrently insert keys into shared PyDictKeysObject. The mutex is only used for modifications to "shared" keys; non-shared keys rely on the locking for the dict object.

In --disable-gil builds, we want to avoid refcounting shared PyDictKeysObject for performance and thread-safety reasons. Instead shared keys objects should be freed during cyclic GC. (Non-shared keys don't need reference counting because they "owned" by a single dict object.) We may want to consider making this change for both the default build and --disable-gil builds to make maintenance easier if there is not a negative perf impact.

PyDictOrValues

PyDictOrValues is the "managed" dict in some PyObject pre-headers. We need some locking/atomic operations to handle the transition between PyDictValues* and storing a PyDictObject*

Optimistically Avoid Locking

See https://peps.python.org/pep-0703/#optimistically-avoiding-locking.

Linked PRs

• gh-112075: Make some dict operations thread-safe without GIL #112247
• gh-112075: Adapt more dict methods to Argument Clinic #114256
• gh-112075: Add critical sections for most dict APIs #114508
• gh-112075: Add try-incref functions from nogil branch for use in dict thread safety #114512
• gh-112075: Use PyMem_* for allocating dict keys objects #114543
• gh-112075: Dictionary global version counter should use atomic increments #114568
• gh-112075: refactor dictionary lookup functions for better re-usability #114629
• gh-112075: Make PyDictKeysObject thread-safe #114741
• gh-112075: Make instance attributes stored in inline "dict" thread safe #114742
• gh-112075: Add a little specialization thread safety #114768
• gh-112075: Free-threaded dict odict basics #114778
• gh-112075: Add gc shared bits #114931
• gh-112075: Iterating a dict shouldn't require locks #115108
• gh-112075: Accessing a single element should optimistically avoid locking #115109
• gh-112075: Use relaxed stores for places where we may race with when reading lock-free #115786
• gh-112075: Remove compiler warning from apple clang #115855
• gh-112075: Avoid locking shared keys on every assignment #116087
• gh-112075: Enable freeing with qsbr and fallback to lock on key changed #116336
• gh-112075: Support freeing object memory via QSBR #116344
• gh-112075: Use atomic exchange in Py_SETREF so updating dict pointers doesn't race #116620
• gh-112075: _Py_dict_lookup needs to lock shared keys #117528
• gh-112075: Make _PyDict_LoadGlobal thread safe #117529
• gh-112075: Lock when inserting into shared keys #117824
• gh-112075: Fix race in constructing dict for instance #118499
• gh-112075: use per-thread dict version pool #118676
• gh-112075: Fix dict thread safety issues #119288
• [3.13] gh-112075: Fix dict thread safety issues (GH-119288) #121545
• gh-112075: Remove critical section in dict.get #129336
• gh-112075: Remove _PyObject_SetManagedDict() function #139737

[chgnrdv]

I'd like to work on this one.

[colesbury]

Thanks @chgnrdv! I think "making operations use the critical section API" can be started now, but most of the other steps still have some pre-requisites that are not yet implemented.

The dict changes are going to be pretty big. It may make sense to convert a few operations at a time to use the critical section API.

[chgnrdv]

@colesbury , I made the PR #112247 that covers the most obvious cases. Lots of methods are still to be converted, mostly the ones that access a single element and are expected to optimistically avoid locking. Most of them do not access PyDictObject fields directly and use _Py_dict_lookup function to get dict values.

[DinoV]

Regarding:

In --disable-gil builds, we want to avoid refcounting shared PyDictKeysObject for performance and thread-safety reasons.

This may be a non-issue in 3.12 and beyond. With the introduction of managed dicts when the values are all stored in the in-line array the shared dict keys is not incremented. If we make a full dict for the object then we will end up initializing it and adding a reference, but it seems like at least as far as the Python test suite is concerned that's a rare event. It seems like most processes hit it less than 10 times, and a handful hit it around 100. test_regrtest seems to hit it around 300.

[colesbury]

I think this avoiding refcounting PyDictKeysObject is something we will want to do, but it doesn't have to happen immediately. We can start with atomic reference count operations in free-threaded builds for now.

The prevalence of __dict__ attribute accesses varies greatly between projects. For example, PyTorch accesses self.__dict__ in every instantiation of nn.Module(), one of the basic types. To be clear, the issue is not really the overhead of atomic reference counting by themselves, but that it introduces a point of contention (inhibiting scaling) on state that's shared between all instances of a type. In other words, if you access self.__dict__ in a constructor, now creating instances of that type doesn't scale across threads. That's both something we want to avoid and surprising to users, because the shared state is an internal detail completely hidden from them.

[DinoV]

Can you explain more what you were thinking about freeing them during cyclic GC then? Given that Python's GC drives down reference counts I'm not 100% sure how that'd work. The only thing I can imagine working is that we maintain a separate list of all shared keys and note which ones weren't visited during a full GC, although maybe you had something better in mind :)

[colesbury]

The only thing I can imagine working is that we maintain a separate list of all shared keys and note which ones weren't visited during a full GC.

That's the basic idea, but the list only needs to bother with shared keys for types that were deallocated. If the type is still alive, then the shared keys must be alive too.

The strategy in nogil-3.12 was:

1. Shared keys objects are eligible for collection only after the containing type is freed. When that happens, they get enqueued in a per-interpreter linked list of maybe-dead shared keys (called tracked_shared_keys):
   https://github.com/colesbury/nogil-3.12/blob/nogil-3.12/Include/internal/pycore_dict_state.h#L48

2. To support this, shared keys objects have some extra state. They are actually PyDictSharedKeysObject, which embed a PyDictKeysObject.

3. During GC, we mark any shared keys referenced by a dict as live.

4. Later in the GC, we loop over the maybe-dead list (tracked_shared_keys), and free any shared keys that were not marked as live.

The collection is simpler than general PyObject collection because keys objects are private data structures that can only be referenced by dicts.