Skip to content

Commit c98182b

Browse files
naschemenascheme
authored
gh-132657: Add lock-free set contains implementation (#132290)
This roughly follows what was done for dictobject to make a lock-free lookup operation. With this change, 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.
1 parent 3e36d37 commit c98182b

File tree

5 files changed

+452
-122
lines changed

5 files changed

+452
-122
lines changed

‎Include/internal/pycore_pyatomic_ft_wrappers.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,8 @@ extern "C" {
5757
_Py_atomic_store_uintptr_release(&value, new_value)
5858
#define FT_ATOMIC_STORE_SSIZE_RELAXED(value, new_value) \
5959
_Py_atomic_store_ssize_relaxed(&value, new_value)
60+
#define FT_ATOMIC_STORE_SSIZE_RELEASE(value, new_value) \
61+
_Py_atomic_store_ssize_release(&value, new_value)
6062
#define FT_ATOMIC_STORE_UINT8_RELAXED(value, new_value) \
6163
_Py_atomic_store_uint8_relaxed(&value, new_value)
6264
#define FT_ATOMIC_STORE_UINT16_RELAXED(value, new_value) \
@@ -140,6 +142,7 @@ extern "C" {
140142
#define FT_ATOMIC_STORE_PTR_RELEASE(value, new_value) value = new_value
141143
#define FT_ATOMIC_STORE_UINTPTR_RELEASE(value, new_value) value = new_value
142144
#define FT_ATOMIC_STORE_SSIZE_RELAXED(value, new_value) value = new_value
145+
#define FT_ATOMIC_STORE_SSIZE_RELEASE(value, new_value) value = new_value
143146
#define FT_ATOMIC_STORE_UINT8_RELAXED(value, new_value) value = new_value
144147
#define FT_ATOMIC_STORE_UINT16_RELAXED(value, new_value) value = new_value
145148
#define FT_ATOMIC_STORE_UINT32_RELAXED(value, new_value) value = new_value

‎Lib/test/test_free_threading/test_set.py‎

Lines changed: 130 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,14 @@
11
import unittest
2-
32
from threading import Thread, Barrier
4-
from unittest import TestCase
5-
63
from test.support import threading_helper
74

85

9-
@threading_helper.requires_working_threading()
10-
class TestSet(TestCase):
6+
class TestSetRepr(unittest.TestCase):
117
def test_repr_clear(self):
128
"""Test repr() of a set while another thread is calling clear()"""
139
NUM_ITERS = 10
1410
NUM_REPR_THREADS = 10
15-
barrier = Barrier(NUM_REPR_THREADS + 1)
11+
barrier = Barrier(NUM_REPR_THREADS + 1, timeout=2)
1612
s = {1, 2, 3, 4, 5, 6, 7, 8}
1713

1814
def clear_set():
@@ -37,5 +33,133 @@ def repr_set():
3733
self.assertIn(set_repr, ("set()", "{1, 2, 3, 4, 5, 6, 7, 8}"))
3834

3935

36+
class RaceTestBase:
37+
def test_contains_mutate(self):
38+
"""Test set contains operation combined with mutation."""
39+
barrier = Barrier(2, timeout=2)
40+
s = set()
41+
done = False
42+
43+
NUM_LOOPS = 1000
44+
45+
def read_set():
46+
barrier.wait()
47+
while not done:
48+
for i in range(self.SET_SIZE):
49+
item = i >> 1
50+
result = item in s
51+
52+
def mutate_set():
53+
nonlocal done
54+
barrier.wait()
55+
for i in range(NUM_LOOPS):
56+
s.clear()
57+
for j in range(self.SET_SIZE):
58+
s.add(j)
59+
for j in range(self.SET_SIZE):
60+
s.discard(j)
61+
# executes the set_swap_bodies() function
62+
s.__iand__(set(k for k in range(10, 20)))
63+
done = True
64+
65+
threads = [Thread(target=read_set), Thread(target=mutate_set)]
66+
for t in threads:
67+
t.start()
68+
for t in threads:
69+
t.join()
70+
71+
def test_contains_frozenset(self):
72+
barrier = Barrier(3, timeout=2)
73+
done = False
74+
75+
NUM_LOOPS = 1_000
76+
77+
# This mutates the key used for contains test, not the container
78+
# itself. This works because frozenset allows the key to be a set().
79+
s = set()
80+
81+
def mutate_set():
82+
barrier.wait()
83+
while not done:
84+
s.add(0)
85+
s.add(1)
86+
s.clear()
87+
88+
def read_set():
89+
nonlocal done
90+
barrier.wait()
91+
container = frozenset([frozenset([0])])
92+
self.assertTrue(set([0]) in container)
93+
for _ in range(NUM_LOOPS):
94+
# Will return True when {0} is the key and False otherwise
95+
result = s in container
96+
done = True
97+
98+
threads = [
99+
Thread(target=read_set),
100+
Thread(target=read_set),
101+
Thread(target=mutate_set),
102+
]
103+
for t in threads:
104+
t.start()
105+
for t in threads:
106+
t.join()
107+
108+
def test_contains_hash_mutate(self):
109+
"""Test set contains operation with mutating hash method."""
110+
barrier = Barrier(2, timeout=2)
111+
112+
NUM_LOOPS = 1_000
113+
SET_SIZE = self.SET_SIZE
114+
115+
s = set(range(SET_SIZE))
116+
117+
class Key:
118+
def __init__(self):
119+
self.count = 0
120+
self.value = 0
121+
122+
def __hash__(self):
123+
self.count += 1
124+
# This intends to trigger the SET_LOOKKEY_CHANGED case
125+
# of set_lookkey_threadsafe() since calling clear()
126+
# will cause the 'table' pointer to change.
127+
if self.count % 2 == 0:
128+
s.clear()
129+
else:
130+
s.update(range(SET_SIZE))
131+
return hash(self.value)
132+
133+
def __eq__(self, other):
134+
return self.value == other
135+
136+
key = Key()
137+
self.assertTrue(key in s)
138+
self.assertFalse(key in s)
139+
self.assertTrue(key in s)
140+
self.assertFalse(key in s)
141+
142+
def read_set():
143+
barrier.wait()
144+
for i in range(NUM_LOOPS):
145+
result = key in s
146+
147+
threads = [Thread(target=read_set), Thread(target=read_set)]
148+
for t in threads:
149+
t.start()
150+
for t in threads:
151+
t.join()
152+
153+
154+
@threading_helper.requires_working_threading()
155+
class SmallSetTest(RaceTestBase, unittest.TestCase):
156+
SET_SIZE = 6 # smaller than PySet_MINSIZE
157+
158+
159+
@threading_helper.requires_working_threading()
160+
class LargeSetTest(RaceTestBase, unittest.TestCase):
161+
SET_SIZE = 20 # larger than PySet_MINSIZE
162+
163+
40164
if __name__ == "__main__":
41165
unittest.main()

‎Misc/NEWS.d/next/Core_and_Builtins/2025-07-11-19-57-27.gh-issue-132657.vwDuO2.rst‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
For the free-threaded build, avoid locking the :class:`set` object for the
2+
``__contains__`` method.

‎Objects/clinic/setobject.c.h‎

Lines changed: 1 addition & 3 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

0 commit comments

Comments
 (0)