5 ms·

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 inv

by Kranar 5y ago

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.

verdagon 5y ago
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)
- Kranar 5y ago
  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 https://blog.regehr.org/archives/490 [1] https://doc.rust-lang.org/nomicon/races.html https://doc.rust-lang.org/nomicon/races.html [2] https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.html https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.ht... [3] https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model [4] https://en.wikipedia.org/wiki/Race_condition#Data_race https://en.wikipedia.org/wiki/Race_condition#Data_race
  - verdagon 5y ago
    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.
rwbhn 5y ago
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'.
- Kranar 5y ago
  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.
  - hedora 5y ago
    > 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.
    - Kranar 5y ago
      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.
reitzensteinm 5y ago
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/ https://www.reitzen.com/post/temporal-fuzzing-01/
- deleted 5y ago
  [deleted]
Hercuros 5y ago
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.

by Kranar 5y ago

verdagon 5y ago

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)

Kranar 5y ago
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 https://blog.regehr.org/archives/490 [1] https://doc.rust-lang.org/nomicon/races.html https://doc.rust-lang.org/nomicon/races.html [2] https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.html https://docs.oracle.com/cd/E19205-01/820-0619/geojs/index.ht... [3] https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model [4] https://en.wikipedia.org/wiki/Race_condition#Data_race https://en.wikipedia.org/wiki/Race_condition#Data_race
- verdagon 5y ago
  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.

rwbhn 5y ago

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

Kranar 5y ago
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.
- hedora 5y ago
  > 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.
  - Kranar 5y ago
    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.

reitzensteinm 5y ago

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/ https://www.reitzen.com/post/temporal-fuzzing-01/

deleted 5y ago
[deleted]

Hercuros 5y ago

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.