[Haskell-cafe] Multiprocessor compiling.

[Alastair Reid]

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 
parallelism.

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