Why Is Concurrent Programming Hard?
stefan-marr.de
stefan-marr.de
Also, due to variation in scheduling order, concurrent program's bugs may be only sometimes reproducible, even when the input between the working and failed cases are identical. It's as if all concurrent programs have an implicit real-time input source that perturbs their behavior.
The bugs in concurrent programs are an entirely new class, like "race condition", "lost wakeup" and "deadlock". Even a great programmer who understands N levels of pointer dereferencing and "leaps complicated algorithms in a single bound", but has no concurrent experience, may well be defeated by concurrency bugs.
When we write programs, we normally keep them tidy by taking advantage of scoping. Data is localized using local variables. We use parameter passing to communicate among modules and avoid globals. However, imperative concurrent programming is all about globals: the "shared variables" that have to do with the concurrency of the program, violate scoping: necessarily so, because to be shared, they have to be accessible from multiple scopes.
In imperative programming, there is an important reassurance: namely that variables retain their last stored value. If you put 42 into x, then x keeps holding 42 until you put something else in x. If x is globally visible, and you call some function, forgetting that it has a side effect of changing x, it wrecks this assumption. Suddenly, x has mysteriously changed: you could swear you put in 42, but now it somehow has 43. Why? All you did was call foo; that has nothing to do with x. Oh, but someone committed a change, and foo now calls bar, and bar makes several other functiosn calls which end up back in this same unit in another function that frobs x.
In concurrent programming, you are opening the doors to this type of problem: and what is worse is that shared variable x can change at any time, not over some predictable action like calling a function. When you assign 42 to x, x could turn into 43 even before control passes out of the assignment statement and to the next statement.
All the surprises arising from multiple scopes having visibility over the same shared data become worse thanks to the asynchronous nature and unpredictable scheduling order.
If you keep programming in the same way that you are used to, you are guaranteed to have a problem. Simply to have the same assurance that "x is holding the value I put there in the current thread of control" you need to take special steps, like locking a mutex (consistently, from every user of x) whereas in non-concurrent programming, the assurance comes from good design, like making x local, or simply not branching into any code which might change x for as long as you need x not to change. I.e. you can achieve the basic assumption quite passively in the absence of concurrency (based on what you don't do), whereas you have to be proactively cunning in concurrent programming.
I may be nitpicking here but "accessible from multiple scopes" is not the same as being "all about globals". Data can usually still be localized to the routines that use it without throwing it in the global scope. The inherent problem of two threads sharing data is also something that will _have to_ be dealt with on some layer of the implementation if you want the threads to communicate, regardless of programming paradigm. Some languages provide really nice abstractions to deal with this in ways that don't explicitly have the programmers invoke locks. Among imperative languages, Go provides a really useful and sensible such abstraction with channels.
> In concurrent programming, you are opening the doors to this type of problem: and what is worse is that shared variable x can change at any time, not over some predictable action like calling a function. When you assign 42 to x, x could turn into 43 even before control passes out of the assignment statement and to the next statement.
Still nitpicking, but you should separate the concerns of parallel programming that don't necessarily have anything to do with concurrent programming. Imperative concurrent programming can be implemented by having routines explicitly yield control to other routines (e.g. protothreads, greenlets), making the execution order entirely predictable.
(There can be a loose order in cooperative threading in not knowing which thread will be run next when yield is called. It's still not serialized.)
Reading the first part of the article is a good start on understanding the distinction. Maybe this sort of lack of a basic understanding of the concepts is why concurrent programming is hard.
However, simulated concurrency requires asynchronous behavior: an external event, such as a timer interrupt, or the arrival of input, can come in at any time and change the control among the tasks (preemption). This looks a lot like true parallelism and must be programmed with the same care as real parallelism, which is why we dare call it concurrency.
Tasking without preemption is not concurrency. The tasks know that they cannot be preempted and rely on that assumption for their correctness. This approach falls into the same domain as the use of coroutines, or dispatch queues of lexical closures, first class continuations, generators and such: none of which represent concurrency.
I do not believe I require any correction in terminology or concepts; I've been programming for 33 years, and I'm the person who invented and first implemented glibc's PTHREAD_MUTEX_ADAPTIVE_NP mutex back in 2000.
You're also implying it is possible to program without shared mutable state. To the best of my knowledge, practically every interesting program (other than compilers) has shared mutable state (yes, even Haskell programs), even if it is delegated to a database (which, of course, also has to be concurrent, and has to be programmed by someone).
Now, the quest for a true general purpose STM has been abandoned, but more domain-specific forms (or even in-memory databases, which are, essentially, STM) are still very much in the game.
Granted, I just recently managed to butcher[1] what is effectively an "anti-immutable" algorithm. Seeing that there have been parallel versions of this algorithm implemented successfully, I can't bring myself to throw out that tub yet. Did they do this by removing the mutable nature of the algorithm? Not to my knowledge. No, instead they kept this mutable tool and built on top of it with something that is basically message passing.
That is, instead of throwing out the mutable tools we have, you can also segment the work you are giving out. This isn't exactly novel, either. Consider anyone planning the festivities of any major event. Timelines and work plans are par for the course. Yet, we often try to make things "just work" for us "in time" in programming.
Still, if you want one "true" abstraction. My bet is on Channels. :)
Nobody is trying to abandon mutable state (or nobody should, at least). If we abandoned it, our computer would be a static screen where nothing would happen.
Functional programmers embrace mutable state, but only where it's needed! If the program is faster or cleaner using mutable state, why not? Check some of Clojure's mutable constructs as an example:
http://clojure.org/vars | http://clojure.org/Refs | http://clojure.org/Atoms | http://clojure.org/transients
Don't get me wrong, I realize most folks are more pragmatic than they are dogmatic. However, I also know that all of my coworkers and most folks I have talked to are obsessed with "persistent" collections. Often touting them as some sort of must have for reliable multithreaded work.
people have trouble even with database transactions - the simplest "imperative with mutable" concurrency model around. The simplicity comes in particular from well-defined hierarchy of objects and locking semantics upon them. No wonder that programs with concurrency, especially written in OOP languages where mutable state hidden, spread around in really disorganized way and de-facto inter-mixed with code, is just a mess. The article mentions Netbeans - yep, UI OOP models are among the messiest.
There is some interesting research on game theoretic adaptive schedulers for highly concurrent systems. Basically, if a scheduler in one process can model the behavior of schedulers in all other processes it interacts with, it can dynamically choose an operation with very low or zero probability of conflicting with the decisions made by all the other schedulers. In principle, this leads to all the schedulers getting maximum work done with minimum coordination or conflict.
Some algorithms I built for massively parallel systems work this way. At some level of concurrency, agreement and coordination becomes impractical so you have to come up techniques where the individual processes make choices that ensure they do not step on each other by making assumptions about the processes they interact with.
The other route is, I think, less well described as "abstraction" and more around restriction. For instance, Erlang's model simply ensures that while you're dealing with exponentially many program states, the kinds of interaction between those states means that you basically are able to pretend like they don't exist for most problems. (This is also the mechanism of things like Bloom and LVars which are whole models of commutative/convergent programming that happen to be executable in parallel).
[0] Here's a good one: combinatorial topology! https://www.elsevier.com/books/distributed-computing-through...
A really good takeaway from the talk is a point he made on software testing: for sequential algorithms, conventional software testing is likely to find most of the bugs you really care about. For concurrent algorithms, however, finding those bugs through software testing is extremely unlikely; an Amazon paper on TLA+ usage[0] details a bug found which required a 35-step trace to reproduce. Given the speed of computers today, it's only a matter of time before these bugs are hit and your system implodes in a confusing and impossible-to-reproduce way. Software testing by itself just isn't good enough anymore.
[0] http://research.microsoft.com/en-us/um/people/lamport/tla/am...
That is, what makes your domain most understandable is not necessarily what makes it most amenable to concurrency. Indeed, it may be directly opposed to this.
This is particularly obnoxious in models where folks try to have a single Foo object that is used everywhere anything representing even part of a Foo is used.
This sounds flippant, but it's not. The erlang BEAM VM is the only system designed to do concurrency correctly. Unfortunately, I think that many people think that concurrency can be done in a library, or on non-concurrent systems like the JVM. I understand fully why Go would like to claim to be concurrent, and all the other languages would like to claim it, because the reality is we're in a multi-core multi-node distributed world. But don't fall for it.
Worse, there are some simple low hanging "concurrent" fruit like go-routines that make it seem like you've solved the problem.
I would have no problem if someone had made a language and VM or compiled-to-binary like go, that was truly concurrent, and that copied the erlang solution (no mutable state, supervision trees, let it fail, etc.)
Seriously, steal from the best if you're making a new language.
So far, nobody has. And since we live in a multi-node, multi-CPU world, you really should learn erlang (or elixir- which adds some features and has an easier syntax).
Seriously, I know it's much easier to go with flavor-of-the-month and pretend that there is no downside. But sooner or later-- hopefully sooner, because it will be much more painful later-- you have to pay the piper for not being concurrent. We've seen massive failures and re-architecting of systems as a result-- twitter survived years of fail whales because of their poor initial engineering. Can you count on enough VC money to do the same?
PS- not to pick on Go. Go has several features that are really bright choices. I am just using it as an example here, but I've heard of everything up to and including node.js being claimed as making erlang unnecessary.
That's a fairly bold claim. Erlang is good at the actor model. It's not an all-around winner in concurrency.
Another shining example is the Glasgow Haskell Compiler runtime system. It has an exceptionally fast and efficient green thread system that (in the latest version of GHC) can scale almost-linearly up to 32 cores, even with some resource contention, and can easily handle millions of concurrent threads. I suspect you could emulate Erlang actors with very little loss of efficiency. (And, of course, you're also free to use a thread-based model.)
And being a language with type-system-encapsulated mutability (and very nice resource contention management mechanisms like STM), concurrency is often "free" and very safe. An example of how concurrency is "free":
main = do
forkIO (putStrLn "thing1")
forkIO (putStrLn "thing2")
threadDelay 1000
A few interesting things to look at:
http://benchmarksgame.alioth.debian.org/u32/performance.php?...
http://haskell.cs.yale.edu/wp-content/uploads/2013/08/hask03...
edit: Added thread delay so code example works out of the box.
I don't know seem true and practical to me. The industry (WhatsApp, Riak, CouchDB, RabbitMQ) and chances are, even your smart phones disagree with you. They are many other closed source applications in the industry that reliably handle concurrency using Erlang.
> I suspect you could emulate Erlang actors
No you can't unless you run in an isolated heap and add a many years battle tested VM system and libraries built for concurrency and fault tolerance.
Otherwise yes, anyone can make a thread work with thread-safe queue -- look Erlang! Nope. Not Erlang. It is a fork-join or just a plain thread+queue.
> It's not an all-around winner in concurrency.
Yes it is. The winner in concurrency is system that has most fault tolerance tooling built in. That is true secret. "Millions of concurrent" threads are useless if the crash of one brings down the rest.
Yes, Haskell already has per-OS-thread heaps, and there's not really any need for isolation since everything is immutable and GCed anyway.
>many years battle tested VM system
The VM is an implementation detail, not a feature. But yes, the GHC RTS is basically a VM.
>libraries built for concurrency and fault tolerance
Yes, Haskell has those. Specifically, libraries work no matter how they're being executed (concurrently or otherwise), and they're fault tolerant in the sense that error conditions are encapsulated in the type system and the libraries do not generally crash.
>It is a fork-join or just a plain thread+queue.
Well, not necessarily. I can express an actor however I want. Haskell forks aren't like regular C forks; they're much more flexible. It's basically the same thing as Actors in Erlang. The thread only gets picked up when something happens to a resource it's waiting on (like actors in Erlang).
>The winner in concurrency is system that has most fault tolerance tooling built in.
Well, Haskell has excellent fault tolerance support, but the recommended programming style is just to never crash, which is an entirely reasonable request when you're writing in Haskell.
>"Millions of concurrent" threads are useless if the crash of one brings down the rest.
There's no particular reason it would. See the `catch`, `handle`, etc. combinators for how to deal with errors in Haskell (although again, it's recommended just to write programs that don't crash).
What makes my spider-sense tingle in Haskell is lazyness. It's all cool until you unexpectedly hit that lazy unroll (not sure what the correct term is) in a time-critical system.
Are there ways to control lazyness in Haskell, just like there are ways to control mutable state?
You can use a number of techniques (the simplest being Bang Patterns) to enforce non-lazy evaluation strategies (including strict evaluation, parallel evaluation, sequential evaluation, etc.).
However, there are very few activities where Haskell's laziness will cause disruptive timing variations. Any language that you might use instead of Haskell is probably heavily heap-oriented, and likely garbage collected, which means that you're already dealing with unpredictable timing variance.
However, once you get used to it, you start to find that strict evaluation is rarely useful.
Yes. http://www.haskell.org/haskellwiki/Performance/Strictness
import Control.Concurrent
main = do
forkIO (putStrLn "thing1")
forkIO (putStrLn "thing2")
import Control.Concurrent
loop :: Int -> Int
loop x = loop x
main = do
forkIO (putStrLn "thing1")
forkIO (putStrLn "thing2")
putStrLn $ show (loop 0)
See: http://www.haskell.org/haskellwiki/Concurrency and http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/using...
And Haskell threads aren't preempted except on memory allocation, so a tight loop without memory allocation never is preempted, so the main thread here never is forced out of control.
It's very different from most concurrency systems. It's a very, very lightweight cooperative green thread system. We're kind of dealing with pathological edge cases here. We're forking to do exceptionally simple, fast things (you shouldn't do that) and we're trying to sleep by wasting CPU cycles (you shouldn't do that).
For example, this works fine:
import Control.Concurrent
main = do
forkIO (putStrLn "thing1")
forkIO (putStrLn "thing2")
threadDelay 1000
1. Reasoning about systems with multiple concurrent series of events which can interact with eachother is harder than reasoning about a single, serial chain of events, and
2. For a long time most programming environments (languages and libraries) -- and this is still true of many that are still widely used -- have only rudimentary support for concurrency.
Progress in language facilities and libraries is mitigating #2, but #1 is fairly fundamental.
No languages nor tools will ever entirely fix this. The promoters of Erlang and Haskell in this discussion are optimists. I'm particularly amused by the notion that Haskell threads only yield on memory allocation, which is the worst kind of imperative programming heuristic, forcing the programmer to worry a great deal about the ordered sequence of operations and the way in which it will change the state of the system in exactly the way Haskell is supposed to not to.
I don't think this is a fault in Haskell: it is just a pragmatic language designer bowing to the inevitable (although I'd argue that having the potential to yield as a side-effect of allocation is a sub-optimal choice for a side-effect-free language... I presume there must be an explicit instruction also that permits a yield to take place?)
> although I'd argue that having the potential to yield as a side-effect of allocation is a sub-optimal choice for a side-effect-free language...
Preemption isn't a side-effect in the sense in which Haskell is side-effect free even in the single-threaded case, since timing isn't guaranteed to start with (and, particularly, a single-threaded Haskell program can be preempted by the host OS at any time, based on any heuristic applied by the host OS, and for any amount of time), and to extent that preemption effects semantics, it only effects the semantics of things like IO actions which are not, by design, side-effect.
> I presume there must be an explicit instruction also that permits a yield to take place?
Yes, Concurrent Haskell includes an explicit yield.
[1] https://hackage.haskell.org/package/base-4.7.0.0/docs/Contro...
Now the problem can be correctly rephrased as:
Why is it hard to get non-deterministic programs to do deterministic things.