Recently I decided to look at Haskell programming language. I have downloaded the best available compiler ([?:http://haskell.org/ghc/ GHC 6.8.1]), retrieved tutorial and started to dig in.
Everyone Haskell-related has promised me the pure functional language. This means lazy evaluations and no side effects. The basic syntax is quite easy, so I have started to do exercises.
One of them was about calculating fibonacci numbers. I have quickly written the most obvious code:
fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)
What have I expected from the Haskell environment about this code? At least one of the next:
1. I have expected that the result of the function with the same argument value will be cached, so each number in the recursion will be calculated only once.
2. The environment will take into account my double-core CPU and will calculate the function in two parallel threads.
Well, quite predictable expectations, aren't they? Hey, come on, it's very simple function on the pure functional language, thought I.
I gave a task for the ghci: evaluate me the fib 50, please. Yes, I know, the result will be big. But at least please give me something fast.
You know what? It took long. Very long. And what is more, I have opened the Task Manager and have discovered the 50% CPU load. Only one core was busy.
So, the most adopted "industrial" GHC has failed on my simple expectations.
Yes, of course, this function can be rewritten properly so it will be blazing fast and so on... But in this particular case the compiler have all required information for doing the job better without disturbing any parts of my tired brain.
However, [?:http://folding-maps.org Dmitry Timofeev], one of the co-founders of [?:http://spbhug.folding-maps.org Saint-Petersburg Haskell User Group], was a little bit surprised with this result, and has declared intentions to create better optimizing Haskell compiler, which will at least be more successful with doing multi-threading.
Dima, I'm watching you! :)
Comments
Yes, you are right: GHC's
Yes, you are right: GHC's optimizing and parallelizing capabilities are limited (although it is the best available Haskell compiler at present). Currently if you want to get maximum performance, you should take care about algorithms you use (including memoization and accumulators). You should also consider laziness/strictness and tail recursion etc.
Implicit parallelism is also problematic, but you can use explicit threads (STM seems to be a "right thing"), 'par' language construct and nested data parallelism (although its support is new and there will be many amendments).
There is a Wiki page on performance:
http://www.haskell.org/haskellwiki/Performance
But it is impossible ever for the best compiler for any language to make an efficient binary code if the program being compiled implements an inefficient algorithm, so your complaints about "bad compilers" are rather naive :).
Of cource, there is a plenty of room for improvement in compilers and tools design, so I expect that pure functional programming language compilers will someday outperform their imperative counterparts.
It's true that I (just) started to work on implicit parallelization of lazy pure functional languages, but I'm not the only one who deals with this problem. There are many research works on this subject, so I think that better compilers (and, first of all, better GHC versions) will be available soon.
In my gentoo linux x86_64
In my gentoo linux x86_64 (Core2Duo 6400) I have discovered the 100% CPU load.