[Haskell-cafe] Automatic parallelism in Haskell, similar to "make -j4"?

[Luke Palmer]

On Sun, Nov 2, 2008 at 12:42 PM, T Willingham <t.r.willingham at gmail.com> wrote:
> On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin
> <bulat.ziganshin at gmail.com> wrote:
>>> What would it take to implement a -j equivalent for, say, GHC?  Or if
>>> this is not possible, what is wrong with my reasoning?
>>
>> problem is that make have rather large pices of work which it can run
>> parallel. if ghc will try to parallel every machine operation, it will
>> pend more time maintaining these jobs. 'par' is just the way to tell
>> GHC "this part of job is large enough"
>
> Right, but couldn't the Haskell complier+runtime discover "rather
> large pieces of work"?

Perhaps, but not easily.  Especially if it can be done statically,
there is plenty of research to be done in this area.

Haskell is rather different from make.  The graph of a lambda calculus
program is not nearly as transparent as the graph of a makefile --
*especially* considering lazy evaluation.  For example, you might
think:

  map (+1) [1..10000000]

Is a "rather large piece of work", but if it is then applied to "take
4", that is no longer true.  We don't want to be futilely spinning our
processor computing this.

So my guess is that there are some cases, in the same way as
strictness analysis, where you can identify these, but there are many
cases which are much more subtle and hard to identify automatically.
But I am no expert in the area.

Luke