Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make dict objects thread-safe in --disable-gil builds #112075

Closed
Tracked by #108219
colesbury opened this issue Nov 14, 2023 · 9 comments
Closed
Tracked by #108219

Make dict objects thread-safe in --disable-gil builds #112075

colesbury opened this issue Nov 14, 2023 · 9 comments
Assignees
Labels
3.13 bugs and security fixes topic-free-threading type-feature A feature request or enhancement

Comments

@colesbury
Copy link
Contributor

colesbury commented Nov 14, 2023

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

@chgnrdv
Copy link
Contributor

chgnrdv commented Nov 17, 2023

I'd like to work on this one.

@colesbury
Copy link
Contributor Author

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 added a commit to chgnrdv/cpython that referenced this issue Nov 18, 2023
For `dict.__len__`, use `_Py_atomic_load_ssize_relaxed` to access `PyDictObject` `ma_used` field.

For the following methods
* `dict.fromkeys`
* `dict.copy`
* `dict_richcompare`
* `dict.clear`
* `dict.__sizeof__`
* `dict.__or__`
* `dict.__ior__`
* `dict.__reversed__`
* `dict.keys`
* `dict.items`
* `dict.values`

use critical section API, either in form of AC directive or macro.
@chgnrdv
Copy link
Contributor

chgnrdv commented Nov 18, 2023

@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
Copy link
Contributor

DinoV commented Jan 23, 2024

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
Copy link
Contributor Author

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
Copy link
Contributor

DinoV commented Jan 23, 2024

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
Copy link
Contributor Author

colesbury commented Jan 23, 2024

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.

DinoV added a commit that referenced this issue Jan 23, 2024
* Move more dict objects to argument clinic

* Improve doc strings

* More doc string improvements

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

---------

Co-authored-by: Erlend E. Aasland <[email protected]>
DinoV added a commit that referenced this issue Jan 25, 2024
… thread safety (#114512)

* Bring in a subset of biased reference counting:
colesbury/nogil@b6b12a9a94e

The NoGIL branch has functions for attempting to do an incref on an object which may or may not be in flight. This just brings those functions over so that they will be usable from in the dict implementation to get items w/o holding a lock.

There's a handful of small simple modifications:

    Adding inline to the force inline functions to avoid a warning, and switching from _Py_ALWAYS_INLINE to Py_ALWAYS_INLINE as that's available
    Remove _Py_REF_LOCAL_SHIFT as it doesn't exist yet (and is currently 0 in the 3.12 nogil branch anyway)
    ob_ref_shared is currently Py_ssize_t and not uint32_t, so use that
    _PY_LIKELY doesn't exist, so drop it
    _Py_ThreadLocal becomes _Py_IsOwnedByCurrentThread
    Add '_PyInterpreterState_GET()' to _Py_IncRefTotal calls.


Co-Authored-By: Sam Gross <[email protected]>
DinoV added a commit that referenced this issue Jan 29, 2024
DinoV added a commit that referenced this issue Jan 29, 2024
…ents (#114568)

Dictionary global version counter should use atomic increments
DinoV added a commit that referenced this issue Jan 30, 2024
…ty (#114629)

Refactor dict lookup functions to use force inline helpers
diegorusso pushed a commit to diegorusso/cpython that referenced this issue Apr 17, 2024
diegorusso pushed a commit to diegorusso/cpython that referenced this issue Apr 17, 2024
diegorusso pushed a commit to diegorusso/cpython that referenced this issue Apr 17, 2024
diegorusso pushed a commit to diegorusso/cpython that referenced this issue Apr 17, 2024
DinoV added a commit that referenced this issue Apr 22, 2024
…fe (#114742)

Make instance attributes stored in inline "dict" thread safe on free-threaded builds
DinoV pushed a commit to DinoV/cpython that referenced this issue Apr 23, 2024
DinoV pushed a commit to DinoV/cpython that referenced this issue Apr 24, 2024
DinoV pushed a commit to DinoV/cpython that referenced this issue Apr 25, 2024
DinoV added a commit that referenced this issue Apr 25, 2024
Lock shared keys in `Py_dict_lookup` and use thread-safe lookup in `insertdict`

Co-authored-by: Sam Gross <[email protected]>
DinoV added a commit that referenced this issue May 7, 2024
use thread state set of dict versions
@colesbury
Copy link
Contributor Author

@DinoV is the dict work finished? Should we close this issue?

@DinoV
Copy link
Contributor

DinoV commented May 7, 2024

@DinoV is the dict work finished? Should we close this issue?

I think so, anything else that comes up would just be a bug.

@DinoV DinoV closed this as completed May 7, 2024
SonicField pushed a commit to SonicField/cpython that referenced this issue May 8, 2024
DinoV pushed a commit that referenced this issue May 24, 2024
miss-islington pushed a commit to miss-islington/cpython that referenced this issue Jul 9, 2024
Fix dict thread safety issues
(cherry picked from commit f0ed186)

Co-authored-by: Germán Méndez Bravo <[email protected]>
colesbury pushed a commit that referenced this issue Jul 9, 2024
(cherry picked from commit f0ed186)

Co-authored-by: Germán Méndez Bravo <[email protected]>
estyxx pushed a commit to estyxx/cpython that referenced this issue Jul 17, 2024
Glyphack pushed a commit to Glyphack/cpython that referenced this issue Sep 2, 2024
…14256)

* Move more dict objects to argument clinic

* Improve doc strings

* More doc string improvements

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

* Update Objects/dictobject.c

Co-authored-by: Erlend E. Aasland <[email protected]>

---------

Co-authored-by: Erlend E. Aasland <[email protected]>
Glyphack pushed a commit to Glyphack/cpython that referenced this issue Sep 2, 2024
…n dict thread safety (python#114512)

* Bring in a subset of biased reference counting:
colesbury/nogil@b6b12a9a94e

The NoGIL branch has functions for attempting to do an incref on an object which may or may not be in flight. This just brings those functions over so that they will be usable from in the dict implementation to get items w/o holding a lock.

There's a handful of small simple modifications:

    Adding inline to the force inline functions to avoid a warning, and switching from _Py_ALWAYS_INLINE to Py_ALWAYS_INLINE as that's available
    Remove _Py_REF_LOCAL_SHIFT as it doesn't exist yet (and is currently 0 in the 3.12 nogil branch anyway)
    ob_ref_shared is currently Py_ssize_t and not uint32_t, so use that
    _PY_LIKELY doesn't exist, so drop it
    _Py_ThreadLocal becomes _Py_IsOwnedByCurrentThread
    Add '_PyInterpreterState_GET()' to _Py_IncRefTotal calls.


Co-Authored-By: Sam Gross <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
3.13 bugs and security fixes topic-free-threading type-feature A feature request or enhancement
Projects
None yet
Development

No branches or pull requests

3 participants