I was going to write a blog post flaming this blog post, but I’ve change my mind. The only real sin he’s committed is making up his mind before all the facts are in my opinion.
But I don’t think he’s right. Not because message passing is bad or is going to go away- it’s not. It’s that it’s not a case of either or. The more I think about it, the more I think the future is going to be a combination of STM and message passing. Both have their advantages and disadvantages.
The advantage of message passing is that it’s distributable. You don’t care if the other process you’re sending a message to is on the same CPU or the other side of the planet, it doesn’t matter. The disadvantage of message passing is that it requires, at minimum, at least one copy of the data, and often multiple copies of the data. Plus task switching and cache flushing. It is heavy weight, at least compared to STM and shared memory multithreading.
This is a non-trivial problem. Parallelism comes in a gradiant, based on how much data needs to be transmitted between the processing elements per time period. One on extreme end of the gradiant you have very little data that needs to be distributed. The gold standard here is stuff done by distributed.net takes on- brute force crypto key searches and the like. We’re talking about a few hundred bytes every couple of days. This makes it trivial to distribute the computational load over widely dispersed machines.
Note that this also explains why supercomputers died in the 90’s, but big iron database servers didn’t. Supercomputers were, at heart, about solving either large numbers of small linear algebra problems, or a small number of large linear algebra problems. In either case, the problems were fairly easily distributed with small communication demands- a few megabytes per second- that supercomputers could be replaced by racks of PCs communicating via ethernet. Databases, however, require more communication between nodes (especially if you want to parallelize a single query, or allow multiple queries to access the same table simultaneously), and as such didn’t distribute via ethernet. So Sun and IBM are still profitable, Cray and SGI are dead.
Distributed databases are possible, for at least some workloads, I comment (before half a dozen people do). The problem is that only certain types of workloads distribute- write a query that doesn’t distribute, and all your work has to be done on a single box. Which is why they haven’t caught on- and Sun and IBM are still in business.
The problem is that everything needs to be parallelized. But being distributed isn’t quite as big an issue. What’s driving the sudden obsession with parallelization is the sudden appearance of multicore chips. But notice something about the multicore chips- how close the CPUs are to each other. Often they even share cache. If two processes can share a data structure by just sharing a pointer to the datastructure, communication speeds are nearly infinite. This allows for multithreaded programs that have incredibly huge communication requirements. Tightly coupled programs are possible in this environment.
Tightly coupled parallelism is most likely to arise with some form of automatic parallelism. I think the fullest power of STM will be found in a Haskell-like purely functional language (with STM built into the monads automatically, meaning you can’t accidentally forget the STM) combined with cilk-style microthreading. Lazy evaluation and parallelism are very similiar concepts- both are dealing with asynchronous computation. Lazy evaluation moves the computation to the first time the value is needed, while parallel evaluation the evaluation happens (conceptually, at least) in parallel. But this level of sharing requires very tight binding, very high communication rates. But I’m not doing a lot of computation per byte of communication. This is even more the case if the different CPUs are, in fact, running on an SMT CPU (aka Hyperthreading by Intel).
I actually think that a lot of problems will be ameniable to both levels approaches. Do message passing, ala MPI or Erlang, at the top level, breaking the problem up into big chunks which can then be distributed over a local network or a highly non-uniform ccNUMA architecture. But then each chunk is solved in a microthread+STM approach, allowing for good utilization of local resources and tightly coupled parallel processes.
As a side note, the “emergent complexity” he worries about having with STM is also a problem with message passing. Emergent complexity is always a problem- and the fundamental simplicity of the individual components doesn’t help (much). And, unlike STM, message passing does admit the possibility of a deadlock- thread A waiting for a message from thread B which is waiting for a message from thread A. It’s much less likely than in the classic (and unarguably awful) threads+locks paradigm, but it’s still possible. The only advantage message passing has over STM in the emergent complexity department is that it encourages bigger chunks per thread (due to the relatively high cost of communication)- fewer interacting components means less emergent complexity.
But fewer interacting components also means less parallelism, and less performance on future hardware. The new Moore’s law is that the number of cores will doubly every couple of years now. However parallel you program is today, it’ll need to be twice as parallel in a couple of years- and dozens to thousands of times more parallel in a decade or so! Actually, the situation is even worse than this. Once multithreaded programming becomes common, the new performance metric will be performance per transistor. If I can trade off 10% performance and fit the CPU in 1/5th the die size on the same process, I can fit 5 cores where 1 used to fit and the CPU is 4.5x faster for programs that can take advantage of 5 cores.
Of coruse, 5 cores doesn’t mean I get 5x the memory bandwidth. It actually becomes more important in this case to be tightly bound, so gaggles of threads can share cache efficiently. Five threads all talking to memory and not to each other would die on performance. On the other hand, this also means that moderately size machines will start being more non-uniform in the memory architecture. Talking to the thread on the next core over is very cheap- but talking to that thread microseconds away is painfull and slow. The former is a job for STM, the latter for message passing.
That said, I could be wrong. I know what damned well doesn’t work, but I don’t know what does work yet. One good thing does arise out of this debate, I comment. Wether it’s Erlang and message passing, Haskell and STM, or some hybrid, it looks like the solution is going to be functional programming plus something else. What really drove the adoption of OO programming was GUIs. Note that Doug Englebart was one of the inventors of OO programming at the same time he was inventing the modern GUI interface. Heck, the first Smalltalk dates from 1972. But it wasn’t until GUIs hit the mainstream in the mid/late 80’s that OO programming also took off. In a similiar way, I think parallelism is going to drive the adoption of functional programming. Which will be for the betterment of programming in general.
19 Comments
There has been a good deal of progress towards deadlock free message passing. Check out Mark Miller’s thesis (section III is the part the focuses on this area, though all of it is a very good read).
I actually can’t see what the functional languages can add to this “concurrency problem”. At first it’s not an unsolvable problem. Multiprocessor machines aren’t new, and there are a lot of applications which can use all the processing power.
The messaging paradigm have a lot of implementations:
c++:
http://www.twistedsquare.com/cppcsp/docs/index.html
python:
http://www.stackless.com
A nice article (c++,2003):
A C++ Producer-Consumer Concurrency Template Library
http://www.bayimage.com/code/pcpaper.html
Yep concurrency isn’t easy, but programming alone isn’t easy.
Good post. It’s nice to see something balanced on this topic.
I think the most irritating part of Logan’s post was when he said that STM would be the worst thing that could happen to the industry. Nonsense, the worst thing would be if we all continued using locks! Either STM or message passing would be a huge improvement over the current state of parallel programming in mainstream languages such as Java or C#.
A thoughtful post, and a nice change from what is rapidly becoming a flame war. Thanks.
The message passing paradigm and associated middleware are definitely strengths for Erlang. I believe that the HiPE compiler also tries to keep message data in a shared heap to avoid copying.
STM, on the other hand, is a strength of Haskell. I can’t see STM working in an impure language because it will be too easy for programmers to forget the atomic blocks, or alternatively too hard for the compiler to work out which data might be handled without the transactional overhead.
To Teki: functional programming brings a lack of side effects. In both Erlang and Haskell they only happen in limited circumstances. Haskell in particular controls them with the type system: each kind of side effect has its own type (e.g. one type for IO side effects, one for parsing side effects, etc.). So IO side effects can be separated from the side effects within a transaction, and the only way to convert from side effects inside a transaction to side effects outside is with “atomic”. Meantime most computation is done with “pure” functions (no side effects at all), so no transactional guarantees are required in them.
Paul.
Jack: thanks for the link, it’s gotten added to my reading list. I’m willing to bet dollars to donuts, however, that the solution involves limiting who can send messages to whom- i.e. it’s not legal for both a to be able to send a message to b and for b to be able to send a message to a. This strikes me as being a potientially severe restriction on the paradigm, although I can’t think of a case offhand where it’d really be a problem.
Teki: one good point I forgot to make was that an advantage message passing has is that it can be bolted on to a language after the fact as a library. Witness the success of MPI- which is effectively what enabled racks of PCs to kill the supercomputer. I’m not sure if I stated it explicitly, but my basic conclusion was that the C++ parallism committee would have been better off to adopt on the message passing proposals. Unfortunately, they’re headed straight for threads & locks land. IMHO, it is beyond arguing that message passing is way better than classic threads & locks programming.
As for the comment that multithreaded programming isn’t new, you’re right- but until now, it’s been rare. It’s been rare because generally it’s been optional- with a few exceptions, most programs didn’t need to be multithreaded to take advantage of CPU speed gains. If, in 18 months, a new CPU will be out that will run your current single-threaded code twice as fast, it isn’t worth it to multi-thread your program. And computers with more than 2, maybe 4, processors were rare outside of the machine room.
That isn’t true anymore. Now, if you want your program to go faster anytime this decade, it had better scale to multiple processors. Multithreading isn’t the option it has been for the last several decades.
As for the advantages of functional languages- above and beyond the normal advantages functional code has even in non-threaded environments (shorter code, fewer bugs, faster development, etc.), functional programming has several specific advantages in a multithreaded environment.
First, and most importantly, immutable data structures don’t need to have acces be synchronized. This is what I was refering to when I talked about sharing a single pointer- hey, here’s a pointer to a whole huge data structure. But since it’s immutable, and neither one of us can change it, we don’t need to worry about who is accessing it. Expensive locks and copying aren’t necessary.
Second, and almost as importantly, purely functional code can be aborted and restarted. Just drop all the half constructed values on the floor for the garbage collector to pick up and retry. Haskell/STM uses this explicitly- transactions are aborted and can be retried, and I think Erlang uses this to restart failed processes (but I’m not sure). You can do this with imperitive code, but it’s more more risky and error prone. Basically, all the code has to be transaction-aware, and transaction-beware. Which is why, for example, I doubt you’ll see Ocaml/STM.
Thirdly, pure functional programming with strong static typing allows you to provide correctness gaurentees. For example, it’s impossible in Haskell to forget to put mutable state in a monad. Monads are the only way you can get mutable state. So if all monads are transactional, all mutable state is transactional.
There are probably more advantages, but that’s what I can think of at the moment.
As a side note, I think it’d be interesting to see STM used in an operating system context. It’d have to be used carefully, but it would solve some hard problems, such as priority inversion, in a neat way. A lower priority process could stay lower priority and just start modifying STM variables. Then, if a higher priority process needed in, it could simply abort the transaction of the lower priority process, then do what it needed to do. Implemented carefully you could provide realtime gaurentees. The way to solve priority inversion at the app level is to not have priorities, IMHO. But that’s a different rant.
Neil: Yeah, the original article was pretty much an Erlang advocacy, and not a very well done one. Lots of jumping up and down and yelling “STM bad! Erlang good!” Which is about par for the course for language advocacy. Yeah, I know- this blog has a special section called “C++ sucks”, primarily because it’s a topic I tend to harp on. But I try not to just say “C++ sucks”, I try to say “C++ sucks, here’s how, here’s why, and here’s how it could be done better”.
I am research student and the people on my floor are in two distinct camps: 1) multi-core is going to force people to embrace functional programming as parallelism is trivial, 2) existing languages will be retro-fitted to deal with the new problem. I am in a third camp. I think functional programming and OO programming will start to merge.
The truth is that there is no bullet proof solution to the parallelism/concurrency problem that works in all situations. Erlang shines in distributed systems. STMs are hard to implement efficiently. Both have not really been battle tested, to my degree of satisfaction :P, on multi-core client-side Windows/Linux applications in the “real world” It will be interesting to see what happens in the mainstream; mainstream to me being Java, C, C# and the like.
Paul: You’re exactly right on STM. If you have on peice of mutable data that isn’t transactional, welcome to hell. If you change that mutable data, and the transaction aborts, what then? The change remains in place, even though the rest of the transaction “never happened”, and may be tried again. This will cause incorrect behavior (aka “be a bug”) for sure. For STM to work, it has to be pervasive.
Which is why I don’t hold any hope that STM will come (in a usefull way) even to languages like Ocaml. And sure as heck not to languages like Ruby, Java, or C++.
My pragmatic side is saying that I shouldn’t bother with the topic, but I like to search better solutions to handle complex things more easy.
So my next question :).
Why does C++ have to support any kind of parallelism at all explicitly?
I like the way that OpenMP is dealing with the problem.
> I try to say “C++ sucks, here’s how, here’s
> why, and here’s how it could be done better”
I don’t think that C++ sucks. I agree on that a lot of things can be done easier. But I am not sure that everything must be solved in C++.
Teki: Let’s turn that question around for a moment: why the heck do we need C++? What does C++ give us that good ol’ fasioned C doesn’t? Objects? C has structures of function pointers. A little more clunky, but not much. I’ve done full on Gang of Four Design Patterns OO programming in C, it can be done. See GTK. Templates? Macros. Exceptions? Setjmp/longjmp. Etc.
My point here is this: sometimes enough “syntactic sugar” of the right kind moves you into a completely different design space. Implementing objects in C was not hard, but it was hard enough to prevent a serious exploration of the design space. OO Patterns didn’t develop until true OO languages, that made objects easy and natural, became widespread (the concepts of OO themselves date back to the sixties).
As for how C++ sucks, here’s one way: it doesn’t have garbage collection. Well, it has Boehm’s collector, which a) fails for large memory usage patterns, b) doesn’t interact well with C++’s object system, and c) can get totally blown out the water if some library (like Qt) were to override ::new(), and d) it’s not a copying garbage collector.
This is important when you realize that deallocation is a mutation. Immutable data structures don’t need to be synchronized on, but the immutability needs to include not deallocating the data structure. If some other thread somewhere wants to keep a pointer to the data structure around, the data structure needs to be kept around.
With garbage collection, this isn’t a problem. By definition an object isn’t garbage until there are no references to it from any live objects. At which point the garbage collector doesn’t need to synchronize on the object to deallocate it, only the GC can “find” the object.
OpenMP works good if what you’re doing is simple iterations over arrays- i.e. dense linear algebra stuff. Which is where I’ve mainly seen it used. But how well does it deal with business logic flow, for example? How well does it deal with the case where you can have wildly different amounts of time to complete a process (“Oh- that a form 1024-D3, for that you have to query this completely other database, that’ll take a bit, and…”)? How well does it deal with non-regular messages and thread results? How well does it deal with synchronizaiton, with complex webs of communications? Etc.
The El Dorado of an automatically parallelizing compiler has been the topic of research for decades. And last I checked, the fundamental result was still “parallelizing BLAS- easy. Parallelizing anything else- we’re working on that.” Note that neither Erlang nor Haskell/STM are automatic parallelizers. They give the programmer the tools neede to easily express parallelism in the implementation, but they still expect the programmer to find and express the parallelism.
Let the computers do what the computers do well, and let the humans do what the humans do well. Humans are really good at seeing that if you express this solution in a slightly different way, all these opportunities for parallelism open up. Computers suck at this. On the other hand, computer are really good at dilligently performing simple checks millions of times, where a human gets bored and lazy and inattentive fairly quickly. Especially if he’s thinking about better ways to express the fundamental solution.
Let’s turn that question around for a moment: why the heck do we need C++?
That’s my point too. If not C++ is the “tool” for a job, just don’t use it.
As for how C++ sucks, here’s one way: it doesn’t have garbage collection.
You can find as many people saying that GC is evil as many who wouldn’t like to live without it. I don’t miss it at all.
Note that neither Erlang nor Haskell/STM are automatic parallelizers. They give the programmer the tools neede to easily express parallelism in the implementation, but they still expect the programmer to find and express the parallelism.
It’s possible to create message queues in C++ too, and use only that for communication between threads.
But again, if I would have to implement a server application right now I would seriously consider Erlang.
For a big company the possibilities are more open. They have the resources to develop+maintain a framework which can be used effectively to implement such applications in C++.
Diversity is a good thing (C++ have it’s place, and needn’t to be repositioned), and the searching for the silver bullet is a good thing too (it will not be found, but generates a lot of great new ideas), but to say that “C++ sucks” just too harsh for me.
Teki: consider this. In the last 20+ years, I’ve only seen one language developer even the smallest following that didn’t have garbage collection- The D programming language. Every other single language that has more than a dozen people using it has GC. Every single one. Java, C#, Perl. Python, Ruby. Ocaml. Haskell. All of them.
You can add CLI/C++ to the list :).
But seriously, I still don’t understand what’s your problem with C++. It doesn’t have GC, maybe it isn’t crucial in it’s problem domain.
Ruby sucks, because it cannot be compiled to native code.
Python sucks, because it’s lambda is lame.
Perl sucks, because it’s ugly.
…
Ferrari cars suck, because they can’t go off-road.
These are the characteristics of the language. They help you to chose the tool.
Teki, good point. Stroustrup wrote this article in 1999 : Why no single programming language can solve every need. ( http://www.redherring.com/Article.aspx?a=6457 )
Main points:
First, we should remember that languages are used by people — a significant range of people
Second, we should resist the temptation to solve all programming problems once and for all by standardizing a single solution
Third, we should recognize that a programming language is a tool, not a solution.
And, then, there is timeless “No Silver Bullet”:
http://www-inst.eecs.berkeley.edu/~maratb/readings/NoSilverBullet.html
Let’s turn that question around for a moment: why the heck do we need C++? What does C++ give us that good ol’ fasioned C doesn’t? Objects? C has structures of function pointers. A little more clunky, but not much. I’ve done full on Gang of Four Design Patterns OO programming in C, it can be done. See GTK. Templates? Macros. Exceptions? Setjmp/longjmp. Etc.
Why not do it in assembler? Or, even better, why not go back to to flipping switches manually instead of abstracting them into humanly comprehensible entities such as integers, strings and functions?
One thing that keeps on striking me is the militant approach people tend to take when they dislike certain language as if someone is twisting their hand or legislate use of a language. Don’t like C++? More power to you – don’t use it.
Although there is no single programming language which will work in all cases, I disagree that there can’t be a dominant and provably/demonstrably better language in a particular solution space.
Consider, for instance, OSes. If you want to write an OS, your reasonable selection of languages are pretty small. And of that selection, you basically land on either C or a variation on C (cilk/CMinus).
Similarly, we are seeing business languages land in the same dominance. Java firmly killed off COBOL and has pretty much killed off C++, and would be the undisputed champion of the business world right now if it weren’t for the tight relationship between .Net and Windows: there would not have been a niche for CSharp to exist in without that coupling. And even so, the differences between CSharp and Java are small and getting smaller as time goes on — they’re converging within the same solution space. So you’ve got a similar solution.
Now that concurrency is becoming so critical to applications, I think the solution space is going to change in favor of functional programming. But we’ll see moving forward.
>Although there is no single programming language >which will work in all cases, I disagree that >there can’t be a dominant and >provably/demonstrably better language in a >particular solution space.
Exactly my point, with emphasis on “particular solution space”.
As for Java “killing” C++, you may want to reconsider your statement:
http://www.infoworld.com/img/38FEjobs_sc1.jpg
I’ll tell you what will kill off C in the low-level/banging on hardware space: a language that combines VHDL and C, i.e. that you can compile to both efficient software and efficient hardware. There have been attempts to bolt one on to the other, none of them worked very well.
One of my biggest complaints with C++ is that it tries to be all things to all people. It does low level OS code (in it’s C-like subset) and high level OO code! And with the new libraries in Boost, it even does functional programming (really badly)! It’s a floor wax and a desert topping! Although C++ isn’t the only language that comes in for this criticism (I really don’t like Ant because Java is a sucky scripting language, for example).
As for why I critize C++, there are two reasons. First, even if I don’t have to program in C++, I still have to use the broken and bug-ridden programs written in C++. For example, Lack of garbage collection isn’t just about programmer productivity (although pretty much every study ever done has shown that GC is a huge boost to programmer productivity), it’s also about correctness. The most common security hole is still the buffer overflow exploit, which is directly attributable to the lack of GC in C/C++ (well, and the lack of bounds checking- another feature provided by just about every language in the last 20 years). So the fact that my inbox has 60 spam, about half of which are various virii, just for today, is C++’s fault. Note that this is a reason why languages which are arguably even worse than C++ (APL, PL/I) don’t draw nearly as much ire.
The other reason is that there is a better way. But part of realizing that there is a better way requires realizing that the previous way wasn’t good (enough).
Also, part of my annoyance is that at times past, I held similiar opinions. Google “Brian Hurt” and comp.lang.java.advocacy for examples (this is also a good way to get long diatribes on why C++ sucks). 4-5 years ago (good lord, has it been that long?) I was developing a new language- an improved Java. I decided to learn Ocaml to at least understand why I wasn’t designing a functional programming language. Ocaml turned out to be a better language than I was designing, a better language than I knew how to design.
I’m disinclined to write down all the ways I think C++ sucks. Partially because I’m not programming in C++ anymore. But primarily because I’m now thinking beyond Ocaml. It’s not that Ocaml is a perfect language, far from it. It’s just light years better than C++ for the things Ocaml is at all good at. But we can do much better than Ocaml. The question is: how?
More on this later.
Brian
A smart acquaintance hilighted recently to me one seemingly large problem with STM vs. locks: at least with locks it is obvious which ones are “hot” so you can improve performance. With a transaction (whatever the connotation) if you get rollback you do not know why. So you can’t rework your code to avoid it in the future so easily.
Actually, I disagree that this is a difference. To tell which locks are “hot”, the lock implementation needs to be modified to keep track of which locks are being contended for. In much the same way, the STM implementation knows which ref cell caused the conflict that aborted the transaction, and this information could be recorded. This gives you exactly the same information- where are the contentions?
More generaly, you have to get it right before you make it fast. I don’t care how fast your program returns the wrong answer. Locks, especially locks plus mutable data, makes things very hard to get right. STM, especially STM + strong static typing + purely functional language, makes it very easy to get things right.
4 Trackbacks
[...] The conversation that ensued was really good. There were about five or six people who really became the ad hoc panel, and we talked about advantages of functional languages, and limitations to the adoption. During the talk about the advantages of concurrency with functional languages (see Brian’s post on the matter for more on that), this guy who had his head in his computer most of the time piped up to make an interesting observation: that Rails basically addresses the problem by forcing a single-threaded model, and leaving any “multithreading” aspect out of the user space. I thought that was pretty insightful, and I said something which I can’t really recall, and we moved on — it was until later that I realized it was celebrity guest David Heinemeier Hansson, the creator of Rails! I retroactively got a bit fanboyish when I found that out. [...]
[...] are going even further down memory lane with this post on Enfranchised Mind about Parallelism in General. It feels good to see a well-balanced and thought [...]
[...] is the continuation of a conversation started at Brian’s post on approaches to parallelism infrastructure, and continued at Thinking [...]
[...] Thoughts on Parallelism [...]