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