Re: [Haskell-cafe] transparent parallelization

On Tue, 2007-09-18 at 18:13 +0200, Thomas Girod wrote:

Hi there. Beeing rather new to the realm of Haskell and functional programming, I've been reading about "how is easier it is to parallelize code in a purely functional language" (am I right saying that ?).

My knowledge of parallelization is also very weak, but I've been thinking about this and I have a question. Let's say we take a small piece of code, like the quicksort algorithm.

...

qsort [] = [] qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater where lesser = filter (=x) xs

(actually I didn't test this code, this is just for the example)

Here, computing "lesser" and "greater" are two disjoint actions - we don't need the result from one to compute the other, and haskell does not allow one to alter data so that would change the behaviour of the other. So I guess those could be run in parallel.

Would it be fairly simple to automatically determine parts of code that can be run in parallel, and parts that cannot (at least in non-monadic code) ?

The problem with Haskell is not finding opportunities to parallelize, they are legion. Actually, quite the opposite, there's so much that your code ends up slower than a sequential realization. The hard part is making a good cost-model and a good way to create coarser chunks of work. It's not worthwhile to spawn a thread (even a very lightweight one) for virtually every subexpression. Automatic parallelization is easy, efficient parallelization is hard.