[Haskell-cafe] Multiprocessor compiling.

Alastair Reid alastair at reid-consulting-uk.ltd.uk
Sat Jul 31 16:45:38 EDT 2004

On Saturday 31 July 2004 09:11, Matthew Roberts wrote:
> tell us the fundamental reason it is hard to compile Haskell
> for multiple processor machines - in broad strokes.

Unpredictability, heavy use of heap and overly fine granularity of inherent 

Unpredictability: Haskell's laziness (also being higher order, overloaded and 
polymorphic) makes it harder to predict what is related to what:  if I start 
to evaluate X, will I certainly/maybe evaluate Y; if X raises an exception, 
is it ok for Y to raise an exception too; does X contain a pointer to Y; etc.  
You can tackle this using a static analysis (e.g., strictness analysis) or 
using a dynamic mechanism (e.g., revertible grey holes).  Your analysis will 
have to be good enough to cope with very heavy use of higher order functions 
and overloading in typical Haskell code - though inlining and optimization of 
overloading will eliminate a lot of these features for you.

Heavy use of heap means that any locking required to implement memory 
allocation can easily be a significant overhead.  In single-processor 
systems, the cost of heap allocation might be 3 instructions: register add, 
register compare, branch.  In multi-processor systems, you probably need to 
have a separate allocation arena for each processor to get close to this cost 
since a single allocation arena would require locking.

Fine granularity of inherent parallelism is a problem because you really don't 
want to fork 3 threads to compute "a*b + c*d" because it would probably take 
10s of instructions (very optimistic minimum) to fork each thread but only 3 
instructions to do the actual work.  What you want to do is recognise that 
the three are strongly related and do them all in the same thread.

Hope this helps,
Alastair Reid

More information about the Haskell-Cafe mailing list