Does F# Async.Parallel speed up calculations?

Question

Does the "Async.Parallel" construction really help to make calculations faster on a multi-core system? Are .NET TPL "Tasks" involved here somehow?

open System;
let key = Console.ReadKey(true);
let start = System.DateTime.Now
let pmap f l = seq { for a in l do yield async {return f a} } |> Async.Parallel |> Async.RunSynchronously
let map f l = seq {for a in l do yield f a}
let work f l = 
 match key.KeyChar with 
 | '1' -> pmap f l 
 | '2' -> Seq.toArray (map f l) 
 | _ -> [||]
let result = work (fun x -> (x * x) / 75) (seq { 1 .. 100000*3})
let endtime = DateTime.Now - start 
printfn "%A"endtime;
let pause = Console.ReadKey(true);

I suppose some of you will explain it theoretically, but I would also appreciate some real world tests.

• TToni: With the sequence beefed up to 60000000, it runs 10 seconds with map and crashes with out-of-memory in pmap after 40 seconds or so. Both versions utilize only one of my two cores. Now I need an F# guru to explain this :-)

Answer 1

Using F# async for purely CPU-bound tasks works only if the tasks perform some more complicated operation. If you're trying to parallelize code that does something very simple, then it is better to use PLINQ (and the Task Parallel Library), which are more optimized for these kind of problems.

However, even then, getting speedup in a trivial case as the one you have is difficult. If you want to experiment with this a bit more, you can try this:

// Turn on timing in F# interactive
#time 
let data = [| 1 .. 5000000*3 |]
// Use standard 'map' function for arrays
let result = Array.map (fun x -> (x * x) / 75) data 
// Use optimized parallel version
let result = Array.Parallel.map (fun x -> (x * x) / 75) data

Note that using Array.map itself is a lot faster than using sequence expressions and then converting the result to an array. If you want to use more complex operations than mapping, then F# PowerPack contains PSeq module with functions similar to those in Seq or List:

#r @"FSharp.PowerPack.Parallel.Seq.dll"
data 
|> PSeq.map (fun a -> ...)
|> PSeq.filter (fun a -> ...)
|> PSeq.sort
|> Array.ofSeq

If you want to read more about this, I wrote a blog series about parallel programming in F# recently.

• Ade Miller: Tomas forgot to mention that he wrote a series of blog posts on F# and parallelism here: tomasp.net/blog/fsharp-parallel-samples.aspx
• Maslow: link provided in answer is dead

Answer 2

What pmap is doing is creating a list of 300,000 task objects, arranging for them to run in parallel, and only then actually running them in parallel. In other words, a single thread will sit there creating 300,000 objects and queueing them onto the thread pool. Only then will they execute.

Since your task is so trivial (a multiply and a divide), the overhead of creating the task, scheduling it, and handling its result is far more than just running the computation. This means that the async metaphor is ill-suited for this operation. It's far better to use PLINQ for this.

Answer 3

With calculations this simple, a better way is to only create a few async threads (probably one for each cpu), and then have each calculate part of your answer. As Gabe answered, you are spending all of your time creating task objects.

Using this type of a plan, I get speedups that scale pretty closely to the number of CPUs (the most I have tried is 8... I realize it won't scale forever)

Writing a utility for doing this is more work than just calling PLINQ, I guess, but once you have a pmap type utility, you can reuse it easily.