Concurrency ≠ Threads

Here’s a conversation I seem to be having over and over these days:

Someone else: Computers are getting more and more cores. So, we need to thread our software to take advantage of them.

Me: But threads (the Dijkstra style shared-state-with-locks-and-mutexes-and-semaphores-oh-my variety) are almost impossible to get right, and when they’re used in other than the simplest way, its easy to get random deadlocks that happen every few months/years.

Someone else: Computers are getting more and more cores, so we need threads.

Me: But there are other forms of concurrency. Processes that communicate using files, pipes, sockets, or even shared memory. Or software transactional memory (hell, people use databases for IPC now, so STM can only be better), or message passing.

Someone else: … ?

A few days later:

Someone else: Let’s talk about how to multi-thread our code.

Sorry people. As Sutter and Larus say:

“humans are quickly overwhelmed by concurrency and find it much more difficult to
reason about concurrent than sequential code. Even careful people miss possible interleavings among even simple collections of partially ordered operations.”

And as Edward A Lee says:

“[Threads] discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism.”

[Clever summary encouraging people to understand concurrency more closely.]

Advertisements
This entry was posted in Random Thoughts. Bookmark the permalink.

19 Responses to Concurrency ≠ Threads

  1. Steve Laniel says:

    Knuth agrees with you.

    I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the “Itanium” approach that was supposed to be so terrific—until it turned out that the wished-for compilers were basically impossible to write.

    Let me put it this way: During the past 50 years, I’ve written well over a thousand programs, many of which have substantial size. I can’t think of even five of those programs that would have been enhanced noticeably by parallelism or multithreading. Surely, for example, multiple processors are no help to TeX.[1]

  2. John Cheng says:

    I took at the “other forms of concurrency” links, but I did not find out what there other forms of concurrency are.

    Assuming that programmers need to rewrite their code to take advantage of multiple cores, what is the way to do that without using threads? If programmers do have to use threads, what are good/safe way of using it?

  3. Joel Becker says:

    Viro’s Razor:

    Any race condition, no matter how unlikely, will occur just
    often enough to bite you.

  4. foobar says:

    There is nothing wrong with threads, actually, and there are ways to organize your multi-threaded application that avoids a lot of the pit-falls.

    Firstly, shared memory isn’t really workable for languages like Python. At least not if you want to share anything but byte-arrays with other processes. You can’t have your arbitrary objects or data structures in some specific piece of memory just like that.

    Secondly, using IPC to share data structures is always ineffective, due to serialization, copy operations and such, which are required for this sort of thing. It might work for small messages, but larger objects or data sets? Don’t do it…

    Thirdly, while admittedly getting mutexes and properly shared data structures right … you would have the same problem even if you’d use shared memory between processes! You will need a form of mutex then as well, you know? So, using processes rather than threads in that case didn’t buy you anything at all.

    Lastly, while not suitable in all cases, there are ways to communicate between threads in a thread-safe manner without you ever having to deal with mutexes. Uses a an in-memory queue object, which performs all its operations in a thread-safe manner, and you will be able to send messages (short ones, or consisting of very large data structures) to other threads without any copy or serialization overhead at all.

  5. Chris Wenham says:

    Ideas can’t be manufactured by thinking really hard or having someone wag a finger at you, but that said, the hardware manufacturers are still providing very good ideas even today.

    During the 80s and 90s the types of ideas they were having were the ones which give software developers the famous “free ride”. Now the new ideas are different; they’re about how to expand transistor counts in three dimensions rather than two, for example, and how to solve the cooling problems that come with it.
    Many software developers have already figured out how to solve certain kinds of problems in parallel without any problems getting concurrency to work smoothly.

    Some of these techniques are being built into the major frameworks, now. I’ve been using Parallel LINQ extensions for .Net to write programs that perform atomic, CPU-intensive operations on large collections of objects in parallel without running into synchronization problems.
    One example is computing or validating cryptographic signatures on large numbers of messages. On an 8-core server I can have all cores churning on this by adding “.AsParallel()” to a single LINQ statement.
    I can also do the same thing when applying fraud-detecting business rules to batches of incoming orders. An individual order is evaluated on a single thread, but I can evaluate 8 orders simultaneously, or 16 if I had that many cores, or 32.

  6. Shawn Fumo says:

    I’m surprised no one has brought up Clojure yet. Hickey brought up a lot of similar points (like locks being almost impossible to get right) in his screencast on concurrency:
    http://clojure.blip.tv/file/812787/

    The language uses STM, immutable data structures and various other things to help with these issues:
    http://clojure.org/

    Obviously that isn’t a panacea, but it’ll be interesting to see where the hardware and software goes in the future.

  7. t says:

    This is so true. I’ve been having these conversations so many times it’s ridiculous. People keep saying, “Use threads! If execution is done at four points at the same time, then it’s bound to go faster!” And I try to explain the same old story: when state is shared, a thread won’t even give you as much as you’d think.

    Let alone the horrible code threads can produce. It’s just insanity. No, the future is *not* threading. It’s with one of the other ways, my favorite is message passing but that’s me.

  8. kieran hervold says:

    I agree w/ Chris Wenham — some applications don’t easily lend themselves to parallelism, but many do. Certainly graphics have benefited from massive parallelism, and scientific computation offers innumerable examples: curve-fitting data from 1,000 independent samples, aligning to a genome that’s been divided into 1,000 different chunks.

    I don’t believe that every instance of parallelism has been identified and exploited quite yet.

  9. martin says:

    John Cheng, yeah, I didn’t do a great job of anchoring the links in the text. A better link is this one, a different section of the same chapter.

  10. martin says:

    Hey Steve, good to see you again, sorry I didn’t get a chance to say goodbye when I left ITA.

    I hadn’t realized that Knuth felt the same way; thanks!

  11. martin says:

    Joel Becker, I like that quote. 🙂

    foobar, good points, I hadn’t thought about these details, e.g. that most garbage collected languages don’t let the programmer specify where objects go, so you can’t put them in a shared block.

  12. martin says:

    Chris Wenham and kieran hervold, the applications you describe are data parallel (if I understand them correctly). This counts as an example of a “simple” application of threads; I did this for my Ph.D. thesis. You might want to check out MapReduce.

    The irony is that shared state threads are only manageable when the interactions between threads are relatively simple. As foobar points out, the alternatives aren’t necessarily much better. “Oh well.”

    t, glad to hear I’m not the only one.

  13. Andrew says:

    One Word: Erlang!

  14. Brett Morgan says:

    I seem to be having the same conversation. Whether the end point be erlang, scala w/actors, haskell w/stm, or AppEngine style everything in a transactioned datastore.

    The part most people seem to be having difficulty accepting is that pretty much everything we’ve done up until now needs to be re-done to expose the underlying concurrency explicitly.

    Pretty much everyone i speak with is still assuming that some bright spark somewhere will come up with an automatic method for computing out implicit concurrency from our current code base.

    I don’t know whether to be depressed at the lack of acceptance, or upbeat at the knowledge that there is a killing to be made here. But then, memory management took a generation to get generally accepted…

  15. narag says:

    I think that the question here is what are we going to do with extra computing power that those wonderful multicore cpus are bringing.

    It would be idiotic to take a simple straight-forward task and make a complex multithreaded task of it. But right now we deal with mainstream multi-something software: TCP/IP servers that don’t make our lives so difficult. The complexity is buried in the server core and then application programmers write sequential code in some high-level language, not caring to much about synchronization.

    Something similar could happen with other types of environment. Programs would work pretty much the same as current ones, but threads would be used to manage whole subsystems: a 3D interface, spellchecker, voice or shape recognition, generating additional information anticipating users’ desires… everything “pluggable”. The main program would be as simple as it is now.

  16. Aaron says:

    “””The part most people seem to be having difficulty accepting is that pretty much everything we’ve done up until now needs to be re-done to expose the underlying concurrency explicitly.”””

    I don’t know, if think about most computers (i.e. desktops) they usually have at least as many processes running and doing stuff as they have cores. If each process is assigned one core, and does its own thing, there is no real reason to spend a lot of time rewriting all those apps.

    Its only in really computationally intensive code that we can see a performance increase from using multiple cores. Or in systems where there is only one or two active processes (i.e. not desktops).

  17. Paul Houle says:

    Threads are one model. They’re also a foundation that other models can be built on.

    Personally I’m excited about what we’ll be able to do with parallel systems. We’re going to see a huge increase in processing power over the next decade, and many of the promises of AI will be fullfilled. It’s time to quit bitching and start building.

  18. Nick says:

    Sure, there are other ways to achieve concurrency, but there is no doubt that at least in the short term future, for better or worse, threads are going to be a big part of concurrency. And that means developers are going to have to learn how to correctly program with them.

  19. Some software systems can take advantage of lots of cores very easily. The airline reservation system we’re doing at ITA Software has a big cluster of processes that handle requests, each independently. We run one per core, and it all works great: no sharing at all.

    But for cases where you really do want sharing, there is a very strong trend in computer language design right now for languages that are either purely functional (a la Haskell), or that are mostly-functional and have transactions as the basic concurrency primitive. Transactions are far easier to reason about than locks, which is why we’ve been using them in database systems for so long.

    Anders Hejlsberg (the C# creator) talks about this extensively in recent interviews (also see the F# language). Bill Venners talks about this re Scala. Erik Meijer, Steve Vinoski, and Guy Steele (developing Fortress at Sun Labs) all say the same thing.

    Lisp is dear to my heart; I ran the International Lisp Conference 2009 recently (ilc09.org). The Next Big Thing in Lisp, the dialect that has by far the best chance of becoming the major Lisp used for serious software purposes (Scheme is likely to stay big in education and theory work) is Rich Hickey’s Clojure (mentioned in an earlier comment). Clojure also uses this same philosophy.

    I am 100% convinced that this is the way things are going. We will all be programming this way soon, if we want high-performance, correct software that takes advantage of many cores (in ways other than the simple one we use now at ITA). I am learning Haskell and Clojure, and I recommend that to all my colleagues.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s