4 ms·

I think there's some reasonable stuff buried in here, I really do. But... having actually spent some time in the trenches dealing with a hard problem on a mass

I think there's some reasonable stuff buried in here, I really do. But... having actually spent some time in the trenches dealing with a hard problem on a massively parallel machine - more than once - I find it hard to believe that something like map/reduce or the like - or any given small-scale language feature is going to be particularly significant in terms of parallelizing any goddamn thing that's actually hard to do. I see a lot of fatuous claims that language feature X is the missing link in parallelism for the everyday working programmer but I don't see a lot of new solutions for anything hard as a proof of concept. We've only had OpenMP and all sorts of other kludgy extensions for Fortran and C for what, about 15 years? I'm not saying that they're great or elegant or anything, but so many of the things that are hard about parallel programming are NOT FUCKING SOLVED BY MAP-REDUCE. Oops, sorry, shouty. But anything that can be solved by map-reduce wasn't enormously hard to begin with. Map-reduce was itself initially publicized in terms of 'less useful but easier for mere mortals than generalized parallel prefix' which made sense to me. What doesn't make sense for me is all this frenzied enthusiasm for dragging parallel programming into the never-ending programmlng language abstraction wars; at least when the topics being discussed only touch on the very shallowest things needed by parallel programming. You want some respect, solve something hard. Yes, you can do the same thing to each element of an array. Whaddya want, a cookie?

jxcole 16y ago
I agree that map reduce does not solve parallel computing. However, that is just one example of how closures/lambdas can help you design software. It helps in almost any system in which you have two different functions that do almost the same thing, but a little different. For example, say you are writing a double linked list. The push to head and push to tail functions may be completely the same, except one uses the head and one uses the tail, so you could just write one function and pass in the head or tail, right? But you can't. The problem is that when you add something to one side, the links are the opposite. That is a new head goes to the right of the old head, while a new tail goes to the left of the old tail. In order to really do this, you also have to pass in a function. Now, I've written a few doubly linked lists in Java (don't get mad, there _are_ good to do this), and in the end I just copy the function and make the inline changes. Trying to create the right interface and then pass in anonymous classes is almost impossible. And even if in my supreme cleverness I could figure it out, the code would be so confusing as to be unmaintainable. Anyway, I would say that closures are immensely useful, not _just_ because of map reduce, but because of a whole class of examples that work in this manner.
Peaker 16y ago
Here's the main Haskell hero, Simon Peyton Jones giving a talk about data parallel Haskell, which I think is a promising language abstraction to do hard things with parallelism relatively easily: http://www.youtube.com/watch?v=NWSZ4c9yqW8 http://www.youtube.com/watch?v=NWSZ4c9yqW8 As for techniques that can be used now: Haskell's `par` and `pseq` combinators allow adding parallelization to "hard" code after-the-fact pretty easily.
- pjscott 16y ago
  On a few occasions, I've taken a program and added a few functions from Control.Parallel, and five minutes later, I had a significantly faster program running on several cores. It was surprisingly easy. Granted, I was going after the low-hanging-fruit cases, but even so, I was impressed.
- SeanLuke 16y ago
  Wasn't the promise of haskell the idea that parallelism would be implicit? What are operators like those doing there?
  - Peaker 16y ago
    No, that was never "the promise" of Haskell. Making automatic implicit parallelism in Haskell is trivial - but it will yield too much parallelism and the overhead will trump the benefits. The `par` and `pseq` combinators allow the programmer to specify which computations to parallelize explicitly to avoid parallelizing computations that are too small to be worth it and to allow the programmer to care for data-locality. Despite being explicit, they are still far easier than other explicit parallelism mechanisms such as explicit threads because they are: * So easy to throw in the program * Guaranteed not to alter the semantics of your program - so you can just throw them in there and profile the performance changes -- and you know they won't break your program. They can alter the performance for better or worse.
yid 16y ago
> But anything that can be solved by map-reduce wasn't enormously hard to begin with. Depends on your definition of hard. Algorithmically, yes the tasks are relatively simple, but try programming an 80,000 node MPI/PVM cluster to run general jobs and you'll get a very different definition of "hard".
6ren 16y ago
Also, Fortran has long been used for parallel programs (on mainframes). Guy Steele is working on Fortress, and he has some interesting insights on the issue. But I do think that a practical solution will have to rethink not only programming languages, but the concept of programs. It will be made by a young and naive tinkerer, trying to solve a specific problem on actual parallel hardware, not by guys who have been entrenched in the field for decades. So it won't happen til that concrete technology (eg. 100 cores) is widely available. While there may be similarities with functional and object oriented programming (Alan Kay's version), it won't be based on them.
kragen 16y ago
It's a little misleading to link MapReduce to language support for anonymous functions. The original implementation of MapReduce was in C++!
Rusky 16y ago
Joel's point is that these things are easy now because of techniques or features like the ones he brings up. Try to do something like that in assembly or FORTRAN or C and it's not all that easy any more. You're working a level above- map/reduce is easy there and things that would be completely unthinkable to maintain in assembly/FORTRAN/C are the real hard problems.
- onan_barbarian 16y ago
  My feeling is that this notion that each level of abstraction makes 'everything above that level easier, including sophisticated algorithms that would be 2 or 3 levels up' is simply not true. Just because easy things are easier in a language with map/reduce and gc and whatever else, doesn't necessarily mean that things that were hard before will fit cleanly into the mechanism. Your idea that things that are 'completely unthinkable to maintain in Fortran or C' are somehow much easier in this kind of environment is just silly; there are multiple orders of magnitude more parallel code written in both of those languages than map/reduce and many of the classic parallel algorithms and (wince) design patterns like parallel prefix were written in these languages originally or are easily expressed that way. The _hard_ algorithms are ones with sophisticated communication requirements that aren't well captured by map/reduce, so in this case, having a abstraction to deal with the easy cases has accomplished nothing towards making hard cases easier. I'm not against abstraction, of course - just this premature triumphalism that picking a 'easy things become easy' approach gets you, especially if you don't solve the hard things.
  - Rusky 16y ago
    Yes. However, doesn't it make sense that it's easier at least to focus on the hard things when you don't have to worry about the notational clumsiness that comes from a lack of first-class functions, etc.?
- ramchip 16y ago
  Even as a Haskell programmer, I don't really agree with this particular example. This kind of parallelization is extremely easy in C++ and offers a lot of control if you need to do more complicated things: http://en.wikipedia.org/wiki/OpenMP http://en.wikipedia.org/wiki/OpenMP I think it's just that a more complicated example is needed to really show the advantage of the first-class functions and such.
praptak 16y ago
"I find it hard to believe that something like map/reduce or the like - or any given small-scale language feature is going to be particularly significant in terms of parallelizing any goddamn thing that's actually hard to do." I don't believe it either, but it wasn't the point of the article. It was not about magically solving hard problems, but getting about parallelism for free where it is easy. OTOH it is not apparent that those language features are actually indispensable for that. In most cases where 'map' would apply, it is quite possible for a compiler to detect that the loop body does not rely on its own previous executions and can thus be parallelized automatically.
- onan_barbarian 16y ago
  Yes, the last bit was largely my point.
earl 16y ago
In practice, as someone who has spent the last 18 months writing MR code at Quantcast, the difficult parts of writing map reduce programs all are how does one take communicative/global knowledge algorithms and either (1) change the algorithm to require only a handful of passes each with partial knowledge, or (2) create a probabilistic algorithm to solve an approximation of your problem that can be computed with only partial knowledge. No one says otherwise. But Map Reduce does, IMO, do one thing that MPI doesn't: the easy things are easy. Hard stuff is still hard, but easy things are easy. If you have a low communication algorithm that requires only local knowledge and fits into the MR paradigm well, hadoop + hdfs makes it really simple to write and reliably execute, including automatically handling things like (i) worker nodes dying, (ii) sorters dying, (iii) storage nodes dropping out, (iv) whole steps disappearing and having to be rerun.

jxcole 16y ago

I agree that map reduce does not solve parallel computing. However, that is just one example of how closures/lambdas can help you design software. It helps in almost any system in which you have two different functions that do almost the same thing, but a little different. For example, say you are writing a double linked list. The push to head and push to tail functions may be completely the same, except one uses the head and one uses the tail, so you could just write one function and pass in the head or tail, right? But you can't. The problem is that when you add something to one side, the links are the opposite. That is a new head goes to the right of the old head, while a new tail goes to the left of the old tail. In order to really do this, you also have to pass in a function. Now, I've written a few doubly linked lists in Java (don't get mad, there _are_ good to do this), and in the end I just copy the function and make the inline changes. Trying to create the right interface and then pass in anonymous classes is almost impossible. And even if in my supreme cleverness I could figure it out, the code would be so confusing as to be unmaintainable. Anyway, I would say that closures are immensely useful, not _just_ because of map reduce, but because of a whole class of examples that work in this manner.

Peaker 16y ago

Here's the main Haskell hero, Simon Peyton Jones giving a talk about data parallel Haskell, which I think is a promising language abstraction to do hard things with parallelism relatively easily: http://www.youtube.com/watch?v=NWSZ4c9yqW8 http://www.youtube.com/watch?v=NWSZ4c9yqW8 As for techniques that can be used now: Haskell's `par` and `pseq` combinators allow adding parallelization to "hard" code after-the-fact pretty easily.

pjscott 16y ago
On a few occasions, I've taken a program and added a few functions from Control.Parallel, and five minutes later, I had a significantly faster program running on several cores. It was surprisingly easy. Granted, I was going after the low-hanging-fruit cases, but even so, I was impressed.
SeanLuke 16y ago
Wasn't the promise of haskell the idea that parallelism would be implicit? What are operators like those doing there?
- Peaker 16y ago
  No, that was never "the promise" of Haskell. Making automatic implicit parallelism in Haskell is trivial - but it will yield too much parallelism and the overhead will trump the benefits. The `par` and `pseq` combinators allow the programmer to specify which computations to parallelize explicitly to avoid parallelizing computations that are too small to be worth it and to allow the programmer to care for data-locality. Despite being explicit, they are still far easier than other explicit parallelism mechanisms such as explicit threads because they are: * So easy to throw in the program * Guaranteed not to alter the semantics of your program - so you can just throw them in there and profile the performance changes -- and you know they won't break your program. They can alter the performance for better or worse.

yid 16y ago

> But anything that can be solved by map-reduce wasn't enormously hard to begin with. Depends on your definition of hard. Algorithmically, yes the tasks are relatively simple, but try programming an 80,000 node MPI/PVM cluster to run general jobs and you'll get a very different definition of "hard".

6ren 16y ago

Also, Fortran has long been used for parallel programs (on mainframes). Guy Steele is working on Fortress, and he has some interesting insights on the issue. But I do think that a practical solution will have to rethink not only programming languages, but the concept of programs. It will be made by a young and naive tinkerer, trying to solve a specific problem on actual parallel hardware, not by guys who have been entrenched in the field for decades. So it won't happen til that concrete technology (eg. 100 cores) is widely available. While there may be similarities with functional and object oriented programming (Alan Kay's version), it won't be based on them.

kragen 16y ago

It's a little misleading to link MapReduce to language support for anonymous functions. The original implementation of MapReduce was in C++!

Rusky 16y ago

Joel's point is that these things are easy now because of techniques or features like the ones he brings up. Try to do something like that in assembly or FORTRAN or C and it's not all that easy any more. You're working a level above- map/reduce is easy there and things that would be completely unthinkable to maintain in assembly/FORTRAN/C are the real hard problems.

onan_barbarian 16y ago
My feeling is that this notion that each level of abstraction makes 'everything above that level easier, including sophisticated algorithms that would be 2 or 3 levels up' is simply not true. Just because easy things are easier in a language with map/reduce and gc and whatever else, doesn't necessarily mean that things that were hard before will fit cleanly into the mechanism. Your idea that things that are 'completely unthinkable to maintain in Fortran or C' are somehow much easier in this kind of environment is just silly; there are multiple orders of magnitude more parallel code written in both of those languages than map/reduce and many of the classic parallel algorithms and (wince) design patterns like parallel prefix were written in these languages originally or are easily expressed that way. The _hard_ algorithms are ones with sophisticated communication requirements that aren't well captured by map/reduce, so in this case, having a abstraction to deal with the easy cases has accomplished nothing towards making hard cases easier. I'm not against abstraction, of course - just this premature triumphalism that picking a 'easy things become easy' approach gets you, especially if you don't solve the hard things.
- Rusky 16y ago
  Yes. However, doesn't it make sense that it's easier at least to focus on the hard things when you don't have to worry about the notational clumsiness that comes from a lack of first-class functions, etc.?
ramchip 16y ago
Even as a Haskell programmer, I don't really agree with this particular example. This kind of parallelization is extremely easy in C++ and offers a lot of control if you need to do more complicated things: http://en.wikipedia.org/wiki/OpenMP http://en.wikipedia.org/wiki/OpenMP I think it's just that a more complicated example is needed to really show the advantage of the first-class functions and such.

praptak 16y ago

"I find it hard to believe that something like map/reduce or the like - or any given small-scale language feature is going to be particularly significant in terms of parallelizing any goddamn thing that's actually hard to do." I don't believe it either, but it wasn't the point of the article. It was not about magically solving hard problems, but getting about parallelism for free where it is easy. OTOH it is not apparent that those language features are actually indispensable for that. In most cases where 'map' would apply, it is quite possible for a compiler to detect that the loop body does not rely on its own previous executions and can thus be parallelized automatically.

onan_barbarian 16y ago
Yes, the last bit was largely my point.

earl 16y ago

In practice, as someone who has spent the last 18 months writing MR code at Quantcast, the difficult parts of writing map reduce programs all are how does one take communicative/global knowledge algorithms and either (1) change the algorithm to require only a handful of passes each with partial knowledge, or (2) create a probabilistic algorithm to solve an approximation of your problem that can be computed with only partial knowledge. No one says otherwise. But Map Reduce does, IMO, do one thing that MPI doesn't: the easy things are easy. Hard stuff is still hard, but easy things are easy. If you have a low communication algorithm that requires only local knowledge and fits into the MR paradigm well, hadoop + hdfs makes it really simple to write and reliably execute, including automatically handling things like (i) worker nodes dying, (ii) sorters dying, (iii) storage nodes dropping out, (iv) whole steps disappearing and having to be rerun.