31 ms·

The Problem with Threads (2006) [pdf]

80 points by DonbunEf7 8y ago

rectang 8y ago
I've always liked section 3 of this paper, specifically the concept that "infinite interleavings" make threads executing in parallel non-deterministic and difficult to reason about. That gets to the heart of why threaded programs are so prone to heisenbugs. "They make programs absurdly nondeterministic, and rely on programming style to constrain that nondeterminism to achieve deterministic aims." You can't write an infinite number of test cases for all those interleavings, and it requires hard thought to suss out where any problems might lie.
- vvanders 8y ago
  Ayup. My favorite one is where adding debug traces causes the heisenbug to disappear because the printf() inserted a memory fence somewhere deep in the logging library. Nothing like debugging via atomics.
- jlarocco 8y ago
  This is just my opinion, but I've never found that part of multi-threading difficult. Interleaving doesn't matter except where resources are shared between multiple threads, and the solution is to protect the resource with a mutex. Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading.
  - typomatic 8y ago
    > Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading. With respect, this sort of thing works a lot better for small codebases where you're the only one working on it. Multithreading when you can't contain the entire relevant codebase in your brain is where the real challenge is.
  - mchahn 8y ago
    > the solution is to protect the resource with a mutex. Then you have deadlocks.
- chubot 8y ago
  This talk was about Foundation DB was brought up recently, and it's pretty amazing. I recommend watching the whole thing, but to be brief they are taming the "infinite interleavings" problem through determinism. "Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson https://www.youtube.com/watch?v=4fFDFbi3toc https://www.youtube.com/watch?v=4fFDFbi3toc They wrote an interesting Actor DSL that compiles to C++ and is completely deterministic, and they torture this deterministic engine with generated test cases on a cluster every night. I guess you could say that the whole cluster is necessarily non-deterministic, but an individual node is deterministic, given an ordering of the messages it receives.
- ModernMech 8y ago
  I identify with this bit from the paper > To offer a third analogy, a folk deﬁnition of insanity is to do the same thing over and over again and to expect the results to be different. By this deﬁnition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs. I actually had this exact notion when implementing pthreads for a course. I noted to myself "Gee, I keep doing the same thing and every time I get a different result... I must be insane according to the definition"
jgtrosh 8y ago
This piece seems to have predicted a very active field in everyday software development since then. What are the alternative paradigms that have actually become common use? Coroutines, async/await, that's what I hear about online but what are others? I've seen people who touted zmq-communicating-processes with standard patterns as the solution to all problems, and I'm happy not to have to maintain the results. Have we effectively “solved” the concurrency problem, and if so what's left as an exercise for the future?
- chrisseaton 8y ago
  Although this paper talks initially about concurrency, you can see that really he's talking about concurrency specifically for the purpose of parallelism. Coroutines don't solve the parallelism part, because they're concurrent but exclusive. Async/await as implemented in JavaScript doesn't solve the parallelism part either for the same reason, and async/await as implemented in C# has exactly the same problem as threads. There are many ideas for how to solve the problem - but I think anyone who is honest will tell you none are a perfect solution to all situations where you want parallelism or concurrency. For example to use zmq-communicating-processes effectively you need a problem where you can divide the data or tasks cleanly a-priori. We simply don't have the mathematical understanding of how to do that to some important algorithms that people really need to run in parallel today, such as triangulation or mesh refinement. We probably need some radical new idea, or maybe it's looking increasingly like only a mix of ideas will work.
  - amelius 8y ago
    Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.
    - chrisseaton 8y ago
      They’re the canonical example everyone uses of where it doesn’t work well! In both of them there is tons of parallelism but you can’t work out what work is separate (divide it) until you have started the work.

80 points by DonbunEf7 8y ago

I've always liked section 3 of this paper, specifically the concept that "infinite interleavings" make threads executing in parallel non-deterministic and difficult to reason about. That gets to the heart of why threaded programs are so prone to heisenbugs. "They make programs absurdly nondeterministic, and rely on programming style to constrain that nondeterminism to achieve deterministic aims." You can't write an infinite number of test cases for all those interleavings, and it requires hard thought to suss out where any problems might lie.

vvanders 8y ago
Ayup. My favorite one is where adding debug traces causes the heisenbug to disappear because the printf() inserted a memory fence somewhere deep in the logging library. Nothing like debugging via atomics.
jlarocco 8y ago
This is just my opinion, but I've never found that part of multi-threading difficult. Interleaving doesn't matter except where resources are shared between multiple threads, and the solution is to protect the resource with a mutex. Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading.
- typomatic 8y ago
  > Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading. With respect, this sort of thing works a lot better for small codebases where you're the only one working on it. Multithreading when you can't contain the entire relevant codebase in your brain is where the real challenge is.
- mchahn 8y ago
  > the solution is to protect the resource with a mutex. Then you have deadlocks.
chubot 8y ago
This talk was about Foundation DB was brought up recently, and it's pretty amazing. I recommend watching the whole thing, but to be brief they are taming the "infinite interleavings" problem through determinism. "Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson https://www.youtube.com/watch?v=4fFDFbi3toc https://www.youtube.com/watch?v=4fFDFbi3toc They wrote an interesting Actor DSL that compiles to C++ and is completely deterministic, and they torture this deterministic engine with generated test cases on a cluster every night. I guess you could say that the whole cluster is necessarily non-deterministic, but an individual node is deterministic, given an ordering of the messages it receives.
ModernMech 8y ago
I identify with this bit from the paper > To offer a third analogy, a folk deﬁnition of insanity is to do the same thing over and over again and to expect the results to be different. By this deﬁnition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs. I actually had this exact notion when implementing pthreads for a course. I noted to myself "Gee, I keep doing the same thing and every time I get a different result... I must be insane according to the definition"

jgtrosh 8y ago

This piece seems to have predicted a very active field in everyday software development since then. What are the alternative paradigms that have actually become common use? Coroutines, async/await, that's what I hear about online but what are others? I've seen people who touted zmq-communicating-processes with standard patterns as the solution to all problems, and I'm happy not to have to maintain the results. Have we effectively “solved” the concurrency problem, and if so what's left as an exercise for the future?

chrisseaton 8y ago
Although this paper talks initially about concurrency, you can see that really he's talking about concurrency specifically for the purpose of parallelism. Coroutines don't solve the parallelism part, because they're concurrent but exclusive. Async/await as implemented in JavaScript doesn't solve the parallelism part either for the same reason, and async/await as implemented in C# has exactly the same problem as threads. There are many ideas for how to solve the problem - but I think anyone who is honest will tell you none are a perfect solution to all situations where you want parallelism or concurrency. For example to use zmq-communicating-processes effectively you need a problem where you can divide the data or tasks cleanly a-priori. We simply don't have the mathematical understanding of how to do that to some important algorithms that people really need to run in parallel today, such as triangulation or mesh refinement. We probably need some radical new idea, or maybe it's looking increasingly like only a mix of ideas will work.
- amelius 8y ago
  Triangulation and mesh refinement seem suitable for divide and conquer, except perhaps in pathological cases.
  - chrisseaton 8y ago
    They’re the canonical example everyone uses of where it doesn’t work well! In both of them there is tons of parallelism but you can’t work out what work is separate (divide it) until you have started the work.