How Many Processor Cores Are Enough?
|
From: Brian Hurt on 27 Nov 2006 21:38 nmm1(a)cus.cam.ac.uk (Nick Maclaren) writes: >In article <dLGdnRGBz8Rjuf7YnZ2dnUVZ_qednZ2d(a)comcast.com>, >Joe Seigh <jseigh_01(a)xemaps.com> writes: >|> >|> I think the attraction of functional programming is composability. I think >|> there might be a way to get composability in procedural languages but it's >|> so far out of my areas of expertise that I think I'll wait for someone else >|> to figure it out. >You can write functional code in Fortran, and dysfunctional code in >Haskell :-) >At a higher level, functional programming AS SUCH gains little; if >you have to pass damn great structures which you keep changing for >subsequent calls and have to recurse many thousands of levels deep, >just to avoid an iteration with global variables, you have gained >nothing. It is a functional DESIGN that helps with composability. Even among imperitive programmers global variables are gaining a bad reputation. If you have to keep passing damn great structures (which I interpret not as simple structures with lots of elements, but instead complicated structures- you're not passing a list with a thousand elements, but a structure with dozens) this is a sign that your design sucks, and maybe spending some time redesigning so that you have fewer interdependencies would be a good thing. As for recursion vr.s loops, I'll agree that there isn't much practical difference. Well, it does make designing a language easier (you don't need lots of fancy loop controls like break, next, etc.) and designing a compiler easier (SSA is equivelent to purely functional programming- basically, you C++ compiler first translates the C++ into a functional language, and then compiles that). But to the programmer, it doesn't make much difference. Every loop can be expressed as a recursion, and vice versa. But that works both ways- recursion is no better than looping, but looping is no better than recursion. Brian
From: Joe Seigh on 27 Nov 2006 22:48 Brian Hurt wrote: > > There are four problems with multithreaded programming I've encountered: > 1) race conditions > 2) deadlocks > 3) livelocks Herlihy coined the term obstruction-free which sounds better than livelock. > 4) priority inversions > > STM solves 2 and 4, with Haskell's type system ensuring that all mutable > data is in STMs it also solves 1. I'm not sure it solves 3. livelocks, > which is why I still wimble. > > 5) scalability -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software.
From: Nick Maclaren on 28 Nov 2006 04:09 In article <fcNah.8413$lq.325(a)newsread1.mlpsca01.us.to.verio.net>, Brian Hurt <bhurt(a)spnz.org> writes: |> |> >While using functional code to express functional concepts is good for |> >many reasons, contorting stateful designs into a functional style makes |> >them much HARDER to parallelise, by obscuring their design. |> |> My response to that is to avoid statefull designs. At which point functional |> programming generally makes the design *less* obscure. While I agree with that, firstly, stateless designs bring in their own problems (poor error handling and diagnostics, for one) and, secondly, a lot of things CAN'T be done statelessly! |> To date, there are two categories of algorithms I can't do purely |> functionally: |> |> 1) Algorithms that rely on the O(1) nature of hash tables *and* ... |> |> 2) Graph algorithms, were I need to find the edges from a given node i |> fast. Arguably, this falls under 1. You should get out more! ANYTHING that takes an indefinite stream of input where one entry can have an effect an arbitrary time later is necessarily stateful. That includes 90% of all non-trivial, interactive applications, from spreadsheets to compilers to computer games. There are lots of others where it is easy to do them purely functionally, but it merely confuses the code to no gain. For example, any iterative algorithm can be converted to using recursion. |> >Sorry, no. That may be the biggest LOW-LEVEL problem, but there are much |> >worse ones :-( |> |> There are four problems with multithreaded programming I've encountered: |> 1) race conditions |> 2) deadlocks |> 3) livelocks |> 4) priority inversions |> |> STM solves 2 and 4, with Haskell's type system ensuring that all mutable |> data is in STMs it also solves 1. I'm not sure it solves 3. livelocks, |> which is why I still wimble. Again, those are only the very lowest level problems, and are generally easy to avoid by careful coding - even livelocks - but aren't easy to exclude in a language. What about resource distribution (not just data, but let's think of that?) Get that wrong, and you are perpetually having to interactions and hence cause the potential for livelocks. And forget the performance that you won't get .... Scheduling. Ah, scheduling. Resource allocation writ large. See livelock. The way that I feel such issues should be tackled is by handling them as a time-dependent DAG - i.e. where the timing of the messages causes the loop-free nature - because that is the correct mathematical model. Unfortunately, I have never seen a decent book on the topic, and am not enough of a mathematician myself to invent a new field of theory :-( |> I'm not sure loops are the right place to be looking for parallelism. |> Outside of dense numeric work (the baliwick of Fortran), most loops |> simply don't loop that often- a few dozen times at most. Yes and no. They are actually very common, but mostly in an intractable form (e.g. a loop over an input stream). |> For the foreseeable future, I don't see the compiler discovering signifigant |> amounts of parallelism. It's just too complicated. Functional programming |> might make it easier- but I don't think it'll make it easy *enough*. That is precisely what was discovered in the early 1970s. Regards, Nick Maclaren.
From: Nick Maclaren on 28 Nov 2006 04:15 In article <%iNah.8414$lq.351(a)newsread1.mlpsca01.us.to.verio.net>, Brian Hurt <bhurt(a)spnz.org> writes: |> |> Even among imperitive programmers global variables are gaining a bad |> reputation. ... I disagree. They were regarded as something to avoid when you could do so even back in the late 1960s - and the only reason that I give that date is that is when I started in this game :-) However, JUDICIOUS use of global state (i.e. to map what is global state in the underlying design) remains better than hiding it in superfluous arguments. I agree that it should be kept clean and minimal. |> But that works both ways- recursion is no better than looping, but looping |> is no better than recursion. Yup. To paraphrase an old joke: Recursion: equivalent to looping. Looping: equivalent to recursion. Regards, Nick Maclaren.
From: Joe Seigh on 14 Dec 2006 21:53
Chris Thomasson wrote: > "Joe Seigh" <jseigh_01(a)xemaps.com> wrote in message > news:us2dnfMMPJUnGYHYnZ2dnUVZ_sWdnZ2d(a)comcast.com...>>I don't know. I haven't event seen McKenney file any hardware patents in >>that area and he would have been the likely one to do that kind of stuff. > > > No kidding; he already has tons of RCU patents... In one of his bibliography > pages he even has links to your initial RCU+SMR hybrid idea. I wonder when > we are going to see patents for it... > > Soon enough. The patent application is 20060265373 Hybrid multi-threaded access to data structures using hazard pointers for reads and locks for updates by Paul McKenney and Maged Michael. -- Joe Seigh When you get lemons, you make lemonade. When you get hardware, you make software. |