gh-112075: Iterating a dict shouldn't require locks by DinoV · Pull Request #115108 · python/cpython · GitHub

Makes iteration of a dict be lock free for the forward iteration case.

Handles races against the dict as well as allowing the iterator to be used from multiple threads simultaneously.

Includes some of the shared object marking from #115109

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

I think we want to avoid expensive atomic operations, like atomic compare exchange and atomic increments, as well as avoiding locking.

This means giving up some atomicity for list and dict iterators compared to the GIL behavior. We should still avoid crashes/memory corruption, but I think it's okay for concurrent calls to next(it) on the same iterator object to return the same object. These iterators are almost always used by only a single thread and the performance cost of making the next atomic is relatively high.

See #114843 for the list iterator changes.

I think we want to avoid expensive atomic operations, like atomic compare exchange and atomic increments, as well as avoiding locking.

This means giving up some atomicity for list and dict iterators compared to the GIL behavior. We should still avoid crashes/memory corruption, but I think it's okay for concurrent calls to next(it) on the same iterator object to return the same object. These iterators are almost always used by only a single thread and the performance cost of making the next atomic is relatively high.

I was worried some crazy person might be using these things to distribute work across threads :P. I'm happy to make relax the guarantees and see how that goes. I suppose if that ever becomes an issue we can deal with it then :)

Suggested change

      
            #endif
          
            #ifndef Py_GIL_DISABLED
          
            #else /* Py_GIL_DISABLED */

Suggested change

      
            #endif
          
            #endif  /* Py_GIL_DISABLED */

A few code style comments below

has_unique_reference already has special cases for Py_GIL_DISABLED and the default build:

Suggested change

      
            #ifdef Py_GIL_DISABLED
          
                if (has_unique_reference(result)) {
          
            #else
          
                if (Py_REFCNT(result) == 1) {
          
            #endif
          
                if (has_unique_reference(result)) {

I think the preferred style is to always include braces in new C code

Same here

Maybe use the wrappers from pycore_pyatomic_ft_wrappers.h to reduce the number of #ifdef statements.

This looks good, but I think it'd be better if acquire_key_value follows the -1/0 convention. The comment above acquire_key_value would need to be updated too.

Also here: -1 for error and 0 for success

…values seen

) Makes iteration of a dict be lock free for the forward iteration case.

bedevere-app Bot mentioned this pull request Feb 6, 2024

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

Closed

DinoV added skip news topic-free-threading labels Feb 6, 2024

DinoV force-pushed the nogil_dict_iter_threadsafe branch 2 times, most recently from 1266799 to 8d3080b Compare February 6, 2024 22:47

DinoV changed the title gh-112075: Accessing a single element should optimistically avoid locking gh-112075: Iterating a dict shouldn't require locks Feb 6, 2024

DinoV force-pushed the nogil_dict_iter_threadsafe branch from 8d3080b to bf395f6 Compare February 6, 2024 22:54

DinoV mentioned this pull request Feb 6, 2024

gh-112075: Accessing a single element should optimistically avoid locking #115109

Merged

DinoV force-pushed the nogil_dict_iter_threadsafe branch 3 times, most recently from 2b2e75a to 0dd1a06 Compare February 7, 2024 00:14

DinoV marked this pull request as ready for review February 7, 2024 00:48

DinoV requested review from markshannon and methane as code owners February 7, 2024 00:48

bedevere-app Bot added the awaiting core review label Feb 7, 2024

DinoV requested a review from colesbury February 7, 2024 20:39

colesbury reviewed Feb 8, 2024

View reviewed changes

Comment thread Objects/dictobject.c Outdated

DinoV force-pushed the nogil_dict_iter_threadsafe branch from 0dd1a06 to 3c03084 Compare February 16, 2024 00:43

methane reviewed Feb 16, 2024

View reviewed changes

colesbury reviewed Feb 21, 2024

View reviewed changes

DinoV force-pushed the nogil_dict_iter_threadsafe branch 3 times, most recently from e2a13a2 to 0941e62 Compare February 21, 2024 22:06

colesbury approved these changes Feb 22, 2024

View reviewed changes

bedevere-app Bot added awaiting merge and removed awaiting core review labels Feb 22, 2024

DinoV added 2 commits February 22, 2024 10:09

Thread safe lock-free iteration

afddb70

Don't use atomics for iteratio and allow multiple threads to race on …

39bc495

…values seen

DinoV added 5 commits February 22, 2024 10:09

Fixup ifdef/ifndef

902ce67

Use has_unique_reference

0ba2f5d

Less atomics

042cf26

Fix style issues

a079a6d

acquire_key_value returns -1 and 0

a1d7718

DinoV force-pushed the nogil_dict_iter_threadsafe branch from 0941e62 to a1d7718 Compare February 22, 2024 18:32

DinoV merged commit 1002fbe into python:main Feb 22, 2024

bedevere-app Bot removed the awaiting merge label Feb 22, 2024

woodruffw pushed a commit to woodruffw-forks/cpython that referenced this pull request Mar 4, 2024

pythongh-112075 : Iterating a dict shouldn't require locks (python#115108

13bd0c0

) Makes iteration of a dict be lock free for the forward iteration case.

diegorusso pushed a commit to diegorusso/cpython that referenced this pull request Apr 17, 2024

pythongh-112075 : Iterating a dict shouldn't require locks (python#115108

3b06e72

) Makes iteration of a dict be lock free for the forward iteration case.

sobolevn mentioned this pull request May 9, 2024

gh-118849: Fix "code will never be executed" warning in dictobject.c #118850

Merged

LukasWoodtli pushed a commit to LukasWoodtli/cpython that referenced this pull request Jan 22, 2025

pythongh-112075 : Iterating a dict shouldn't require locks (python#115108

9b49cc5

) Makes iteration of a dict be lock free for the forward iteration case.

devdanzin mentioned this pull request Jul 19, 2026

Sharing a dict iterator across threads double-DECREFs di_dict under free-threading #154130

Open

+                  // Even though we hold the lock here we may still lose a race against
+                  // a lock-free iterator, therefore we may end up retrying our iteration.
+              retry:
+                  start_pos = i = _Py_atomic_load_ssize_relaxed(&di->di_pos);

                   return NULL;
               }
+              #endif

		static int
		acquire_key_value(PyObject *key_loc, PyObject value, PyObject **value_loc,

		if (values == NULL)
		goto concurrent_modification;

		if (i >= used)
		goto fail;

gh-112075: Iterating a dict shouldn't require locks by DinoV · Pull Request #115108 · python/cpython · GitHub

Uh oh!

Uh oh!

gh-112075: Iterating a dict shouldn't require locks - #115108

gh-112075: Iterating a dict shouldn't require locks#115108DinoV merged 7 commits intopython:mainpython/cpython:mainfrom DinoV:nogil_dict_iter_threadsafeDinoV/cpython:nogil_dict_iter_threadsafeCopy head branch name to clipboard

Conversation

DinoV commented Feb 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

colesbury left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

DinoV commented Feb 16, 2024

Uh oh!

methane Feb 16, 2024

Choose a reason for hiding this comment

Uh oh!

methane Feb 16, 2024

Choose a reason for hiding this comment

Uh oh!

colesbury left a comment

Choose a reason for hiding this comment

Uh oh!

colesbury Feb 21, 2024

Choose a reason for hiding this comment

Uh oh!

colesbury Feb 21, 2024

Choose a reason for hiding this comment

Uh oh!

colesbury Feb 21, 2024

Choose a reason for hiding this comment

Uh oh!

colesbury Feb 21, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

colesbury left a comment

Choose a reason for hiding this comment

Uh oh!

colesbury Feb 22, 2024

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

gh-112075: Iterating a dict shouldn't require locks#115108
DinoV merged 7 commits into
python:mainfrom
DinoV:nogil_dict_iter_threadsafe

DinoV commented Feb 6, 2024 •
edited
Loading

colesbury left a comment •
edited
Loading