Why Johnny Can’t Write Multithreaded Programs
blog.smartbear.com
blog.smartbear.com
No, no, no. If you are writing multithreaded programs, you _will_ have locks, period. The question is whether you explicitly use them or if they are hidden somewhere in your libraries, frameworks, etc. Actually, the latter are much more difficult to debug. Most of us have probably seen situations where deadlocks or data corruption has occured because of some extremely complicated interaction of message pumps - UI thread - callbacks - async operations - etc., without any explicit locking.
> Perhaps most importantly, modern programming languages and libraries make it easy to create a producer-consumer application.
Yes, that's great again, until the deadlock-corruption-indeterminism problem comes back again in a different abstraction level.
There is _no way out_. If you are writing concurrent apps, you have understand what's happening. By concurrent I mean concurrent on the level you are working on. Using a parallel 'map' operation is different because the concurrency is an implementational detail from your perspective. But if you are writing a massively concurrent quoting/trading engine, then you have to know what's happening. And if you do, then you're free to use locks, executors, async, whatever -- it's just a tool to solve the problem.
...
The more I look at this article the more ridiculous it seems...
Not necessarily. In scientific computing, it is common to encounter "embarrassingly parallel" scenarios where each thread can solve equal-sized chunks of the problem, and you can wait till all threads have terminated to collect results.
edit: Okay, the final wait is usually implemented with a lock under the hood. Nevertheless, this type of program is straightforward to reason about.
Oh wait.
Besides that, depending on the task, it's very important how something is implemented.
The presence of a lock tells you nothing about whether a program is well-designed. In fact, the whole idea that you can argue about the correctness of a program from the presence or absence of "code smells" is absurdly simplistic. I have seen plenty of bad code littered with while statements.
Incorrect use of abstraction levels, such as using tools that are too low-level and error-prone for the task at hand (as in the majority of business applications) IS one of those warning signs. It usually indicates a conceptual problem, and makes the code needlessly complex.
But wait, you don't use blocking-IO, you poll the sockets to see if there is data available, right? Do you realize what you are polling? (hint, it is global and mutable)
Certainly some systems (such as Java and multiple CPUs with independent caches) that use thread-local working areas, you cannot rely on a task being completed meaning that you can actually use the data it has produced, until you actually make use of a lock. The lock ensures that the local copy is synchronised with the central copy.
There's plenty of opportunity for fun if you don't use locks in some form or other in multi-threaded systems.
This type of program is an uninteresting corner case, that tells us nothing about the more general problem of reliably writing concurrent software.
This advice is written for the 90% of use-cases that can be solved with simple abstractions, where programmers are still spinning up threads and locking objects. Most application programmers don't do manual memory management, low-level network programming, graphics, and so on. Why should parallel programming be any different? That is the point I believe the author is making, and I happen to agree.
"Locks and other synchronization primitives are systems level constructs. People who know a lot more about multithreading use those constructs to build concurrent data structures and higher level synchronization constructs that mere application programmers like you and I use in our programs."
...which is probably true, but there is nothing scary about "systems level" stuff---even the author could probably tool up to do it.
That becomes a problem in the 10% of use-cases (which I suspect is more frequent than that) where the simple abstractions are not satisfactory.
You say that and then proceed to call the article ridiculous.
Well, I write and maintain large applications in Clojure. The code uses a multitude of threads for various purposes, with different lifetimes. And I've yet to see a single explicit lock. What's more important, though, is that I've yet to see a race condition, a deadlock, or data corruption, which I find pretty impressive.
I do agree that you need to understand what is happening — but I disagree with your assumption that the basic tools are all on the same level. They are not, which Clojure clearly demonstrates. I won't go into details, because Rich Hickey explains it much, much better than I ever will be able to — here's an example of his talk: http://www.youtube.com/watch?v=dGVqrGmwOAw
So comparing for example Clojure and C++ in regards to multi-threading Clojure will of course win, since C++ only recently got official standardized threading implemented and is far away from a really good concurrency support.
I think we need to distinguish between in-app race conditions (a primitive example is when you're trying to modify a data which cannot be written atomically), and situations where you have to maintain some order of operations because if you don't then the program won't work correctly _from the end-user's standpoint_. In concurrent programming safe operations are not composable, i.e. if you have >1 thread-safe operations then using those operations in parallel won't be thread-safe by itself).
What I tried to say is that as you increase the level of abstraction (i.e. build something useful using the great constructs of Clojure), if concurrency still exists on that higher abstraction level then you need to think about synchronization, again. And the problem you'll face is really similar to those low-level issues when you try to protect a 64-bit long data structure in C. That's why I encourage everybody to think about these simple toy-problems even if they specifically never come up when you write programs using modern tools.
Shared mutable data is handled by the STM in Clojure. The STM, in turn, relies on immutable data structures to work. Since data is immutable you can have optimistic locking. Reading existing state is perfectly safe even when a new state is being generated.
This article http://blog.enfranchisedmind.com/2009/01/the-problem-with-st... does a great job explaining why it's notoriously difficult to make a working STM in an imperative language.
That's true. I also agree that regardless of the language or libraries used one needs to be aware of concurrency issues and understand them. The world is concurrent and there is no way around that.
What I took issue with was the statement that you will have locks and even if they are in your libraries, they will come back to bite you. That is simply not true in case of complete languages/environments designed for concurrency. Clojure is one I know — and it isn't just a "library" that helps, it's the combination of language design, functional approach, data structures, immutable data and software transactional memory.
Incidentally, the words "thread-safe" are really hard to encounter if you write in Clojure. I would imagine it is similar in Erlang.
There's a grain of truth in this one. A lot of people think that multithreaded programming is like single threaded programming with locks added. This is not the case.
In my experience, with almost every mutex there should be one or more condition variables that are used to signal various things. A single mutex is almost never enough to achieve anything meaningful, because for every state you mutate, there's probably another thread waiting for that state to be mutated.
If you're working with a language or a framework that has some kind of queues and channels (like Go or Haskell, for example), they are probably more useful for lots of tasks than locks and conditions. Of course, someone has implemented those queues using locks and conditions, or atomic operations.
> We move data around, transform it, perhaps do some calculations from time to time, and finally store the results in a database or display them on the screen.
If it's just limited to this, then I could partially agree. But I can't agree at all to the following statement:
> There are difficult multithreading scenarios, just as there are difficult scenarios in the single-threaded world. But those are relatively rare.
Adding some "magic" patterns and guidelines won't make synchronization issues go away.
That said, if you aren't at that level you can almost certainly write lock free code (and you should) by apply design principals.
That is not true. Lock-free data structures exist and are applicable to many multi-threading use cases. For a super primer see https://en.wikipedia.org/wiki/Non-blocking_algorithm and if you are really interested, read about Transactional memory - http://dl.acm.org/citation.cfm?id=165164, and then "The Art of Multiprocessor Programming" (it is a text book) by Herlihy and Shavit.
Actually, there is a number of best practices that help you avoiding problems. For example, it helps to have a strict ordering of locks - i.e. everyone who locks on objects A and B, must do so first on object A. As a corollary, you should not call a callback or notify a listener while holding a lock - because you don't know what it will do. These two simple rules together already help a lot - even without understanding every possible state.
It's clear from the article the author means low-level locking primitives.
I've done a lot of multithreaded programs, and, yep, you have to use some good practices to avoid making the code explode. You know, having to learn them and stuff is why they are "difficult". Just because you know how to get something done does not make that "easy". That's what experience is for.
Unless the language/framework/library has automatic serialization and copying of objects, or automatic pointer ownership transfer when put in these magic queues, the problem is still there.
I like to drive the point home with this (slightly hyperbolized) statement: X already does this, and those folks need it to be good if they want to eat, so why the heck are we doing it ourselves?
But someone has to do the 'hard' parts, and do them well, and I don't see why competent tech folks shouldn't at least be interested in that.
Some people, when confronted with a problem, think, "I know, I'll use threads," and then two they hav erpoblesms.
For reference, the language was Erlang, which I believe has the best handling of threading that I've encountered so far.
I think you can learn how to program multithreaded code well without that, but you'll learn a great deal faster if you use a language that kicks you in the face every time you do something stupid (or simply doesn't let you do it). As in, potentially an order of magnitude faster. Fast feedback is non-linearly better than slow feedback.
Though this does assume you get to greenfield the multithreaded code. Woe betide ye who have to retrofit existing poor multithreaded code. I don't even know what to tell you, except you have my pity.
Building multi-threaded applications with functional programming forced me to write pure functions - or close enough, Erlang does have some side-effects but this is just to make it more useable than the mostly academic Haskell.
I've carried this approach into C# and Java, and typically end up with methods that fit a multi-threaded paradigm by default because of their lack of state. As a freebie, they can be effortlessly unit tested by mocking their direct parameters and testing the return values (no need to mock or test state).
There are lots of corner cases that you might overlook when writing multithreaded code, and some of them will only ever happen if the threads get scheduled in a particular manner.
Multithreaded software development is not easy, partially because in the past we've acquired practices that don't work very well in multithreaded world. Partially because it's a whole new world which is not thoroughly explored and established best practices do not exist.
But all in all, too many people are afraid of multithreaded code and this is holding us back. It's not scary or difficult, it just requires a more rigorous approach at times.
Writing a background thread that can be cancelled immediately, that gives useful progress information, that doesn't leave other threads indefinitely blocked if cancelled, and that cleans up after itself if cancelled? hard.
For my single-threaded code I have great static analysis tools, IDE magic, and testing frameworks. For my multi-threaded code, I'm on my own...
That's a big point. The tooling for parallel code is developing really slowly compared to the proliferation of multi-core processors. Most of it seems to be "we'll make the library multi-threaded but all your code will still be single-threaded" like we see in Node.
The majority of developers aren't going to be systems developers, though. Just as the majority of developers don't use assembly language either.
There's a certain thinking style you bring to writing and understanding concurrent software. You need the ability to "visualize" the contexts, behavior, and data access. You need to see the possible race conditions and understand what resources need to be "protected" and how.
Reminds me of recursion. Back in my CS days, it just made some people's heads explode. They couldn't think in a nested fashion to understand what was going on at various recursion levels, nor what was required to terminate, what should be returned, etc.
Like-wise with proofs in geometry. Some people just couldn't get there. But, for those who could, it came without too much effort.
You kind of either have it or you don't. You can practice and improve, but some people just naturally "get it". So, I don't think it's as simple as "they learned the wrong approach". In fact, if they truly understood the concepts and possessed the requisite thinking style, they would be able to identify the "wrong approach", and the right one.
Well no. It is like saying mt programs are broken because the user didn't know how to write them. It is not saying much. Everything with bugs is broken because the writer didn't know how to write it.
The reality is that multi-threaded is hard because it is hard to reason about and hard to get right. In one large application it only takes on junior programmer to dip their fingers in and add that one module that will crash the system 1 out 1000 run on customer's hardware only.
MT issues and problems on a whole new level of difficulty that is qualitatively different than what single threaded programs experience. Sequential problems and bugs are still there, but now there are a host of completely new things happening.
> These programs very often fit nicely into a producer-consumer model with three threads:
* The input thread reads data and places it on the input queue.
Well, you also have to make sure the queue is thread safe. Understand what does it mean to get an item off of an empty queue. Now you have queue-using-up-all-my-memory problem if you do stream processing with mis-matching processing rates between parts of your programs. What about objects you put in the queue. If those have any pointers or are pointers themselves now you are back to the original problem. So make sure objects are copies, are serialized/deserialized or there is proper ownership handoff.
In summary, is it possible to write correct highly concurrent programs in a shared memory model with threads/and-or/events -- yes. Is it easy? No, it is not easy.
The article correctly points the often common fallacy that using event/callback-based single threaded approach is superior and avoids all the concurrency related issue. It doesn't avoid all issues. Now the race is between callback/errback chains instead of threads. Granularity is much higher (if incrementing a shared 64 bit int is fine without a lock). But the need to protect shared data structures is still there. The danger is psychological because one thinks "hey this is safe, I don't need anything to worry about"
That is why I believe it is better to use a language/system/framework that uses isolated heaps and rigidly enforces separation between concurrency units. Erlang has that, D has some of that, Nimrod, Web Workers and Dart isolates to that. You incur a speed penalty for that. Don't be shy about using regular Unix OS processes. Those are great for isolation and do it well. The cost of IPC and cost of creating them can also be high. You in incur a penalty for copying data between concurrency units, but remember, there is a bigger penalty you incur when the program has crashed. The converse of that is, the biggest performance gain your application will achieve is when it goes from not working to working and staying working.
Correction: It's not easy in most programming languages, because most programming languages fail at implementing mutual exclusion in a way that is safe. It's basically the same problem as buffer overruns in C, where indices don't get checked (except that in the concurrent case, most languages don't require you to associate a lock with shared data and/or don't verify that you hold the lock before operating on that shared data).
Per Brinch Hansen's famous rant gives the gory details [1]. The basic technology had been figured out in the early 1970s.
[1] http://cse.unl.edu/~witty/class/csce351/howto/PBHansenParall...
Enormously greater complexity has the side effect of making execution slower. Something to think about. Converting a fast executing and quick to write/debug and reliable single threaded app into an inherently slow executing and slow to write/debug and unreliable multithreaded app needs an extremely good reason outside of the tradeoffs listed above. Those situations do exist, but situations like "I thought it would be fun to put multi-threaded programmer on my resume" happen more often.
Its kind of like using "goto". If you don't really understand everything about the topic, its probably a wise choice to always avoid.
I think that's key.
The primitives of multithreading aren't difficult, nor are the basic concepts. What is hard for most people is thinking about it in a meaningful way.
The mental model for single-threaded programming is challenging for many - you essentially run the program or subset of the program in your head (at least, if you're any good). This includes all branching and jumping, and effectively requires maintaining one or more stacks among other things.[1]
To fully conceptualize multi-threaded programming, programmers need to be able to expand their mental model of the executing application. Not holding one stack, but N. Awareness that each may (and likely will) differ slightly. Awareness of other actors. Awareness of exactly what is shared, and what paths lead to its modification. Being able to visualize (for lack of a better word) which others may interact with the shared data, and under what circumstances. All of this comes into play when you add just a second thread executing the same code - it gets considerably more complex from there. The closest analogy that comes to mind is the shift from thinking in three dimensions from two, or four from three.
It is not impossible to reason about, nor is it impossible to build such a mental model. But it is hard. And it does take practice.
[1] And even this basic ability seems unfortunately uncommon.
I think his focus on “global mutable state” is a bit of a red herring. It makes no difference whether the mutable state is global (protected by a lock) or owned by a single thread. You can refactor all your synchronized {...} blocks and replace them with executor.execute(futuretask); futuretask.get();, where executor is a single-threaded event loop and futuretask.get() blocks for the operation to complete. This refactoring would make a single thread the owner of the state, but there would be exactly the same number of deadlocks. Conceptually, you can think of your critical sections as a separate thread on which you invoke methods and then block until completion.
After refactoring to use Executor and BlockingQueue, one still has to make sure there are no cycles in which threads are allowed to block waiting for which other threads.
Ideally, we need an API that allows selective data sharing, so you greatly reduce the chance of one thread trampling over bits of another. Right now, the common way to do that is with multiple processes and shared memory regions, but it is cumbersome to set up and requires the programmer to treat the shared data very differently (e.g. one process can't just malloc data for a string, say, and then let the other process access it.
The other route is through message-passing, but again you have to write your code in a totally different way. Someone please invent multi-threading with selective sharing!
Bzzt full stop epic fail. Think about the other discussion today about the "naturalness" of zero or one based arrays.
If multithreading was natural and inherent part of all noobs, you'd teach programming beginning with multithreading and maybe later on you'd have some weird module which confused most of the class explaining how some legacy languages and systems only allow one thread which has certain unusual programming constraints that most of the class would screw up. Also all automata theory classes would begin with the eNFA as the base class and later on tell the kids about DFAs being broken forms of a NFA and all that. I'm just not seeing it.
The article did fail at architectural level. Most non-threaded programs can't be upgraded to threading because either its not worth the effort or its impossible to solve the actual problem without threads so the postulated single threaded solution can't exist therefore you can't upgrade what could never have been implemented. Why are you multi-threading?
Most likely if you're adding multi-threading explicitly to a single threaded app for an inherently multi-threaded problem, you're going to spend all your time figuring out how the single threaded part exploited some other component of the entire system to create a psuedo-multi-threaded app. Perhaps it relies on the OS to spawn multiple clients in a client server arch where all the processes live on the same CPU or something. The problem isn't just adding a thread so you can checkmark a marketing box that its now a multi-threaded app so someone can collect an end of year bonus, the problem is you need to scrap the whole thing and start architecture work from first principles.
Another funny part was the natural assumption that all programs/projects will be huge enough to contain at least two completely non-interacting subsystems so no global state is the ideal. That's a dumb architecture design or business decision. Lets think of an example where you would have threads with no global mutable state. How about a tetris implementation in one thread and an enterprise rational DBMS system in another thread and an IRC client in another thread, all in the same program/project. That's just a dumb architectural idea, make totally separate projects. Make the smallest usable debuggable tools and use them together, not the largest undebuggable swiss army knife the world has ever seen.
What would be useful examples? Multithreaded video decoding? Scaling out calculations to multiple cores?
Actually, I prefer to think that the reason multi-threaded programs are harder to write is because it's harder to compose components together. If I have a regular old function and another regular old function and compose them, I get a regular old function and I know that it works how I expect it. With two multi-threaded functions, then I have no guarantees anymore. If I cannot take simple components and combine them into more complex ones, how am I suppose to write correct code? Sorry, but I'm just not good enough.
"There are difficult multithreading scenarios, just as there are difficult scenarios in the single-threaded world. But those are relatively rare."
Is this some sort of flame bait?
Contrary to the growing popularity of message passing concurrency, modern commodity hardware is not massively parallel and jamming massively parallel algorithms on top of it generally is a mismatch. You are almost certainly better off having a few well defined threads that are fast than unbounded threads that are slow.
(I know this isn't quite all there is to the problems of multithreading, but it's a very high percentage indeed in almost all applications.)
A multi-threaded program that doesn't need to share state probably isn't the usual case, not from my experience anyway.
Locks are not evil, think of a railway station, there are sections of track that must be shared by multiple trains.
I would have appreciated an article on the various "libaries" we should be using instead.
"Probably the most important lesson to be learned from the past 60 years of software development is that global mutable state is bad. Really bad."
This represents a misunderstanding about the badness of global variables and the goodness of encapsulation in my mind. Mutable global state is an unavoidable necessity to ship your app - every single pixel on your screen is a bit of global mutable state. I won't dive to far in here, but I cringe everytime I see these fancy pants words applied because its pretentious /and/ trivially measurably wrong (see everything on your monitor right now).
That all went away when I discovered Zero MQ (http://zeromq.org/intro:read-the-manual). The manual claims:
"If you've spent years learning tricks to make your MT code work at all, let alone rapidly, with locks and semaphores and critical sections, you will be disgusted when you realize it was all for nothing."
It's not exaggerating. ZMQ's multithreading is marvelous. No mutexes, no locks, no semaphores, no critical sections, no load problems - just perfectly scalable threads that work with any language on any platform. In fact it's so cool, that if you don't have a problem that needs multithreading, go out and find one.
Understanding when and how ZMQ does this is very important for optimizing throughput.
The main pain with learning threading is you have to wrap your head around the principles of it - which are fairly foreign - while at the same time battling with the very strange and frustrating errors because it's so easy to get wrong. ZMQ teaches you the principles without the errors after which you can go master the low level bits if you wish.
So what? There are all sorts of successful language and computing models which are light years removed from threaded shared memory. Message passing without sharing state, except for some lock-free primitives, is bloody brilliant for very scalable concurrency - as Erlang has shown us for coming up on 30 years now.
"The advantage is more being able to go from threads to processes, then to the network, easily."
That's the raison d'etre for ZMQ to be sure. But very pleasurable multithreading is a massive advantage too. If it scales out to nodes as well, so much the better.
"That advantage is just as useless to most applications as threading is to achieve concurrency (rather than parallelism)."
Threading using ZMQ message passing is a superb way to achieve concurrency (given that this is the real world and we can't all rewrite our apps from scratch in Go or Clojure). I'm a threading beginner and I've got video decoding, graphics handling and networking for a real time app all in separate threads going great guns without falling over or messing each other around - on a very low spec machine too I might add. On a four core workstation, all threads get a whole core to themselves no problem.
Try it. You'll like it :)
I'm not discrediting that operating between threads is a handy addition to ZMQ, but using it for communication between threads seems like a lot of work (moving to that message passing model) if you never intend to leave one process.
I do happen to like messaging, but when your data becomes complex it's a right dog...you're now in the world of protocol design.
OK, now I think you're trolling, perhaps by cutting and pasting from random technical manuals. What you said there makes no sense at all. Could you paste some example code please?
"A coroutine library will get you even more flexibility if you just want to setup pipelines."
Now I know you're trolling. Coroutines are completely useless for real concurrency like decoding audio and video in the background simultaneously - because only one coroutine can be executing at the same time.
"If you want greater scalability, there are lots of non-blocking I/O event libraries (libuv/libevent/boost asio). None of these solutions involve moving to a message passing model."
What if I don't really care about I/O? What if I have a small program that needs to use multiple threads on multiple cores to efficiently search a large problem space while doing video decoding in the background and having a responsive UI? I must just link to Boost? Er, no thanks.
"I'm not discrediting that operating between threads is a handy addition to ZMQ, but using it for communication between threads seems like a lot of work (moving to that message passing model) if you never intend to leave one process."
Compared to getting synchronization right, optimizing critical sections, debugging random failures under load, it's trivial.
"I do happen to like messaging, but when your data becomes complex it's a right dog...you're now in the world of protocol design."
I'm going to assume that you're still in school or not actually a programmer. ZeroMQ is used by AT&T, Cisco, EA, Los Alamos Labs, NASA, Weta Digital, Zynga, Spotify, Samsung Electronics, Microsoft, and CERN (I grabbed this list from its front page). CERN just published a report in which it evaluated ZeroMQ for a custom middleware solutions running 4000 server processes communicating with 80 000 devices for a total of 2 000 000 I/O points that could be queried. It aced the requirements. Erlang has used message passing for decades in the telecoms industry which has enormously complex data and unique realtime, distributed requirements.
Protocol design is easy. Main thread creates child. Child loads video and reports its ready. Main thread sends START. Child thread receives START and starts. Child thread reports DONE when done. Was that so hard?