[Haskell-cafe] transparent parallelization

[Derek Elkins]

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
>                        greater = 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.