GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — gh-112075: Iterating a dict shouldn't require locks by DinoV · Pull Request #115108 · python/cpython

Conversation

DinoV commented Feb 6, 2024 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Contributor

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

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

colesbury left a comment •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

DinoV commented Feb 16, 2024

Copy link

Copy Markdown

Contributor Author

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 :)

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

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

Comment thread

Objects/dictobject.c Outdated

Comment on lines +4539 to +4541

		#endif

		#ifndef Py_GIL_DISABLED

methane Feb 16, 2024

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change

	#endif

	#ifndef Py_GIL_DISABLED
	#else /* Py_GIL_DISABLED */

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

DinoV reacted with thumbs up emoji

All reactions

👍 1 reaction

methane reviewed

Feb 16, 2024

View reviewed changes

Comment thread

Objects/dictobject.c Outdated

		return NULL;
		}

		#endif

methane Feb 16, 2024

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change

	#endif
	#endif /* Py_GIL_DISABLED */

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

colesbury reviewed

Feb 21, 2024

View reviewed changes

colesbury left a comment

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

A few code style comments below

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Outdated

Comment on lines +5034 to +5434

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

colesbury Feb 21, 2024

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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)) {

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Outdated

Comment on lines +4936 to +5333

		if (values == NULL)
		goto concurrent_modification;

colesbury Feb 21, 2024

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Outdated

Comment on lines +4940 to +5338

		if (i >= used)
		goto fail;

colesbury Feb 21, 2024

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same here

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Outdated

		// 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);

colesbury Feb 21, 2024

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

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

colesbury left a comment

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/dictobject.c

Comment on lines +5278 to +5279

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

colesbury Feb 22, 2024

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also here: -1 for error and 0 for success

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

DinoV reacted with thumbs up emoji

All reactions

👍 1 reaction

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

scasella mentioned this pull request

Sep 26, 2026

Free-threading: iterating an instance dict can crash during concurrent deletion #158197

Closed

Reviewers

methane

methane left review comments

colesbury

colesbury approved these changes

markshannon

Awaiting requested review from markshannon

markshannon is a code owner

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news topic-free-threading

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

colesbury left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

colesbury left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

DinoV commented Feb 6, 2024 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

colesbury left a comment •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.