Controlling parallel execution

Question

Haskell provides a par combinator, which queues a "spark" for possible evaluation in parallel with the current thread. It also provides a pseq combinator, which forces evaluation of pure code to occur in a specific order.

What Haskell does not appear to provide is a way to generate several sparks and then wait for them all to finish. This is quite trivial to achieve with explicit concurrency, but appears to be impossible with pure sparks.

In part, this is perhaps because of the intended use-case for sparks. They appear to be designed for speculative evaluation. That is, doing work which might be needed, but might not be. Hence, sparks only run on cores which are otherwise idle.

However, this is not my use-case. I have a bunch of results which I know, for a fact, will be needed soon. And if I start trying to process the results before the sparks have fired, I'll just end up single-threaded again with a bunch of fizzled sparks.

Of course, of par waited for sparks to complete, it wouldn't achieve any parallelism! But it would be really useful if there were some way to produce several sparks and then wait for them all to finish. I can't find any way to do that though.

Does anybody have any useful suggestions? (Other than "use explicit concurrency", obviously.)

Answer 1

The Really Short Answer

You can't.

The Short Answer

To wait for a spark to finish, try to evaluate what the spark was evaluating. For example, if you have expressions a and b, to calculate a + b, you can do

a `par` b `par` (a + b)

or

a `par` b `pseq` (a + b)

The Long Answer

When you create a spark by using par, you are telling the run time system "I will need this value later, so you should evaluate it in parallel." When you later need the value, either the spark has evaluated the expression or it hasn't. If it has, the thunk will be replaced by a value, and so re-evaluation has no cost - it is just fetching the value. If it hasn't been evaluated be the spark then waiting for the spark is useless - it might take a while to get scheduled, and the thread waiting is wasting time. Instead of waiting, you should just evaluate the expression yourself. Essentially, there is no need to wait for a spark. You just try to evaluate the original expression and get performance benifits.

Also, a note on speculation - although sparks can be and often are used for speculation, that is not completely what they are designed for. I see par being used for simple parallelization, as in pfib below, much more often than I see it used for speculation.

Examples

A standard example is parallelizing the Fibonacci numbers, from the serial

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

to the parallel

pfib 0 = 0
pfib 1 = 1
pfib n = l `par` r `pseq` (l + r) where
    l = pfib (n - 1)
    r = pfib (n - 2)

.

Now for an example using speculation:

spec :: a -- a guess to the input value
    -> (a -> b) -- a function to tranform the input value
    -> a -- the actual input value - this will require computation
    -> b -- the function applied to the input value
spec guess f input = let speculation = f guess in speculation `par`
    if guess == input
        then speculation
        else f input

The hackage package I got this from, speculation, actually had a couple optimizations like not doing this on a single core and checking whether the input was already evaluated, but that doesn't matter to the working of the function.

Other Solutions that Make Things More Explicit

• monad-par
• Strategies, which make use of par.
• Messing with IO. There are a lot of things here.