GV

GeezerVison

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

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — GH-132657: Add lock-free set contains implementation by nascheme · Pull Request #132290 · python/cpython

Conversation

@nascheme

@nascheme nascheme commented Apr 8, 2025 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Member

This roughly follows what was done for dictobject to make a lock-free lookup operation. The set contains operation scales much better when used from multiple-threads. The frozenset contains performance seems unchanged (as already lock-free).

Summary of changes:

  • refactor set_lookkey() into set_do_lookup() which now takes a function pointer that does the entry comparison. This is similar to dictobject and do_lookup(). In an optimized build, the comparison function is inlined and there should be no performance cost to this.
  • change set_do_lookup to return a status separately from the entry value.
  • add set_compare_frozenset() and use if the object is a frozenset. For the free-threaded build, this avoids some overhead (locking, atomic operations, incref/decref on key)
  • use FT_ATOMIC_* macros as needed for atomic loads and stores
  • use a deferred free on the set table array, if shared (only on free-threaded build, normal build always does an immediate free)
  • for free-threaded build, use explicit for loop to zero the table, rather than memcpy().
  • when mutating the set, assign so->table to NULL while the change is a happening. Assign the real table array after the change is done.

Free-threading scaling benchmark results from the attached scripts (result for 8 cores in parallel). This is a modified version of the ftscalingbenchmark.py script.

base this PR
dict_contains 9.1x faster 9.4x faster
tuple_contains 8.0x faster 7.6x faster
list_contains 7.9x faster 7.8x faster
frozenset_contains 7.8x faster 7.8x faster
frozenset_contains_dunder 7.6x faster 7.7x faster
set_contains 2.6x slower 7.7x faster
set_contains_dunder 2.8x slower 6.1x faster
shallow_copy 1.8x faster 1.8x faster
deepcopy 4.2x faster 4.5x faster

ftscaling_set.py.txt

Separate repo containing multi-threading stress tests:
https://github.com/nascheme/python_set_stress

  • Issue: copy.copy and copy.deepcopy scale poorly with free-threading #132657

Sorry, something went wrong.

Uh oh!

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

All reactions
@nascheme
wip: lock-free set contains
ff1d60d
kumaraditya303
kumaraditya303 reviewed Apr 13, 2025
View reviewed changes
Comment thread Objects/setobject.c Resolved

Uh oh!

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

@nascheme nascheme mentioned this pull request Jul 11, 2025
gh-132657: Avoid locks and refcounts in frozenset operations #136107
Merged
nascheme added 8 commits July 11, 2025 16:52
@nascheme
Use FT_ATOMIC_* macros.
55ab02a
This makes for longer code vs using the custom LOAD_*/STORE_* macros.
However, I think this makes the code more clear.
@nascheme
Increase items and loops for set test.
7df8f02
@nascheme
Re-order some atomic store operations.
157cd60
@nascheme
Add and use set_compare_frozenset().
4c3596c
@nascheme
Merge 'origin/main' into set_lockfree_contains
6efe562
@nascheme
Fix _PyMem_FreeDelayed() calls, need size.
8ff7dbd
@nascheme
Fix frozenset contains method.
87278ef
@nascheme
Add NEWS.
b2affbf
@nascheme nascheme changed the title Add lock-free set contains implemention GH-132657: Add lock-free set contains implementation Jul 12, 2025
@bedevere-app bedevere-app Bot mentioned this pull request Jul 12, 2025
copy.copy and copy.deepcopy scale poorly with free-threading #132657
Closed
@nascheme
Re-generate clinic output.
70a1c1f
@nascheme nascheme added performance Performance or resource usage topic-free-threading 🔨 test-with-buildbots Test PR w/ buildbots; report in status section labels Jul 12, 2025
@bedevere-bot

bedevere-bot commented Jul 12, 2025

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @nascheme for commit 70a1c1f 🤖

Results will be shown at:

https://buildbot.python.org/all/#/grid?branch=refs%2Fpull%2F132290%2Fmerge

If you want to schedule another build, you need to add the 🔨 test-with-buildbots label again.

All reactions

Sorry, something went wrong.

Uh oh!

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

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jul 12, 2025
eendebakpt
eendebakpt reviewed Jul 13, 2025
View reviewed changes
Comment thread Misc/NEWS.d/next/Core_and_Builtins/2025-07-11-19-57-27.gh-issue-132657.vwDuO2.rst Resolved

Uh oh!

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

Comment thread Objects/setobject.c Resolved

Uh oh!

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

nascheme added 3 commits July 14, 2025 10:48
@nascheme
Better markup in NEWS.
64b17af
@nascheme
Remove unicode case for set_compare_frozenset.
6c339f4
@nascheme
Add multi-threaded frozenset contains test.
89f4696
@nascheme
nascheme marked this pull request as ready for review August 13, 2025 17:35
@nascheme
nascheme requested a review from rhettinger as a code owner August 13, 2025 17:35
@bedevere-app bedevere-app Bot added the awaiting core review label Aug 13, 2025
@rhettinger
rhettinger removed their request for review August 13, 2025 20:42
nascheme added 2 commits September 30, 2025 11:42
@nascheme
Merge 'origin/main' into set_lockfree_contains
406bfb3
@nascheme
Remove unused line of code, from merge.
4ffd3cd
@nascheme
nascheme requested a review from eendebakpt September 30, 2025 22:57
@nascheme
nascheme requested a review from eendebakpt September 30, 2025 22:57
@nascheme

nascheme commented Sep 30, 2025

Copy link
Copy Markdown
Member Author

Hello @eendebakpt, since you have recently worked on the setobject.c source, perhaps you are able to take another look at this. I think the free-threaded scaling improvement is significant. I've merge with the main branch and updated the benchmark results.

All reactions

Sorry, something went wrong.

Uh oh!

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

eendebakpt
eendebakpt reviewed Oct 3, 2025
View reviewed changes
Comment thread Lib/test/test_free_threading/test_set.py Outdated
NUM_LOOPS = 20

s = frozenset()
def make_set():

@eendebakpt eendebakpt Oct 3, 2025

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.

Why is the make_set here in a thread? It just assigns the same frozenset to s each time.

Maybe change make_set so that it creates a different frozenset each time?

Sorry, something went wrong.

Uh oh!

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

All reactions

@nascheme nascheme Nov 3, 2025

Copy link
Copy Markdown
Member Author

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 don't understand this comment. The make_set() binds s to a new frozenset object (at least I intend it to).

Sorry, something went wrong.

Uh oh!

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

All reactions

@eendebakpt eendebakpt Nov 3, 2025

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.

The s is indeed updated with a new frozenset, but it is a frozenset with the same elements each time. I was thinking about something like

def make_set():
            nonlocal s
            barrier.wait()
            num_elements = NUM_ITEMS
            while not done:
               num_elements = (num_elements  + 17 %) NUM_ITEMS
                s = frozenset(range(num_elements))

But what are we testing here. There is no concurrent mutation of the s, so this test is not specific to the free-threading build I think?

Sorry, something went wrong.

Uh oh!

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

All reactions

@nascheme nascheme Nov 4, 2025

Copy link
Copy Markdown
Member Author

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.

Oh yes, I'm not sure what I was thinking when writing that test. It doesn't test what I intended. I re-wrote it so that a set() is used as the key and it mutated.

Sorry, something went wrong.

Uh oh!

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

All reactions
Comment thread Objects/setobject.c
#define SET_MARK_SHARED(so) _PyObject_GC_SET_SHARED(so)

static void
ensure_shared_on_read(PySetObject *so)

@eendebakpt eendebakpt Oct 3, 2025

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.

Note to self: this is identical to the ensure_shared_on_read from dictobject.c. The SET_DICT_SHARED would correspond to SET_SET_SHARED, which is an odd name so here it is SET_MARK_SHARED.

Sorry, something went wrong.

Uh oh!

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

All reactions
Comment thread Objects/setobject.c
FT_ATOMIC_STORE_SSIZE_RELAXED(a->hash, -1);
FT_ATOMIC_STORE_SSIZE_RELAXED(b->hash, -1);
}
if (!SET_IS_SHARED(b) && SET_IS_SHARED(a)) {

@eendebakpt eendebakpt Oct 3, 2025 •
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.

set_swap_bodies is only called in two locations in this file. For both cases the second argument b is a newly created temporary which is discarded afterwards. So we could replace part (all?) of these branches with asserts. Part of the other work (e.g. copying back to b) might not be needed for the same reason.

Sorry, something went wrong.

Uh oh!

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

All reactions

@nascheme nascheme Nov 3, 2025

Copy link
Copy Markdown
Member Author

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.

That would simplify the code and be slightly faster (not sure how much it actually matters). I'll create a separate issue for that so we can benchmark it.

Sorry, something went wrong.

Uh oh!

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

eendebakpt reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
Comment thread Objects/setobject.c Resolved

Uh oh!

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

Comment thread Objects/setobject.c
{
int status;
setentry *entry;
if (PyFrozenSet_CheckExact(so)) {

@eendebakpt eendebakpt Oct 3, 2025

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.

Note: this path can be taken. set_lookkey_threadsafe is only called in set_contains_entry. The set_contains_entry is only called in _PySet_Contains. _PySet_Contains is called in set___contains___impl and in bytecodes.c _CONTAINS_OP_SET (the latter can have frozenset as input)

Sorry, something went wrong.

Uh oh!

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

All reactions
eendebakpt
eendebakpt reviewed Nov 1, 2025
View reviewed changes
Comment thread Objects/setobject.c Resolved

Uh oh!

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

eendebakpt
eendebakpt reviewed Nov 1, 2025
View reviewed changes
Comment thread Objects/setobject.c Resolved

Uh oh!

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

eendebakpt
eendebakpt reviewed Nov 1, 2025
View reviewed changes
Comment thread Objects/setobject.c
Comment on lines +117 to +121
if (table == FT_ATOMIC_LOAD_PTR_ACQUIRE(so->table) &&
startkey == FT_ATOMIC_LOAD_PTR_ACQUIRE(ep->key)) {
assert(cmp == SET_LOOKKEY_FOUND || cmp == SET_LOOKKEY_NO_MATCH);
return cmp;
}

@eendebakpt eendebakpt Nov 1, 2025

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.

What are we checking here and why? For the original code the PyObject_RichCompareBool could have changed the set, and these checks guard against this. However, in the free-threading setting a concurrent thread can change the set so after the table == FT_ATOMIC_LOAD_PTR_ACQUIRE(so->table) && startkey == FT_ATOMIC_LOAD_PTR_ACQUIRE(ep->key), but before the return cmp;. So any calling method cannot assume that when SET_LOOKKEY_FOUND is returned the key is still in the set.

Maybe adding the check help to preserve backwards compatibility in case of a mutating rich compare?

Sorry, something went wrong.

Uh oh!

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

All reactions

@nascheme nascheme Nov 3, 2025

Copy link
Copy Markdown
Member Author

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 believe the "why" is to handle PyObject_RichCompareBool() mutating the set, via the restart. I think we want to preserve that, even for the free-threaded build, since some code that running single-threaded might assume set lookups handle mutation that way.

Sorry, something went wrong.

Uh oh!

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

All reactions
eendebakpt
eendebakpt reviewed Nov 1, 2025
View reviewed changes
Comment thread Objects/setobject.c Resolved

Uh oh!

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

nascheme added 4 commits November 3, 2025 14:17
@nascheme
Minor code cleanup based on review.
2d49303
* Add comment to _PySet_Contains()
* Rename set_compare_entry() to set_compare_entry_lock_held().
* Remove unneeded `startkey == NULL` test.
@nascheme
Merge 'origin/main' into set_lockfree_contains
93c21fd
@nascheme
Improve unit tests.
a095661
The test_contains_frozenset() was not actually doing anything useful,
rewrite it.  Add test_contains_hash_mutate() which triggers unusual
code paths due to `__hash__` on the key mutating the container.
@nascheme
wip: improve test
33838a8
@eendebakpt eendebakpt mentioned this pull request Nov 7, 2025
gh-132657: optimize PySet_Contains for frozensets #141183
Merged
@nascheme
Merge branch 'origin/main' into set_lockfree_contains
235b6eb
@nascheme
nascheme enabled auto-merge (squash) December 13, 2025 09:29
@nascheme
nascheme merged commit c98182b into python:main Dec 13, 2025
46 checks passed

Uh oh!

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

@bedevere-app bedevere-app Bot removed the awaiting core review label Dec 13, 2025
@nascheme nascheme mentioned this pull request Dec 13, 2025
Minor optimization for set object, swap bodies #142659
Open
@Siyet Siyet mentioned this pull request Apr 6, 2026
gh-142659: Optimize set_swap_bodies for intersection_update #148155
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@eendebakpt eendebakpt eendebakpt left review comments
@kumaraditya303 kumaraditya303 kumaraditya303 left review comments

Uh oh!

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

Assignees

No one assigned

Labels

performance Performance or resource usage 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.

4 participants

@nascheme @bedevere-bot @eendebakpt @kumaraditya303
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 01402520 — 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.