3 ms·

I have to second that. Parallel programming is extremely hard to get right and people persistently underestimate it. For example, I've seen many times code that

I have to second that. Parallel programming is extremely hard to get right and people persistently underestimate it. For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. Of course, it depends a lot on what your programming language has to offer. For example,in my experience Ada makes it easier to get parallelism correct than many other languages, primarily because Ada tasks have a precisely defined and specified semantics and because Ada's "Rendesvouz" makes certain kinds of errors impossible. The same is sometimes claimed about Rust. In more permissive languages like Go, however, almost every parallel program is wrong in one way or another. For example, it is extremely common for parallel Go libraries to stop in a deadlock. The situation is so bad that I have stopped using concurrent Go libraries, except for the well-implemented standard libraries. Even then, many package authors don't tell you what they do internally and their libraries lock up in unexpected places. For example, I've recently been looking for a parallel tree walker library in Go, and every package I tried stopped with an infinite deadlock on my file system, presumably due to the interplay between error handling and spawning goroutines. Ironically, even many goroutine scheduling libraries I've tried have locked themselves up.

ColanR 7y ago
> For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. As someone who has made that assumption, what's wrong with it?
- jcranmer 7y ago
  If you have two accesses on different threads, at least one of which is a write, then you need a synchronization chain between them. Note that this is true even if the read occurs before the write. The most common synchronization chain is the first thread doing some kind of "release" action (releasing a mutex, or storing to an atomic variable using a release (or stronger) ordering type), followed by the second thread doing some kind of "acquire" action on the thing that was "release"d. When you are missing the synchronization chain, the issue you can run into is that the value of other memory locations is undefined. The sequence of accesses to any given location does comprise a total order (due to cache coherence), but it is not generally the case that the ordering of accesses to different locations will be agreed on by different threads.
  - tomp 7y ago
    I'm not a low level programmer, but can you elaborate on this a bit? E.g. why would reading a shared mutable value be wrong, in some specific circumstances? In particular, if the value is a word (and the architecture guarantees atomic writes for word-sized values), and if the reader doesn't care if it reads the previous or the new value (e.g. executes a read of a monotonic counter in a loop, so even if I read the current value this time, I'll read the new value next time or after some number of next times), and if the language is sensible (i.e. Java, not C++... although AFAIK even C++ frowns upon "values out of thin air" and they're trying to modify the standard to formally prohibit them... but in general the issue with C++ is the compiler, not the platform if we assume x86).
    - jcranmer 7y ago
      If you've never had to deal with this stuff before, you probably follow a naive model of memory, wherein all operations are "sequentially consistent": you pick a random thread, and you execute the next memory instruction, and everyone understands that the memory is updated. That model is not how any multicore hardware is actually implemented, because it is slow and often unnecessary. Now, it is known that, if your program is correctly synchronized, then the existing hardware models are indistinguishable from sequentially consistent execution. This gives rise to the data-race-free model that defines all modern language-level programming models: data races can only exist in the absence of proper synchronization, so we call that behavior undefined [1], and our code goes back to sequential consistency. The primary issue is that there are two entities playing games with your code to support faster execution: both the compiler and the hardware are making assumptions to speed things up. From the perspective of hardware (i.e., why using "volatile" to stop the compiler from playing games isn't good enough), different processors may have the values in their caches. While cache coherency requires that any given point in time, every processor must agree on the value of every memory location, there is great leeway to reorder loads and stores so that they may execute in different orders than the instruction sequence implies. In the extreme, it is possible that the load of *p may happen before the load of p itself (this is the Alpha memory model, and comes from the existence of uncoordinated cache banks). [1] Okay, there's a slight untruth here: the C++11 "relaxed atomics" is effectively a data race as could be observed by hardware, but is not undefined in the C++11 sense. This is where it's important to point out that we have been struggling for over a decade to actually come up with a suitably precise definition for relaxed atomics that we're happy with--it is by no means a solved problem.

ColanR 7y ago

> For example, I've seen many times code that erroneously assumed that values can be read from global memory concurrently if only write access is guarded. As someone who has made that assumption, what's wrong with it?

jcranmer 7y ago
If you have two accesses on different threads, at least one of which is a write, then you need a synchronization chain between them. Note that this is true even if the read occurs before the write. The most common synchronization chain is the first thread doing some kind of "release" action (releasing a mutex, or storing to an atomic variable using a release (or stronger) ordering type), followed by the second thread doing some kind of "acquire" action on the thing that was "release"d. When you are missing the synchronization chain, the issue you can run into is that the value of other memory locations is undefined. The sequence of accesses to any given location does comprise a total order (due to cache coherence), but it is not generally the case that the ordering of accesses to different locations will be agreed on by different threads.
- tomp 7y ago
  I'm not a low level programmer, but can you elaborate on this a bit? E.g. why would reading a shared mutable value be wrong, in some specific circumstances? In particular, if the value is a word (and the architecture guarantees atomic writes for word-sized values), and if the reader doesn't care if it reads the previous or the new value (e.g. executes a read of a monotonic counter in a loop, so even if I read the current value this time, I'll read the new value next time or after some number of next times), and if the language is sensible (i.e. Java, not C++... although AFAIK even C++ frowns upon "values out of thin air" and they're trying to modify the standard to formally prohibit them... but in general the issue with C++ is the compiler, not the platform if we assume x86).
  - jcranmer 7y ago
    If you've never had to deal with this stuff before, you probably follow a naive model of memory, wherein all operations are "sequentially consistent": you pick a random thread, and you execute the next memory instruction, and everyone understands that the memory is updated. That model is not how any multicore hardware is actually implemented, because it is slow and often unnecessary. Now, it is known that, if your program is correctly synchronized, then the existing hardware models are indistinguishable from sequentially consistent execution. This gives rise to the data-race-free model that defines all modern language-level programming models: data races can only exist in the absence of proper synchronization, so we call that behavior undefined [1], and our code goes back to sequential consistency. The primary issue is that there are two entities playing games with your code to support faster execution: both the compiler and the hardware are making assumptions to speed things up. From the perspective of hardware (i.e., why using "volatile" to stop the compiler from playing games isn't good enough), different processors may have the values in their caches. While cache coherency requires that any given point in time, every processor must agree on the value of every memory location, there is great leeway to reorder loads and stores so that they may execute in different orders than the instruction sequence implies. In the extreme, it is possible that the load of *p may happen before the load of p itself (this is the Alpha memory model, and comes from the existence of uncoordinated cache banks). [1] Okay, there's a slight untruth here: the C++11 "relaxed atomics" is effectively a data race as could be observed by hardware, but is not undefined in the C++11 sense. This is where it's important to point out that we have been struggling for over a decade to actually come up with a suitably precise definition for relaxed atomics that we're happy with--it is by no means a solved problem.