Slashdot Mirror
Time to Get Good At Functional Programming?
prone2tech writes "From an article at Dr. Dobb's: Chipmakers have essentially said that the job of enforcing Moore's Law is now a software problem. They will concentrate on putting more and more cores on a die, and it's up to the software industry to recraft software to take advantage of the parallel-processing capabilities of the new chips. As is argued in this article, this means becoming proficient in parallel functional programming. The bad news? Getting good at functional programming is hard, harder than moving from iterative Pascal or Basic or C coding to object-oriented development. It's an exaggeration but a useful one: When you move to FP, all your algorithms break.'"
I don't see why an algorithm would break just because you're changing language type, the whole point of an algorithm is that it's programming language independent.
It's been said in the comments on slashdot many times. Learning functional programming techniques will improve your programming skills. There are many good functional languages out there, and many have imperative features for ease of transition. No functional will not solve all of your problems, but it will give you that most valuable of all lessons, how to think about a problem _differently_.
You don't need an excuse, start today.
Absolute statements are never true
So a quick question before I go and master FP...does the compiler automatically compile the code that can be done in parallel in the proper "way", or do I have to specify something?
Also, if I rewrote an app written in an imperative language to a FP one like Haskell, would I see a that much of a difference on a multi-core processor?
Another question you might ask yourself is, are you going to let the CPU designers push you into a programming paradigm you are not effective in? Personally, I can see a machine being quite useful with say, 16 or 32 cores just because these machines do more than one thing at a time. But I'd much rather see them speed the cores up than endlessly multiply the number of them. There is a *lot* of room left to do this. Three D architectures offer more connectivity than is currently being used, and both the number and type of one-cycle instructions within a CPU can be increased until the summary is "all of 'em", which I doubt they're going to ever get to, orthogonality can be increased until again, the answer is that all instructions are available to the same degree for all registers and addressing modes no matter what. Compilers like broad orthogonality (and so do assembly programmers, not that there are a lot of us left.)
If CPU designers run off towards the horizon making many-core designs, what if no significant number of people follow them there? Which... frankly... pretty much seems to be the case. I've an 8-core machine, and just about the only things that actually use those cores together are the easy ones: graphics and waveform encoding/decoding. Aperture sure enough uses all my cores in a well-balanced fashion and can build a JPEG in a snap; but that's a far cry from my web browser doing the same thing while trying to render a page.
I'm just saying that the direction the CPU folks have chosen lately doesn't have to be the direction we actually end up going, and there are points in favor of this as the best choice.
Just some thoughts.
I've fallen off your lawn, and I can't get up.
Look at the table of contents of this BYTE magazine from 1985. In a nutshell it said the same thing as this article: Functional languages are the great hope for solving the parallel programming problem. Only then the languages were different: Hope, Linda, and Prolog were among them.
My response back then was to get excited about FP. My response now is: Where is the proof? Can anyone name a single instance where a functional paradigm has yielded the best measured performance on a parallel computing problem? In other words, take the best functional programmers in the world, and pair them up with the best tools in existence. Can they actually create something superior, on any problem running on any hardware? This is a very low bar, but until it's demonstrated FP will be confined mostly to the lab.
IMHO the path forward is to treat parallel programming like just another optimization. As we know, the vast majority of your code doesn't need to run fast, and you get most of the performance benefit by optimizing small bits of code that really matter. I suspect the same thing will happen with parallel programming: In a given application only a few areas will benefit much from parallelism, and these tasks will probably be very similar across applications. Graphics rendering, large matrix math, video encoding/decoding, and speech recognition would be examples. People will treat these as special cases, and either develop special-purpose hardware (e.g., GPUs), or libraries that encapsulate the nitty-gritty details. The interesting question to me is what is the best runtime model to support this.
As an example of the learning curve, I wanted to learn a little OCaml. I played around with this insertion sort example. I used it to sort a list of 10,000 integers, and it took 10 seconds, versus <1 second in C with linked lists. Not too horrible. But changing it to 100,000 integers made it die with a stack overflow, so I'm guessing that its memory use goes like n^2. However, it's not at all obvious to me from looking at the code that this would be the case. I think if I wanted to do a lot of OCaml programming I'd have to develop "FP Eye for the Straight Guy." Probably if you wanted to make it perform better on big arrays you'd want to make it tail-recursive, but it's not totally obvious to me from the code that it's *not* tail-recursive; although the recursive call isn't the very last line of code in the function, it is the very last thing in its clause...?
I know of at least one well known OSS project in Haskell, written by a very smart guy, that is really struggling with performance issues. I wonder whether bad performance is to FP as null-pointer bugs are to C. Sure, a sufficiently skilled programmer should theoretically never write code that will dereference a null pointer, but nevertheless my Ubuntu system needs a dozen security patches every month, many of which are due to null pointers, buffer overflows, etc.
Find free books.
Think of it as being "Moore's law is now also a software problem".
In the past, Moore's law meant that you could buy new hardware and have your stuff go way faster without any further work.
Now, Moore's law mainly means that you get more parallelism. Without software work, this means that your stuff runs at the same speed it used to. Thus software also needs to change in order to obtain the benefit.
If you mod me Overrated, you are admitting that you have no penis.
Actually, the reason for this is because of the heat consumption. As the power of a chip grows, the heat consumption grows much faster, and more cores are a much better way to get more speed with less power consumption and heat.
Well we've been using the same basic single-core architecture for the last, what, 30 or 40 years? Now programmers have a much bigger challenge in front of them - taking a program and make it work in a new environment.
I don't honestly believe there's been much in the way of innovation in the programming world for a while. Sure, you might have new coding languages that can do some things better than others or process it a different way, but don't they all operate on the same basic principle? Now programmers are faced with a complete paradigm change - the old style of programming isn't going to cut it 10 years from now when everything from your computer to your coffeemaker has a multi-core processor.
Engineers deal with stuff like this all the time. More than a few programmers use the term "software engineer". It's finally time for them to prove they can live up to that name and innovate.
Random Thoughts From A Diseased Mind (Not For Dummies)
Auto-parallelization of functional programs has been proposed for decades now, and every attempt has fallen on its face as the overhead has killed any gains. Current parallel FP research isn't even putting that much effort into auto-parallelization, because most PLs researchers consider it a dead end---taking a random FP and evaluating all its thunks in parallel as futures, or some similar mechanism, is not going to solve the problem.
Instead, most of the current research is in programmer-level primitives for designing and specifying inherently parallel algorithms. There is some of this in both the FP and non-FP communities.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
More CPU horsepower is the obvious choice for non-bus limited operations, but things are starting to get expensive there, so I welcome a few extra cores. The real question is if Intel and AMD will save some cash from their MMC(massive multi-core) projects and deliver a more sensible number of faster cores. You just can't depend on a given user's programs being set up to run efficiently in parallel.
personally, i think in terms of commodity computing, we don't really need to squeeze any more power out of the CPU than we've already got. use fully pipelined superscalar architectures, perhaps multithreaded dual or quad cores (for high-end workstations) and VLIW to maximize ILP efficiency. even at current processor speeds, 99% of the applications people (especially casual computer users) use have bottlenecks elsewhere (like memory & disk I/O speeds, internet bandwidth, user response time, etc.).
for the really resource-intensive stuff, like image/video/audio processing, cryptography, 3D graphics, CAD/engineering applications, scientific modeling, processing/manipulating financial data, etc. you would be much better off using a specialized dedicated vector coprocessor (as opposed to a general-purpose scalar processor that commodity CPUs tend to be). this way you can have a relatively low-power (and low clock rate) CPU for processing common SISD instructions that constitute 99% of all computing tasks, greatly cutting the cost of consumer and pro-sumer systems. and by using highly specialized coprocessors to handle the heavy lifting, those applications can be processed more efficiently while using less power (and at lower clock speeds) than trying to get a general-purpose scalar CPU to do the same work.
that is why GPGPUs are generating so much interest these days. it just so happens that most of the really processor-intensive applications consumers run greatly benefit from stream processing. game developers have long taken advantage of dedicated vector coprocessors with highly-specialized instruction sets and architecture made specifically for 3D gaming. DSPs with specialized architectures are also commonly used for hardware-accelerated video encoding, audio processing, etc. and now companies like Adobe are also seeing the advantages to using specialized vector coprocessors for their resource-intensive applications rather than having the CPU handle it.
and, honestly, how many different kinds of processor-intensive applications do most users run on a regular basis? if you're a graphic designer, your main processing power concern is only in relation to 2D/3D graphics. if you're an audio engineer or musician, then you're only going to use audio-related resource-intensive software. likewise, if you're a cryptographer/cryptanalyst, you probably won't ever run any audio editing software or 2D graphics software. therefore, it makes sense to pair moderately powered general-purpose scalar CPUs up with a powerful & highly specialized vector coprocessor like a GPU/DSP/Stream Processor/etc.
That's not really true. Supporting instruction level parallelism is reasonably straightforward - you just analyses the per-instruction data dependencies and output things ordered in such a way that the hardware instruction scheduler can do it's thing. There's only one problem - optimally ordering a set of instructions is NP-hard. So if you want to do a good job ordering 5 instructions you're fine, 15 instructions is obnoxious, and 150 instructions is basically impossible.
Further, instruction level re-ordering doesn't change the basic algorithm. If you're compiling a heapsort routine, the re-ordered instructions are still going to implement heapsort. And heapsort doesn't parallelize well. Maybe you could build logic into your compiler to detect heapsort and automatically replace it with parallel quicksort, but that doesn't help you when you run into a non-sorting routine.
Realistically, programmers have to write parallel code for many-processor platforms. It's not amazingly difficult (given reasonable training and a reasonable set of tools), but it is different. But it's not something that's going to go away when the gcc guys / java team / VS.NET team implement some clever optimization.
-- The act of censorship is always worse than whatever is being censored. Always.
Sorry, I didn't mean to imply that we had come to the end of invention, even in a small area.
But all of the effective techniques *that we know about* have been implemented, and the chip makers have been banging their heads on the wall for years trying to come up with new ones. They went to multi-core processors as an absolute last resort, and 5 years later it's probably time for most programmers to accept that and learn to target multi-core platforms.
-- The act of censorship is always worse than whatever is being censored. Always.