Picture Thread A reading the value of X=0, then the Python scheduler preempts the thread. Then Thread B fetches and increments X three times. X is now 3. Thread A then runs again, and increments the value of X it had read previously, (0+1), then writes 1 to X.
The memory location just went: 0,1,2,3,1
I'm working on a series for my blog called Temporal Fuzzing that simulates these edge cases in a virtual machine. It is often very hard to predict the total set of possible behaviour given random interleavings.
(Edit: Apologies for misreading; our definitions are indeed similar, continued below)
In safe Rust data races are not possible and yet it is still possible for a Rust program to exhibit the behavior in your article, because your article is not an example of a data race but rather a race condition. Note that in the source you reference, it explicitly states that while data races are protected, race conditions are not.
The scenario I gave, where performing an operation such as "x = x + 1" can result in x decreasing in value can only be caused by an overflow, or a data race. No interpretation of a Python or safe Rust program will ever produce a decreasing value of x when evaluating "x = x + 1" (ignoring Rust's overflow behavior) since data races are not possible. In Java or C++, since data races are possible it is also possible that "x = x + 1" produces a decreasing value of x (that is not due to overflow).
Finally here is a good article that lays out the differences between data races and race conditions:
https://blog.regehr.org/archives/490
[1] https://doc.rust-lang.org/nomicon/races.html
[2] https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.ht...
The Python example has two concurrent accesses of the same memory (the global counter) where one of them is a write. That seems to meet the definition.
We're also seeing the telltale symptoms of a data race. Note that we don't need to see slicing to qualify as a data race; as plenty cache-line-aligned data races don't exhibit slicing (not implying you were claiming this, just mentioning it for anyone curious).
The Rustonomicon definition also adds "they are unsynchronized", perhaps that's the part we disagree on.
I see this code as unsynchronized; there is no mutex or atomic increment happening around this operation. One could reasonably disagree, depending on what level they're looking at: statement-level, instruction-level, opcode-level, assembly level, uop level, or a higher "logical" level.
Either way, the point of the article is to help debunk a common misperception that the GIL helps users with their concurrency in some way.
>>> import dis
>>> def increment_counter():
... counter = counter + 1
>>> dis.dis(increment_counter)
2 0 LOAD_FAST 0 (counter)
2 LOAD_CONST 1 (1)
4 BINARY_ADD
6 STORE_FAST 0 (counter)
8 LOAD_CONST 0 (None)
10 RETURN_VALUE
A data race looks like LOAD_FAST from thread 1 begins
STORE_FAST from thread 2 begins
memory is partially overwritten
LOAD_FAST from thread 1 finishes (got partially written garbage)
STORE_FAST from thread 2 finishes
This is not a data race: LOAD_FAST from thread 1
LOAD_FAST from thread 2
STORE_FAST from thread 1
STORE_FAST from thread 2
There's no LOAD_FAST + STORE_FAST "transaction" here, GIL has no such guarantee.Edit: You also need to realize that in Python, that BINARY_ADD can be anything:
import time
class SlowCounter(int):
def __add__(self, other):
time.sleep(1)
return SlowCounter(super().__add__(other))
counter = SlowCounter()
counter += 1
The GIL isn't going to wait around for the __add__.Ah, but no, there is never concurrent access to that memory address, that's what the GIL prevents. The loads/stores to that memory address happen only while the GIL is held. The "concurrency" being used here is much more narrow than the dictionary definition of concurrency and the way it is usually discussed in the Python world.
That said, reads and writes can be atomic and still subject to race conditions which is what your example demonstrates. All your article shows is that data race freedom does not imply race condition freedom and this true not only of Python but of all programming languages.
That's what the C++ standard says, linked from the wikipedia article you linked. I realize that C++ may not be completely applicable to Python, but this fits my prior understanding of the topic.
Since there's no formal semantics to consult here, no actual alternate definition of concurrency, and the definition of data race fits, I can't say that the article is incorrect.
This is going long and I need to get dinner, but thank you for the great discussion!
"The parts of this definition relating to signal handlers are idiosyncratic to C++ and are not typical of definitions of data race."
Now we can definitely go into the nature of signal handlers in C++, but suffice it to say signal handlers are not considered to be executed from within the same thread as the main program. A signal handler is executed from within a special execution context that is independent of the rest of the program and whose behavior is distinct from typical threads. Suffice to say, other than specific idiosyncrasies, a signal handler is treated as if it were a separate thread of execution (even though technically an implementation does not have to actually spawn a separate thread for a signal handler).
In Python at this level, we don't even have a notion of a memory address. In fact, the memory address of where the integer itself is stored is going to be different, since integers in Python are boxed and immutable. Even if that weren't the case and these were direct memory accesses as you'd see in a lower level language, this would still not be able to introduce a data race, as the GIL prevents these two threads from ever actually running at the same time (while executing pure-python code that does not otherwise release the GIL. A poorly written extension or buggy code outside the GIL could cause data races, but that's a bit of a rabbithole). They'll hop back and forth as they acquire/release the GIL, and so the memory accesses can never race.
The Wikipedia article quotes part of the C++ standard which defines "potentially concurrent", but even with that definition, the article's understanding of data race stands, because these two operations are indeed unsequenced w.r.t. each other.
I don't see a reason to depart from the usual understanding of "concurrent", but I'm open to being convinced!
No code that runs under the GIL is ever run concurrently. All of the code in the example holds the GIL, there's never any concurrency in your article! With no concurrency, there can be no data race.
(Edited in response to your edit)
For example it's possible on a single core CPU to have one thread operate on the higher bits of a 32-bit memory location then yield to second thread that operates on the lower 32-bits of the same memory location so that the end result is a clobbered write. At no point do the two threads run simultaneously and yet this would still be an example of a data race.
Python's GIL makes such an access impossible on any platform it runs on.
I'd be interested to see a concrete example of how it could actually happen on a real currently-deployed system. (I'm not saying people should normally write such code, but things do need to ground out in a concrete machine model at some point, even if it's just for the sake of implementing higher level language semantics.)
(Edit: replied to you with similar comment in sibling thread...)
A data race occurs when two memory accesses race, and at least one of them is a write. In C/C++, data races using non-atomic accessed are undefined behavior, and that's why those can be very bad and you definitely want to avoid those.
You can also have a data race using atomic accesses, but there the behavior (ignoring some of the issues with the C/C++ memory model) is well-defined, and therefore it is not by definition incorrect.
I would say that the Python code in the post does have a data race (since it has unsynchronized accesses to a variable, and at least one is a write). But the behavior of that code is still precisely defined (though non-deterministic), since Python just guarantees that you will see some interleaving of the individual atomic steps of each of the threads due to the GIL). Hence the data race in Python is not undefined behavior as in C/C++, and hence it does not have the same negative connotations. Basically, Python variable accesses behave like sequentially consistent atomic reads/writes in C/C++.
Note that data races in C/C++ being undefined behavior is in large part due to compiler optimizations and preventing accesses from being reordered by the compiler or the CPU. If you're working with 32-bit (or 64-bit) cacheline aligned memory accesses, then "clobbering" or "tearing" of memory accesses is not likely to be affect you, but your code can still be broken by reordering in the compiler or the CPU (either due to instruction reordering or caches/bus communication). Hence if you have a data race on say an int variable, you probably will never see 65536 there if you didn't write that value there, but you might see older/newer values than you would expect.
In languages were data races are possible you can have every thread only ever increment x, and yet x's value will decrease due to a data race.
Python's GIL will protect against data races, meaning that certain classes of bugs where a specific memory location takes on a completely arbitrary value will never be observed from a Python program.
x starts as 0.
Thread A evaluates x + 1, getting 1.
Thread B executes the full statement 100 times, setting x to 100.
Thread A finishes executing the statement, setting x to 1.
So x decreased from 100 to 1.
But I agree with you that this is a race condition, not a data race.
That would be a very strange language, or a very strange machine.
In particular integer reads and writes are atomic (though not necessarily well ordered) on x86, arm, etc, so you'd be hard pressed to get a C compiler to emit code that tears the reads or writes in a way that would lead to integer decrements.
You can't dereference a non-aligned pointer in portable C. It will bus error on certain architectures (including some arm variants).
(I've written plenty of code that relies on unaligned reads, and also that relies on non-torn reads/writes, just not at the same time, and never when portability was a concern.)
If you wish to discuss x86 or ARM, well a data race can occur in a C program through the use of SIMD instructions or writing through an unaligned pointer. If you want to pick an architecture that does not allow unaligned accesses, sure we can discuss the PowerPC 500 series where unaligned accesses are a bus error, but then reads and writes of 32 bit values are not atomic and hence can produce data races.
We can't mix properties of one architecture with properties of another architecture and also discuss portable C. Any consideration of data races or undefined behavior in general must be specific to a particular architecture and we must apply the rules of any given architecture consistently.
The bug is due to the fact that an operation such as "x = x + 1" is not atomic, it can be interrupted at several points to allow for another thread to read and write to x. Each individual read and write is atomic, but the order of such reads/writes is non-deterministic. A data race would be if the memory location that x represents is written to simultaneously as it's being read from which could result in a form of clobbering.
To make this more concrete, given the following code:
print(x)
x = x + 1
print(x)
In Python it will always be the case that the first print statement prints a number that is less than the second print statement, guaranteed. However if data races were possible, it would be possible that the second print statement displays a number less than the first print statement. For example the first print statement could print 65535, and the second print statement could print out 0. This can happen if for example, two simultaneous additions occur where one addition is in the process of clearing out the lower bits at the same time that another thread's addition is in the process of clearing out the higher bits so that at the completion of both threads, x's bits are reset to 0. Such a scenario is not possible in Python.
Whether one considers data races to be race conditions is a matter of debate, but at any rate no one familiar with the difference between the two should consider the behavior in this article to be a data race.