Laziness and parallelism

1

What is the state of the art on the interaction of laziness and parallelism? I don’t see much (any) talk about it.

Haskell has an exceptional concurrency model that is facilitated by purity, not laziness.

Laziness keeps you pure. But does laziness keep you parallel? I believe laziness keeps you from automating parallelization. Therefore, in order to achieve Automatic Parallel Haskell, you need to ditch Lazy Haskell (which is basically doing another language).

It kinda makes sense. Laziness demands you to defer as much as possible (you don’t want to do needless work). Parallelism demands you to be as eager as possible (you want to discard needless work and have it ready if you need it). If you could determine automatically if something should be run in parallel, laziness is out of the picture, because you will need it or it will fizzle out, no need to defer it.

Not only laziness can interfere with the parallelization of finite expressions, the infinite data structures it allows pose a challenge too. If you have a list of infinite expensive items, and the user will consume some of them, when do you stop generating them? When do you start generating them? How do you reconcile minimizing time spent and minimizing memory consumed to try to be as eager as possible but not explode memory with both thunks and optimistic thunks?

I think Haskell does alright with the current parallel automatization it has (using strictness analysis to spark to-be-used computations), and enables the creation of libraries that do parallelization for you (Accelerate, massiv, async, ki). Basically, you have the best of both worlds: you don’t have to declare the order of expressions and can reap the benefits of laziness, but if you want, you can, and you can compose them.

Maybe it’s a good thing that parallelization has to be made explicit. For example, for the HVM3 you can write both sequential and divide-and-conquer algorithms and you won’t notice the parallelization kicking in until you run it and compare the results. In a way, it is similar to writing lazy code and not figuring out the thunk leaks are there, until you run it and see the memory graph.

By providing the programmer as many shapes as possible to manually fit the problem in (or Strategies, as in Parallel), you are indeed explicitly helping the programmer write parallel code. This reminds me of Clojure and its keyword, recur. Clojure doesn’t do Tail-Call Optimization, but it gives you recur, to turn its caller into a loop. If you write a function with recur, and it’s the wrong shape, it won’t let you do it and it will tell you. If you write it correctly it will be allowed and it won’t blow the stack.

So if automating parallelism in a language crafted for that very reason is a tall order (because you need to make the shapes match otherwise it degenerates to a sequence), laziness is a thrown wrench with dynamite on top and gives you an impossible-to-make runtime with so much profiling it would make V8 and HotSpot blush.

Basically, I don’t see an Automatic Parallel Haskell, but Parallel Haskell is indeed here and it’s great (which makes Haskell worth recommending for commercial use, I didn’t want to derail the thread).

2

  • I associate the term “automatic” with Haskell’s memory management because there’s no direct way to “decree” (in ordinary Haskell) that some particular expression “shall” work without it.

  • In contrast, laziness in Haskell can be “modulated” (hence the term non-strict semantics) - I can use (ordinary Haskell) bang annotations on types:

    data Complex a = !a :+ !a

    …or the confusingly-named primitive seq function (which isn’t actually sequential). Using -XStrict takes this to the extreme by inserting calls to seq throughout the modules it’s used on.

That is why I chose the phrase “lazy by default” for my initial post about parallelism - Haskell can be written “lazily”, but that’s rarely seen these days.

Parallel Haskell is indeed here and it’s great (which makes Haskell worth recommending for commercial use […])

I believe one LaurentRDC would completely agree with you!

…but some aren’t quite satisfied:

Completing #240 would then present an opportunity for (Glasgow) Haskell - since it already goes to the trouble of identifying suitable candidate expressions for speculative evaluation:

2.7. Version 9.6.7 — Glasgow Haskell Compiler 9.6.7 User's Guide

Added new flags -fspec-eval and -fspec-eval-dictfun to allow switching off speculative evaluation […].

a parallel version of GHC could (at least to begin with) just annotate some of those candidates with calls to par, possibly depending on how many tasks the hardware can support. Since multithreading would be enabled by default in GHC, so would this elementary form of parallelism.

(…hrm: I thought this was a private topic.)

2 Likes
3

As for switching to a strict Haskell - they keep appearing:

…and disappearing:

  • Discus - abandoned;
  • Mu - now being reimplemented in (Glasgow) Haskell;
  • Amy - no repository activity for about seven years now.
  • Hamler - no repository activity for about four years now.

As for other strict (mostly) “auto-parallel” functional languages:

Apart from Mu, does anyone else know why such languages don’t maintain any visible “traction” ?

2 Likes
4

Ah, I understand now.

You want -threaded by default (which didn’t happen because of regressions) and to actually spark with par some candidates (no sparks are generated if you don’t use par). Seems reasonable.

Given the “parallel by default” after the “lazy by default”, I got the impression that you wanted GHC to spark almost everything (basically HVM’s motto of “if it can run in parallel it will run in parallel” and a lot of non trivial things can be parallelized) to make parallelism as prevalent as laziness.

Other languages that come to mind are Chapel and Futhark.

5

You want -threaded by default (which didn’t happen because of regressions) and to actually spark with par some candidates (no sparks are generated if you don’t use par).

Correct; with par not being added by GHC if -single-threaded is used. (There’s no practical parallelism in small programs like POSIX’s true and false.)

I got the impression that you wanted GHC to spark almost everything […] to make parallelism as prevalent as laziness.

…hmm:

(…not yet, anyway ;-)

6

Mu is neither disappearing nor ditching strict semantics. It always has been implemented in Glasgow Haskell. It’s only replacing it’s current frontend to GHC (code to core). Backend and runtime stay the same.

1 Like
7

All of those strict Haskell dialects are still strict. As (more specifically) for Mu:

(…“they” being Standard Chartered.) So Mu’s new implemented-in-Glasgow-Haskell front section will only increase that LOC count further. Yes, that’s still smaller that SC’s Mu codebase…but that’s still more non-strict Haskell code.

8

I’d be surprised if Mu’s front end is not already implemented in Haskell. And they are going to use GHC as the front end. So their in-house Haskell codebase will probably shrink after this.

9

[…] they are going to use GHC as the front end.

…by (permanently) using -XStrict? If not, then how?

10

They still control the full back end, so they can give it a strict semantics without needing -XStrict. As a simple example, consider that you’ve been given the front end (i.e. parser and type checker) for this lambda calculus language:

data Exp = Var String | Lam String Exp | App Exp Exp

Then you can of course write a strict interpreter for it:

data Val = Clos (String -> Val) String Exp

interp :: (String -> Val) -> Exp -> Val
interp ev (Var v) = ev v
interp ev (Lam v x) = Clos ev v x
interp ev (App x y) = case interp ev x of
  Clos ev' v x' -> interp (\v' -> if v == v' then interp ev y else ev' v') x'
11

But Mu being strict means Haskell basics like [0, 2 ..] would either require “special handling” by SC’s existing back section to avoid endless looping, or a “front-of-front” section to ban such expressions outright.

Alternatively, did Mu already support [0, 2 ..] and similar expressions?