Bug report
Summary
In a free-threaded build, concurrent calls to set.intersection_update() on the same set can produce a non-deterministic result, which I did not see it with -X gil=1. One successful intersection can be lost when another thread later computes and assigns a result calculated from an older target state. The result from set.intersection_update() differs from s &= other (s.__iand__(other)), although both have the same single-threaded result.
Reproducer
AI Disclosure: This code is generated by Codex, but I have already verified it.
"""Run with: ./python.exe -X gil=0 this_file.py or ./python.exe -X gil=1 this_file.py"""
from threading import Barrier, Thread
N = 20_000
TRIES = 60
# Every serial sequence of intersections must leave only range(N).
sources = [set(range(4 * N)), set(range(3 * N)), set(range(2 * N)), set(range(N))]
initial = set(range(5 * N))
expected = initial.intersection(*sources)
def run(name, operation):
for attempt in range(TRIES):
target = set(initial)
start = Barrier(len(sources))
def worker(source):
start.wait()
operation(target, source)
threads = [Thread(target=worker, args=(source,)) for source in sources]
for thread in threads:
thread.start()
for thread in threads:
thread.join()
if target != expected:
print(f"{name}: WRONG on attempt {attempt}")
print(f" got {len(target)} items")
print(f" expected {len(expected)} items")
return
print(f"{name}: matched expected result in {TRIES} attempts")
run("intersection_update", lambda s, other: s.intersection_update(other))
run("&=", lambda s, other: s.__iand__(other))One observed result with -X gil=0:
intersection_update: WRONG on attempt 0
got 60000 items
expected 20000 items
&=: matched expected result in 60 attempts
A result with -X gil=1:
intersection_update: matched expected result in 60 attempts
&=: matched expected result in 60 attempts
Expected behavior
For sets A through D, every serial order must produce:
initial.intersection(A, B, C, D)
In this reproducer, it is set(range(N)), with 20,000 items.
Why the result cannot be serialized
Let me simplify this example to have only two sets. When there are an initial set and two operand sets, the valid serial executions are as follows, where both include both intersections.
(initial & A) & B
(initial & B) & A
However, how the current set.intersection_update() works can be visualized (in a simple way) as follows.
tmp_a = original_target & A
tmp_b = original_target & B
target = tmp_a
target = tmp_b
The last replacement wins. Therefore, it can leave only original_target & B, or original_target & A depending on an execution order, which is not equivalent to either serial ordering.
A Possible Cause
set.intersection_update() causes set_intersection_update_multi_impl() in Objects/setobject.c. This method first calculates a temporary result:
tmp = set_intersection_multi_impl(so, others, others_length);
Then, it separately takes the target's critical section and swaps the whole target body:
Py_BEGIN_CRITICAL_SECTION(so);
set_swap_bodies(so, (PySetObject *)tmp);
Py_END_CRITICAL_SECTION();
Another intersection_update() in another thread can calculate its temporary result after the first calculation has finished, but before the first swap occurs. Its later swap can overwrite the first update.
On the contrary, __iand__ reaches set_iand(), which holds a critical section across both calculation and assignment.
Py_BEGIN_CRITICAL_SECTION2(so, other);
result = set_intersection_update(so, other);
Py_END_CRITICAL_SECTION2();
Question
Is this behavior expected? Is set.intersection_update() intended to be linearizable with respect to concurrent updates of the same target set, given that its operands are sets that are not modified concurrently?
I would be interested in preparing a fix if this is confirmed to be a bug.
CPython versions tested on:
CPython main branch
Operating systems tested on:
Linux, Windows
Linked PRs
Bug report
Summary
In a free-threaded build, concurrent calls to
set.intersection_update()on the same set can produce a non-deterministic result, which I did not see it with-X gil=1. One successful intersection can be lost when another thread later computes and assigns a result calculated from an older target state. The result fromset.intersection_update()differs froms &= other(s.__iand__(other)), although both have the same single-threaded result.Reproducer
AI Disclosure: This code is generated by Codex, but I have already verified it.
One observed result with
-X gil=0:A result with
-X gil=1:Expected behavior
For sets
AthroughD, every serial order must produce:In this reproducer, it is
set(range(N)), with 20,000 items.Why the result cannot be serialized
Let me simplify this example to have only two sets. When there are an initial set and two operand sets, the valid serial executions are as follows, where both include both intersections.
However, how the current
set.intersection_update()works can be visualized (in a simple way) as follows.The last replacement wins. Therefore, it can leave only
original_target & B, ororiginal_target & Adepending on an execution order, which is not equivalent to either serial ordering.A Possible Cause
set.intersection_update()causesset_intersection_update_multi_impl()inObjects/setobject.c. This method first calculates a temporary result:Then, it separately takes the target's critical section and swaps the whole target body:
Another
intersection_update()in another thread can calculate its temporary result after the first calculation has finished, but before the first swap occurs. Its later swap can overwrite the first update.On the contrary,
__iand__reachesset_iand(), which holds a critical section across both calculation and assignment.Question
Is this behavior expected? Is
set.intersection_update()intended to be linearizable with respect to concurrent updates of the same target set, given that its operands are sets that are not modified concurrently?I would be interested in preparing a fix if this is confirmed to be a bug.
CPython versions tested on:
CPython main branch
Operating systems tested on:
Linux, Windows
Linked PRs