Interestingly if you change the line to `counter += 1` it still has the race condition. I'm not sure how the byte code is different for the two options but it doesn't make a difference, I had hoped it would.
In general, "+=" probably needs to be non-atomic to support "__add__" overloading; Python wouldn't be able to call arbitrary "__add__" methods in a way that could guarantee atomicity.
A bit more detail: there is an atomic addition bytecode, called INPLACE_ADD, which is why something like “a_list += [1]” is actually atomic. The problem is that integers are immutable, so “counter += 1” involves a (non-atomic) load and store of counter, and that’s where the race is.
Hypothetically, if Python had a built-in mutable integer type, the increment could be made atomic.
Python’s GIL does exactly nothing to prevent data races (or any other concurrency issues); it merely protects the runtime from memory corruption stemming from concurrency.
Obviously, the fundamental issue with concurrency is programmer’s intent. This statement:
x += 1; y -= 1
can be interpreted in two ways:
atomic {
x += 1
y -= 1
}
or
atomic { x += 1 }
atomic { y -= 1 }
The best the compiler can do would be to alert the programmer of the ambiguity; I know of no compiler that does that.
The article isn't trying to claim either interpretation, it's just using it as an example to show that the GIL doesn't actually help protect users from concurrency problems. You'd be surprised how many people think that!
I used to think that it did as well, but then my C/Java brain kicked in and realized that couldn't be correct. I wrote this article to help others see it in action.
I did too. I even wrote multithreaded test programs to see if it was true: they would always give me consistent results on Python and Ruby but on Java and C data got clobbered as expected.
for example: "move money from one bank account to another bank account"
essentially the same operations in the same order, that need to be isolated (i.e. transactional / atomic) from concurrent threads performing the same operations.
> Python’s GIL does exactly nothing to prevent data races (or any other concurrency issues)
That sounds good and authoritative. Unfortunately the Python documentation itself is silent on the subject. And more importantly the Python community is filled with people who believe exactly the opposite.
It's a real hole. And the only solution right now is to tell everyone to avoid threads. The Python world simply isn't prepared for them.
FWIW: I'm one of a handful of people who have found and fixed race conditions in python scripts. And it was largely because my background is in racey C code and my eyes were primed to see it. And even then, I genuinely thought (based on incorrect advice like the above) that this sort of thing was impossible and kept looking before trying the obvious synchronization solution. And it was only then that I realized what a mess concurrency is in the mind of the modern python developer.
The feature just makes it run identically to the last run. It's useful for reproducing bugs; if you encounter a bug, just start the program in "replay" mode, supply the recording from the last run, and fire up the debugger, and watch as the bug is reproduced perfectly.
It's kind of like a time-traveling debugger, but with stronger guarantees.
I'm particularly excited about combining this with concurrency, we'll never have to spend hours hunting down mysterious race conditions ever again!
The GIL is for internal python state. Not for atomic preservation of python data types.
I learned very early on that python threads should be treated like C threads, and therefore should be avoided. Also there really isn't a performance gain to using threads (other than maybe waiting for IO completion).
If you use C code that releases the GIL, you can see big speed ups with threads. A lot of C extension modules will drop the GIL. For instance, NumPy drops the GIL for many array operations, so threads can significantly speed up numeric workloads.
I'm unable to reproduce. Increasing the number of iterations to `1000000` and using a temporary variable `c = counter + 1; counter = c` doesn't help either.
Why ? I'm on Linux, using Python 3.10. It's only happening using Python2.7.
Python 2.x is unsupported and anyone using it should operate on the assumption that whatever bug its got is final unless they're the one who is going to fix it.
> Ironically, CPython 3.10 has gone the opposite direction and made thread scheduling much more deterministic. It now only releases the GIL on backwards edges in the byte code The example in the article always prints 40000000 in CPython 3.10! I expect this will ultimately make Python code less reliable in the future as many programs will accidentally depend on this behavior.
If only one thread is reading or writing the counter at a time, and holds the GIL while doing so, it's not a data race, but a mutex which fails to ensure the atomicity of the read-modify-write operation:
That's a logical race, not a data race, right? Technically, "counter = counter + 1" accesses counter twice (once to read and once to write).
The fact that "counter" gets modified between the read and the write doesn't imply that multiple accesses were happening simultaneously; it just means that accesses from different threads were getting interleaved. The GIL would only prevent the former but not the latter, since a thread can give up the GIL at any point between operations.
it's kind of the canonical example of a data race. down in machine code land, the instructions that implement synchronization primitives are typically of the form "check prior existing value and change the value in one atomic step."
and yes, as everyone is saying, the gil keeps the python interpreter/runtime from ending up in an inconsistent state... its behavior should not be depended on by user programs. if you need to increment a counter, use a lock, or a counter that explicitly states that it's a thread safe atomic counter on the tin.
The semantic operation is increment. It being read, add, write is an implementation detail. The increments happen simultaneously, meeting the definition for 'data race' according to Padua, which is the definition most people would use.
That's an implementation detail based on a particular architecture. A different architecture could have an atomic increment operation if it wanted to, and Python could use it for this syntax.
In Python though, there's really only one architecture. Yes there's PyPy and such, but CPython and it's bytecode is both the official implementation and official spec of Python. Maybe the underlying hardware has those operations, but the Python VM does not.
Because that's what the user wrote. You can reason about the operation in terms of smaller operations (such as read, add, store) but not more coarse operations, because the user could have just written the single operation.
Consider the situation "counter = counter + get_value()". That also can be reasoned about in terms of smaller operations, but not more coarse operations, because the user could have just written the single operation.
We wouldn't expect this to be atomic, because the get_value() function could do tons of things, and we don't expect all that to be atomic. It doesn't make sense to call something atomic just because the user wrote it.
The article mixes up data races and race conditions, which is understandable since it's a common mistake. Race conditions are a fairly general class of bugs involving some non-deterministic sequence of operations, but a data race is a very specific scenario (within a given memory model) that occurs when there are two or more concurrent accesses to a memory location and at least one of them is a write. Ignoring C extensions, the GIL absolutely does protect against this and data races are not possible in Python.
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.
Everyone seems to have their own definition of data race! The article uses the one from the Rustonomicon, and by that definition, the Python example does appear to have a data race.
(Edit: Apologies for misreading; our definitions are indeed similar, continued below)
The definition I gave is exactly the one given by Rust [1], by C++ [2], by Java [3] and the one found on Wikipedia [4].
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:
Thanks for the clarification. It's interesting that we see the same definition so differently.
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.
The GIL helps users protect against data races, it does not protect against race conditions. In Python, due to the GIL, it is not possible to concurrently access a memory location and hence there is no concurrent access to x. There are concurrent threads of execution, but they are interrupted either before accessing x, or after accessing x. At no point is a thread of execution interrupted right in the middle of an access to x.
These things are running concurrently with each other though. Concurrent operations can happen one after the other, and Python's threads are more about concurrency than parallelism. If these definitions instead mentioned "simultaneous" or "in parallel", I could agree with your belief.
There need not be any parallelism or simultaneity for a data race to occur. What matters is that writes occur concurrently with another read/write, not whether they occur in parallel.
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.
> 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.
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.
There's plenty of reading in the set of links in the grandparent, so maybe I can just quickly clarify. When we speak of concurrency and data races, we're speaking about concurrent accesses to a particular memory location, where concurrent means "at the same or overlapping times".
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.
I'm not seeing anything in the links suggesting that there's a special different "concurrency" than the one commonly used in programming discussion.
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.
The precise definition of a concurrent access is with respect to a programming language's memory model. Now Python does not provide formal semantics for its memory model (neither does Rust for that matter or C++ prior to C++11), instead Python is defined by its reference implementation where individual reads and writes are protected by the GIL. So while threads in Python run concurrently as in individual operations interleave with one another, there is never a concurrent read or write operation. Every individual operation performed by the Python bytecode interpreter is protected by the GIL, ie. atomic.
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.
Two operations can be concurrent, even if they are run on the same thread, as long as they are unsequenced, in other words, there is nothing making one happen before the other.
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!
You have misread what C++/Wikipedia says and are hence incorrect. The Wikipedia article says that actions are potentially concurrent if (they run from two different threads) OR (they are unsequenced AND one operation is performed by a signal handler). I have added the parenthesis to group together the logical clauses. Your omission of the requirement that the operation be performed from within a signal handler is significant and Wikipedia states the following about it:
"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).
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__.
I don't think that program can cause the value to decrease below its initial value with any current C compiler on any modern architecture. (Ignoring overflow, and also cases where the integer is misaligned. Misaligned accesses are a bus error on some architectures, so it's so far into undefined behavior that the race isn't very interesting in my book.)
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...)
I’m not sure if you can read a corrupted value from a word-sized (or smaller) int with a modern C compiler, but Python int is arbitrary precision. You can easily corrupt a gmp int with concurrent read & write.
Your statement about your sample code is incorrect - just confirmed it for myself (cpython 3.8.3 is what was handy). Just add those print statements to the example in the article (before/after labels make analysis easier) and also add a set of threads that just do 'x = 0'.
If you have a thread decrease the value of x then of course it's possible for x to decrease in value. The point is if you have a bunch of threads where every thread only ever increases the value of x like in the article then in Python it will never be the case that the value of x decreases.
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.
> 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.
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.
Your statement is too strong and comes with important caveats. Only certain aligned memory accesses to non-floating point data types are atomic. Floating point values, unaligned accesses and even integer operations via SIMD instructions are not atomic on the platforms you list. You can absolutely produce an unaligned pointer in C, or use SIMD to increment an integer value (in conjunction with other values) in which case there is no guarantee of atomicity and hence the potential for data to be clobbered if it's not protected by a synchronization primitive.
But (other than floating point, which is surprising, if true for word and smaller values on machines that actually have floating point units), all of those examples are either non-portable assembly code (SIMD) or directly violate the C memory model (unaligned access).
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.)
We're jumping all over the place I'm afraid. If you're talking about writing standard/portable C then data races are undefined behavior and hence there is no portable manner in which a data race can be observed. A C compiler is free to produce any observable behavior whatsoever in the presence of a data race.
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.
It absolutely is possible for a value to decrease, and that does not require reads or writes to not be atomic.
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.
There are still some points in your explanation of data races that are not entirely correct (partly a matter of definitions).
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.
I would have an issue with having Python in some sort of development mode that would change behavior versus deployed mode ? (I don’t even think how this would occur other than adding an argument to the interpreter itself). Mainly because of having two separate modes of operations.
The author evidently does not understand how threaded programming works in Python. The reason for the "data races" he describes is that, even with the GIL in Python, you have no control over the order in which different threads execute particular operations that are operating on the same objects, unless you use synchronization primitives like mutexes. Python has never claimed that having the GIL allows you to avoid that.
The Python documentation on threading and the GIL [1] makes it clear that the reason for the GIL is to make operations on Python objects inside the interpreter thread-safe, by ensuring that the C structures that store the states of Python objects can only be mutated by one thread at a time. All of those C-level operations happen "inside" a single bytecode. Python operations that require multiple bytecodes do not have any of the same guarantees.
> It's too bad they exposed the GIL to C extension authors.
As I understand it, yes, that has been one of the main obstacles to removing the GIL. The current way forward seems to be to make all the interpreter state per-thread, so that each thread could have a separate interpreter; this would make the GIL unnnecessary, but of course one would still need synchronization primitives like mutexes to control access to data shared between threads.
For what it’s worth, Python does have an atomic add instruction, but because integers are immutable, the load/store operations to the global variable are unsynchronized (the add produces a new object which must be stored to the global).
If you replace the Python integer with a 0D NumPy array, and use a real in-place operation, the race disappears:
import numpy as np
counter = np.array(0, dtype=np.uint32)
one = np.uint32(1)
def increase():
global counter
for i in range(0, 100000):
counter += one
Of course, the lesson still holds: accessing shared state from multiple threads still requires care; you don’t get to ignore these things just because Python has a GIL.
This is not a data race in the sense that Rust prevents.
Case in point, here is the same race condition in Rust:
- playground[0] (see for yourself)
- inline code (not that long):
use std::thread;
use std::sync::atomic::AtomicU32;
use std::sync::atomic::Ordering;
static COUNTER : AtomicU32 = AtomicU32::new(0);
fn increase() {
for _i in 0..100000 {
let a = COUNTER.load(Ordering::SeqCst);
COUNTER.store(a + 1, Ordering::SeqCst);
}
}
fn main() {
let mut threads = Vec::new();
for _i in 0..400 {
threads.push(thread::spawn(increase))
}
for thread in threads {
thread.join().unwrap();
}
println!("Final counter: {}", COUNTER.load(Ordering::SeqCst))
}
The data races that Rust prevents are "instruction-level data races". They occur when a single, non atomic, architectural instruction is executed in parallel by multiple threads. In that case we can really get corrupted values, in that "partially written" value in the architectural sense (depending on architectural details) can be produced. Think a double word with one word rewritten by one thread and the other word rewritten by the other thread.
In the given code example that is not an instruction-level data race, the produced value will strictly be in the range <max_number_of_increase>..<max_number_of_increase>*<number_of_threads> (plus or minus the usual off-by-one error), and no architectural artifacts can ever manifest.
I guess the insight of the article could be that `counter = counter + 1` is closer in Python from `a = atomicLoad(counter); atomicStore(counter, a + 1)` than from `atomicIncrement(counter)`?
I wonder if using `counter += 1` changes anything? In any case, I can see how it is easier to trigger accidental race conditions of that kind in Python than in Rust, with the atomic operations being implicit in the former, and explicit in the latter.
77 comments
[ 5.1 ms ] story [ 214 ms ] threadHere is an example what thread safe increment looks like in Python:
https://julien.danjou.info/atomic-lock-free-counters-in-pyth...
You need to lock it explicitly.
Note that `INC` instructor for x86 architecture needs explicit hints/locks as well, so this should suprise anyone:
https://stackoverflow.com/q/10109679
Hypothetically, if Python had a built-in mutable integer type, the increment could be made atomic.
Obviously, the fundamental issue with concurrency is programmer’s intent. This statement:
can be interpreted in two ways: or The best the compiler can do would be to alert the programmer of the ambiguity; I know of no compiler that does that.I used to think that it did as well, but then my C/Java brain kicked in and realized that couldn't be correct. I wrote this article to help others see it in action.
I did too. I even wrote multithreaded test programs to see if it was true: they would always give me consistent results on Python and Ruby but on Java and C data got clobbered as expected.
essentially the same operations in the same order, that need to be isolated (i.e. transactional / atomic) from concurrent threads performing the same operations.
That sounds good and authoritative. Unfortunately the Python documentation itself is silent on the subject. And more importantly the Python community is filled with people who believe exactly the opposite.
It's a real hole. And the only solution right now is to tell everyone to avoid threads. The Python world simply isn't prepared for them.
FWIW: I'm one of a handful of people who have found and fixed race conditions in python scripts. And it was largely because my background is in racey C code and my eyes were primed to see it. And even then, I genuinely thought (based on incorrect advice like the above) that this sort of thing was impossible and kept looking before trying the obvious synchronization solution. And it was only then that I realized what a mess concurrency is in the mind of the modern python developer.
1. Don't allow any undefined behavior or `unsafe` code in the language.
2. Record all inputs from FFI.
3. Carefully track the orderings of interactions across threads.
The article goes into the first two, but the third one is the most interesting IMO:
When we unlock a mutex or send a message, we assign a "sequence number" (similar to what we see in TCP packets).
Whenever we lock a mutex or receive a message, we read the sequence number and record it to this thread's "recording".
When replaying, we use that sequence number and that file to make sure we're reading in the same order as the previous execution.
An unexpected state would seem to break the memory model, and lead to corrupted data, wouldn't it?
It's kind of like a time-traveling debugger, but with stronger guarantees.
I'm particularly excited about combining this with concurrency, we'll never have to spend hours hunting down mysterious race conditions ever again!
I learned very early on that python threads should be treated like C threads, and therefore should be avoided. Also there really isn't a performance gain to using threads (other than maybe waiting for IO completion).
Why ? I'm on Linux, using Python 3.10. It's only happening using Python2.7.
> Ironically, CPython 3.10 has gone the opposite direction and made thread scheduling much more deterministic. It now only releases the GIL on backwards edges in the byte code The example in the article always prints 40000000 in CPython 3.10! I expect this will ultimately make Python code less reliable in the future as many programs will accidentally depend on this behavior.
The fact that "counter" gets modified between the read and the write doesn't imply that multiple accesses were happening simultaneously; it just means that accesses from different threads were getting interleaved. The GIL would only prevent the former but not the latter, since a thread can give up the GIL at any point between operations.
and yes, as everyone is saying, the gil keeps the python interpreter/runtime from ending up in an inconsistent state... its behavior should not be depended on by user programs. if you need to increment a counter, use a lock, or a counter that explicitly states that it's a thread safe atomic counter on the tin.
https://link.springer.com/referenceworkentry/10.1007/978-0-3...
Under the section 'General Races and Data Races', then 'Data race'. There's a definition of data races, in relation to general races.
"A data race is a special case of a general race. A data race exists between conflicting memory accesses..."
Why? Who defines that?
We wouldn't expect this to be atomic, because the get_value() function could do tons of things, and we don't expect all that to be atomic. It doesn't make sense to call something atomic just because the user wrote it.
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.
(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...
[3] https://en.cppreference.com/w/cpp/language/memory_model
[4] https://en.wikipedia.org/wiki/Race_condition#Data_race
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.
(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.
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.
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.
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).
Edit: You also need to realize that in Python, that BINARY_ADD can be anything:
The GIL isn't going to wait around for the __add__.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...)
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.
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.
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.
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.
https://www.reitzen.com/post/temporal-fuzzing-01/
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.
The Python documentation on threading and the GIL [1] makes it clear that the reason for the GIL is to make operations on Python objects inside the interpreter thread-safe, by ensuring that the C structures that store the states of Python objects can only be mutated by one thread at a time. All of those C-level operations happen "inside" a single bytecode. Python operations that require multiple bytecodes do not have any of the same guarantees.
[1] https://docs.python.org/3/c-api/init.html#thread-state-and-t...
As I understand it, yes, that has been one of the main obstacles to removing the GIL. The current way forward seems to be to make all the interpreter state per-thread, so that each thread could have a separate interpreter; this would make the GIL unnnecessary, but of course one would still need synchronization primitives like mutexes to control access to data shared between threads.
If you replace the Python integer with a 0D NumPy array, and use a real in-place operation, the race disappears:
Of course, the lesson still holds: accessing shared state from multiple threads still requires care; you don’t get to ignore these things just because Python has a GIL.Case in point, here is the same race condition in Rust:
- playground[0] (see for yourself)
- inline code (not that long):
The data races that Rust prevents are "instruction-level data races". They occur when a single, non atomic, architectural instruction is executed in parallel by multiple threads. In that case we can really get corrupted values, in that "partially written" value in the architectural sense (depending on architectural details) can be produced. Think a double word with one word rewritten by one thread and the other word rewritten by the other thread.In the given code example that is not an instruction-level data race, the produced value will strictly be in the range <max_number_of_increase>..<max_number_of_increase>*<number_of_threads> (plus or minus the usual off-by-one error), and no architectural artifacts can ever manifest.
I guess the insight of the article could be that `counter = counter + 1` is closer in Python from `a = atomicLoad(counter); atomicStore(counter, a + 1)` than from `atomicIncrement(counter)`?
I wonder if using `counter += 1` changes anything? In any case, I can see how it is easier to trigger accidental race conditions of that kind in Python than in Rust, with the atomic operations being implicit in the former, and explicit in the latter.
[0]: https://play.rust-lang.org/?version=stable&mode=release&edit...