GeezerVisonThe World Wide Web, restored to 800 pixels of glory. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Home|About|Gaming cabinet|Archives|How it works|Starter sites | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GeezerVison is showing github.com — GH-132657: Add lock-free set contains implementation by nascheme · Pull Request #132290 · python/cpython Conversation
|
| 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 |
Separate repo containing multi-threading stress tests:
https://github.com/nascheme/python_set_stress
Sorry, something went wrong.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
This makes for longer code vs using the custom LOAD_*/STORE_* macros. However, I think this makes the code more clear.
|
🤖 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. |
Sorry, something went wrong.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
|
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. |
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| NUM_LOOPS = 20 | ||
|
|
||
| s = frozenset() | ||
| def make_set(): |
There was a problem 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.
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
| #define SET_MARK_SHARED(so) _PyObject_GC_SET_SHARED(so) | ||
|
|
||
| static void | ||
| ensure_shared_on_read(PySetObject *so) |
There was a problem 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.
There was an error while loading. Please reload this page.
| 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)) { |
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
| { | ||
| int status; | ||
| setentry *entry; | ||
| if (PyFrozenSet_CheckExact(so)) { |
There was a problem 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.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
| 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; | ||
| } |
There was a problem 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.
There was an error while loading. Please reload this page.
There was a problem 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.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
* Add comment to _PySet_Contains() * Rename set_compare_entry() to set_compare_entry_lock_held(). * Remove unneeded `startkey == NULL` test.
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.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
Successfully merging this pull request may close these issues.
There was an error while loading. Please reload this page.