Hacker News Reader

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.

https://www.reitzen.com/post/temporal-fuzzing-01/

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:

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

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.

(Edited in response to your edit)

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.

Two different kinds of concurrency, a twist! If you have a link to enlighten, I'd love to read more about this.

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!

Let's try simpler:

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).

Just look at the bytecode.

  >>> 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__.

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...)

what about alpha?

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.

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.

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.

As reitzensteinm points out, even if every thread does "x = x + 1", x can decrease.

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.