Violation of atomicity on set difference operations

@mqbal

Hi,

We're a research group focused on testing concurrent runtimes. Our work-in-progress prototype found a behavior that happens in Jython but not in Python 2.7 or even 3.14 when using concurrent operations on different threads on the same set. The program below shows the wrong result:

import threading
import sys
from collections import *
def t0(s,res):
    s.difference_update(set([2, 3]))
def t1(s,res):
    res.append(s.difference(set([2, 3])))

def Test():
  s =  set([1, 2, 3])
  threads=[]
  res = []
  threads.append(threading.Thread(target= t0, args=(s,res)))
  threads.append(threading.Thread(target= t1, args=(s,res)))
  for i in range(0, len(threads)):
      threads[i].start()
  for i in range(0, len(threads)):
      threads[i].join()
  for i in range(0, len(res)):
      if res[i] != set([1]):
          print("found bug: " + str(res))

print("test begin...")
for i in range(0,50000):
  threads = []
  if i % 1000 == 0:
      print(i)
  for i in range(0,100):
      threads.append(threading.Thread(target= Test))
  for t in threads:
      t.start()
  for t in threads:
      t.join()
print("test Done")

Here's the output on a sample execution:

test begin...
0
found bug: [set([1, 2])]
found bug: [set([1, 2, 3])]
found bug: [set([1, 2])]
found bug: [set([1, 2, 3])]
found bug: [set([1, 3])]
found bug: [set([1, 3])]
found bug: [set([1, 2])]
found bug: [set([1, 2, 3])]
found bug: [set([1, 3])]
found bug: [set([1, 2, 3])]
found bug: [set([1, 2])]

A set starts as set([1,2,3]) and two threads t0 and t1 make a concurrent operation on it: difference_update(set([2,3])) and difference(set([2,3])), respectively.

As a result, after the execution the set should be set([1]) (which it is), and t1 should observe the same result set([1]).

It appears that, as the program above shows, t1 can observe set([1,2]), set([1,3]), and set([1,2,3]). This behavior is impossible in Python 2.X and 3.X.

We tested this program on the most recent self-contained jar file available for download.

@mqbal is part of the team, adding them so they get notified about further discussion.

@jeff5

I guess, here bites that Jython uses true multithreading while Python has pseudo multithreading (unless if specially compiled with the hot new multithreading feature activated). Then, Python's data structures are not claimed to be thread safe.
Considering that Jython is transparently advertised as using true multithreading under the hood, one might call this expected behavior.
That said, I agree that it's somewhat misleading behavior. As soon as the Python threading module is used, it's natural to expect Python-compatible behavior. However, I'm not sure how to solve this.

backing the Python data structures by threadsafe implementations would make them more expensive for single-threaded use I suppose, which is probably the vast majority of use cases
letting the threading module emulate CPython's behavior would effectively require introduction of a GIL, which is more or less a non-option since GIL-freeness has been a prominent core feature of Jython ever since

Ideas? @jeff5 ?

It's always helpful to see unexpected things. The behaviour is surprising, but is it incorrect?

The Jython implementation of set seems to be based on a high-performance, concurrent set implementation in Java, but when it finally gets around to computing a set difference it does it in a loop that without synchronisation, so it is possible for another thread to see it part way through.

As soon as the Python threading module is used, it's natural to expect Python-compatible behavior.

... although we take "Python compatible" to mean "what Python promises" not necessarily "what CPython happens to do".

Until recently, some operations in CPython were accidentally atomic, and you would know which ones by inspecting the bytecode. Further discussion always ends up in the implementation detail of CPython. This is not very helpful for Jython as it leads to authoritative-looking answers that just aren't true in general. If CPython had chosen to implement those set operations in Python code, they wouldn't be atomic.

I'd say the historic position is that a developer who wants correct behaviour from their application needs to take control of concurrency themselves. Jython limits its ambition to protecting the internal state of objects, and the interpreter itself obviously, against corruption by unmanaged concurrent access. This seems still to be the right choice because the developer does not build thread-safe software merely by assembling thread-safe objects. So we can't do this job for them. We'll try not to crash while you get your program to work.

Python has only recently begun making promises about concurrency in containers. I would feel constrained to keep those promises in Jython 3, and undocumented intentional atomicity where we recognise it in CPython, but not the accidental kind.

When I read about concurrency in Java, the precision and subtlety of the reasoning seems streets ahead of what I read in Python. I don't see the same arguments about safe publication, escape or "happens-before". I don't say the problem isn't recognised, just that justification of the solution feels a bit short. It may just be that I don't come across that level of discussion: there are a lot of very clever people in the CPython community and it's hard to believe no-one would voice these misgivings if they were poperly founded. Also, my own grasp of Java's "precision and subtlety" is tenuous, and doesn't translate to C, so I'm not going to launch into a critique.

I spend a lot of time thinking about this in a prototype Jython 3. We might have something to contribute eventually.

Thank you for the insightful discussion.

One thing to note is that we are testing all other set operations in a concurrent environment, and other operations that seem implemented similarly in a loop without synchronization do not show such behaviors. It may be the case that we simply didn't find more behaviors like this by sheer luck, but I'm not willing to say that just yet.

Thank you for pointing out the source implementation of how a set difference is computed. However, it is not immediately clear to me where/how the difference_update (or -= operator) is implemented. Is it possible that -= works in place on the original set, while other operations make a copy of the set, perform their work on the copy, and then replace the original set with the updated copy?

The backing Java code for the set Python builtin type is in
https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java
however, the relevant code for this discussion is inherited from
https://github.com/jython/jython/blob/master/src/org/python/core/BaseSet.java#L135
It's also interesting to check how the backing Java set is constructed, which happens in
https://github.com/jython/jython/blob/master/src/org/python/util/Generic.java#L131
In essence, a ConcurrentHashMap is constructed and turned into a set via Collections.newSetFromMap.
It would be convenient if the resulting set implemented the optional removeAll operation in atomic manner, but since ConcurrentHashMap does not seem to support it, I guess it's unimplemented by the resulting set.

Oh, I see.

It seems that t0 is mutating the set one element at the time with set_difference_update here: https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java#L335

So t1 might see one element removed by t0 (e.g., 2) and add it to its difference, which explains the behavior in the original report.

The code suggests that method set_symmetric_difference_update might result in a similar behavior as it also mutates the set in-place: https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java#L318

Interestingly, method set_intersection_update creates a copy of the original set with the intended contents, and then changes the set all at once with one write to field BaseSet._set: https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java#L302C16-L302C39
It seems that set_intersection_update would not result in this type of behavior being visible, as other threads either see the old contents or the new contents, and not something in-between.

What are your thoughts on implementing the set_..._update methods similarly to set_intersection_update, so the reported behavior is not possible on Jython?

Also, I noticed that BaseSet._set can be read and written by different threads and is not declared as volatile. I think I was able to convince myself that this is fine because the object it refers to is always thread-safe. Still, should it be documented?

@jeff5

The more I look into this the more I get the impression the code needs an overall overhaul, but it's probably not worth the effort for Jython 2. Perhaps if the the new code could be reused for Jython 3...

E.g. the implementation of set intersection, which is used by __and__ and set_intersection_update https://github.com/jython/jython/blob/master/src/org/python/core/BaseSet.java#L403 should rather be implemented via retainAll. At least if the argument is a PySet.

I dislike the concept of changing the backend variable. IMO in-place operations should translate to in-place operations on the backend. Recreating the backend might cause unexpected behavior and I would say the methods that do it should be adjusted to keep the backend in place rather than bringing this misbehavior to other methods.

The reason is that a user may explicitly provide a backend on PySet construction via https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java#L38.
Assume someone uses a wrapper around some set implementation to monitor or log set access, perhaps for debugging or fancy integration of some database or whatever. The provided backend must not be unexpectedly replaced or this use case would be compromised. In a sense that would violate the contract of in-place operations.

That said, it appears like since Java 8, the preferred way to create a "ConcurrentHashSet" is ConcurrentHashMap.newKeySet rather than newSetFromMap.
newKeySet produces a ConcurrentHashMap.KeySetView which does implement removeAll by inheriting it from ConcurrentHashMap.CollectionView though.
Assuming, since it's in ConcurrentHashMap, the removeAll implementation is atomic, one could implement the in-place difference by creating a union of the given sets and then call on the backend removeAll with that union. Ideally, the union would somehow be just a union-view.

@jeff5 how is this working or planned for Jython 3? If we would tackle this, it would be most efficient to tackle it for both together and reuse code as far as possible.

I haven't ported set. I have ported list, however, which requires the same consideration. I'm not sure we could pull off any actual concurrency, so the backing list is simple.

You can tell I was thinking about it this aspect, even before free threading.

I see, list is a different can of worms. I just skimmed through that code... is there any method that changes the initially created backend? Perhaps it would be safer and cleaner if PyList wouldn't take care of the synchronization but instead the backend is initially wrapped through Collections.synchronizedList.
I think it would be good to establish a clear synchronization/concurrency policy for all datastructure types.
E.g.

PyX classes are thin wrappers around the backend which do not add concurrency/thread safety
thread safety has to be built into the backend and by default thread-safe backends are used
the backend is not changed, in-place operations modify the backend in-place

This was, to some extent, a sketch exploring correctness of containers in general. And set is a different can, but still a container. We clearly don't achieve (or promise) atomicity in all operations, but with Python making specific cases of accidental atomicity into features, we should do the same, at least for 3.

It is worth looking at these promises in PEP 703. I understand enough to think they may be wrong that "Some simple operations can be implemented directly with atomic accesses and do not need locks because they only access a single field." This would not be true under the Java Memory Model.

I think you are mostly right that another route to correctness is via the synchronized(List|Set|Map)wrapper, rather than our class being that wrapper. Being the wrapper means we get to add methods we need without the extra layer. I believe I considered using a synchronised list in Jython 3 PyList. The problem was to synchronise two containers when you'd like that field to be private.

I've done that double lock somewhere, the need for which PEP 703 also refers to, but I'm surprised it's not in this class.

One might be motivated to a pluggable backend because a particular implementation has a more desirable compromise of characteristics than our default choice, but it still has to be a Python set. This is quite likely to include concurrency, in which case, using it through a synchronising wrapper defeats the object, but I cannot see how to keep the promise Python makes without synchronisation if the underlying container does not implement the behaviour. We cannot synchronise just the extra methods. I do not know the best answer here.

I cannot see how to keep the promise Python makes without synchronisation if the underlying container does not implement the behaviour

First of all, only the default choice has to implement the behavior. As soon as a user-provided container is used, it's the user's responsibility and we just have to make that contract transparent. Perhaps the user only needs a single thread and wants a faster backend for that case. The synchronized keyword has an immense overhead for method calls an by having it on PyList level it would be impossible to bypass that overhead by plugging an alternative backend.
But I guess you refer to the challenge of providing the required behavior even within a default backend. For the case of PySet, I think everything can be implemented based on assumingly atomic removeAll and retainAll methods. Otherwise another layer would be needed to add missing methods in synchronized manner.

As soon as a user-provided container is used, it's the user's responsibility and we just have to make that contract transparent.

I think this is a sensible idea, but I can see a danger in having only some containers meet their contract, when handed to code that may not know this. I still hold, however, that serious concurrency in an application requires the developer to apply their own locks.

The synchronized keyword has an immense overhead

An uncontended lock is said to be quite cheap (Java Concurrency in Practice, Peierls, Goetz, et al.). It's only when a thread has to wait that things start to go south.

The concurrent containers are there for a reason, however, so users should have access to them, and probably they should appear as Python sets. Notice how carefully this is stated (package docs for java.util.concurrent, my emphasis): "Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread." Anything that depends on multiple elements, like size(), or an iterator, is very guarded in its promises.

I noticed that BaseSet._set can be read and written by different threads

Through the _update method? I think this is questionable design. I think creating a set with a specified backing type is ok, but this apparently invites us to swap the implementation on the fly.

An uncontended lock is said to be quite cheap (Java Concurrency in Practice, Peierls, Goetz, et al.). It's only when a thread has to wait that things start to go south.

The JVM (Hotspot and OpenJDK) uses biased locks, and acquiring an uncontended lock (on an object without a hash code) is as cheap as one CAS. If no other CPU has this object on its cache, I believe the hardware can make this as cheap as a regular write. There may be better resources, but this is a good explainer and starting point: https://dl.acm.org/doi/10.1145/582419.582433

Through the _update method?

This particular line, apologies if I misunderstood the code base: https://github.com/jython/jython/blob/master/src/org/python/core/PySet.java#L312

You haven't misunderstood, I have. I had looked at

jython/src/org/python/core/BaseSet.java

Lines 18 to 29 in 3760bfb

    
           protected BaseSet(PyType type, Set<PyObject> set) { 
        
               super(type); 
        
               _set = set; 
        
           } 
        
           public Set<PyObject> getSet() { 
        
               return _set; 
        
           } 
        
           protected void _update(PyObject data) { 
        
               _update(_set, data); 
        
           }

and misremembered what _update does.

I think this is a sensible idea, but I can see a danger in having only some containers meet their contract, when handed to code that may not know this. I still hold, however, that serious concurrency in an application requires the developer to apply their own locks.

Keeping synchronization out of the container gives the developers the most freedom to apply their own locks. Changing synchronization behavior to more or less strictness would be possible by switching the backend, but you cannot remove synchronization boundaries established by the container. E.g. some days ago someone requested to add Eclipse Collections to APIdia, which pointed me to this library (which we might consider as alternative data structure backend btw since it promises superior memory efficiency w.r.t. JDK's in-house implementations). To reduce locking, I found especially interesting MultiReaderList and MultiReaderSet. Unfortunately, their docs are not exactly verbose about the behavior but it sounds like locking only prevents concurrent write access, not read access. I'm not saying that we should adopt this lib; just that users should be enabled to switch the backend to these types of implementations on their own account. That would be difficult or impossible if the container dictates synchronization.

I dipped a toe into a discussion of the synchronisation of list. https://discuss.python.org/t/bad-nogil-behaviour-or-something-else-is-broken/103977, which led me (indirectly) to my first mention of happens-before in this context.

Thanks for the update.

Might be worthwile looking at some behaviors we reported to the CPython no-GIL team: https://github.com/python/cpython/issues?q=is%3Aissue%20author%3Aluisggpina

As with the issue here, these behaviors are not possible when using CPython with GIL.

Clearly your programs to reproduce these bugs are quite stylised, but someone seeing them for the first time might need a few comments to get started. A check ...

Talking myself through python/cpython#129619 ...

You create 100 Test threads, and start them approximately simultaneously.
Each Test thread creates two Racer threads and a barrier of size 2.
When you call a test function (t0, t1 here), the tests call barrier.wait, so that t0 and t1 do their next action in a race.
You do all of the above 50000 times.

Now, items 4 and 1 are just about doing the test lots of times, and concurrently to save wallclock time, but none of these threads are contending for data (except maybe data in the runtime we can't see). The only race we are testing is at step 3, set up by step 2, between two threads in (potentially) different methods of the object.

I think this is nice (IIUC): I've been trying to torture (in Java) aspects of a prototype Jython 3 runtime. I'm using a barrier to start the race, but I hadn't thought of passing it into the test actions.

The response of core developers is interesting. They are clearly deciding as they go along what actions should be atomic, with a rule-of-thumb that multi-element operations would not be. PEP 703 gives us a hint but apparently a definitive statement is to come.

In this one python/cpython#129519 (comment) (unresolved), Peter Bierma questions the assertion in PEP 703 that the length/size of a container does not need to be within the lock as it can be accessed atomically.

@alirs2

items 4 and 1 are just about doing the test lots of times, and concurrently to save wallclock time

Also, to add pressure to the underlying memory system. Research finds that adding memory pressure causes the hardware to show "weird" memory behaviors more often (or at all). Here's an example of such a paper for GPUs, CPUs show the same trends: https://dl.acm.org/doi/10.1145/3597926.3598095

I'm using a barrier to start the race, but I hadn't thought of passing it into the test actions.

The barrier here aligns all threads so that it is more likely that two threads are actually attempting to manipulate the same data at the same time, thus uncovering potential bugs.

We're preparing a paper to submit to an academic conference about how to make sense of all of these behaviors in Python implementations that do not rely on the GIL. I can share it privately when I have something worth your time reading it, and I can drop it on arxiv once we do submit it.

In the meantime, I can point you to @alirs2's MS thesis that does something similar but focusing on the perceived memory model, not on the concurrent semantics of Python's data-structures: https://indigo.uic.edu/articles/thesis/Litmus_Testing_CPython_Without_the_Global_Interpreter_Lock/29338727?file=55442684

In the meantime, I can point you to @alirs2's MS thesis that does something similar but focusing on the perceived memory model, not on the concurrent semantics of Python's data-structures: https://indigo.uic.edu/articles/thesis/Litmus_Testing_CPython_Without_the_Global_Interpreter_Lock/29338727?file=55442684

Fascinating read. Thanks for posting. I have seen a few of those litmus test patterns in other writing, but not so many systematised in one place. I also followed a few references. It is clear one must work quite hard to induce the sort of failures being sought. I'll have to up my game.

Navigation Menu

Repository navigation

Violation of atomicity on set difference operations #396

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	protected BaseSet(PyType type, Set<PyObject> set) {
	super(type);
	_set = set;
	}

	public Set<PyObject> getSet() {
	return _set;
	}

	protected void _update(PyObject data) {
	_update(_set, data);
	}

Violation of atomicity on set difference operations #396

Description

Activity

Stewori commented on Aug 28, 2025

jeff5 commented on Aug 29, 2025

luisggpina commented on Aug 29, 2025

Stewori commented on Aug 29, 2025

luisggpina commented on Aug 29, 2025

Stewori commented on Aug 30, 2025

jeff5 commented on Aug 30, 2025

Stewori commented on Aug 30, 2025

jeff5 commented on Aug 31, 2025

Stewori commented on Aug 31, 2025

jeff5 commented on Sep 4, 2025

jeff5 commented on Sep 4, 2025

luisggpina commented on Sep 4, 2025

jeff5 commented on Sep 5, 2025

Stewori commented on Sep 5, 2025

jeff5 commented on Sep 30, 2025

luisggpina commented on Sep 30, 2025

jeff5 commented on Oct 4, 2025

luisggpina commented on Oct 6, 2025

jeff5 commented on Oct 11, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions