CODEWITHSUNDEEP
parallel-processingf#
dwagner6
dwagner6

Reputation: 77

How to execute two functions at once in f#?

I am trying to make my quick sort program in F# work in parallel by making two tasks execute in parallel. I tried looking at Microsofts online documentation but it didn't really help me! Here is my code without parallelism: 

let rec quicksort (list: int list) =
  match list with
  | [] -> [] // if empty list, yield nothing
  // otherwise, split the list into a head and tial, and the head is the pivot value
  | pivot :: tail ->
      // Using List.partition to partition the list into lower and upper
      let lower, upper = List.partition (fun x -> x < pivot) tail
      // Recursive calls, final product will be low list + pivot + high list
      quicksort lower @ [pivot] @  quicksort upper

I tried implementing something like

Async.Parallel [quicksort lower; @ [pivot] @ quicksort upper;] |> Async.RunSynchronously

But I get syntax errors referring to the type. What am I missing here?

Upvotes: 1

Views: 188

Answers (2)

Tomas Petricek
Tomas Petricek

Reputation: 243041

As mentioned by @hvester, adding parallelization to quicksort in this way will not help you much. The implementation is slow because it uses lists and allocations, not because of actual CPU bounds.

That said, if this was just an illustration to look at different ways of parallelizing F# code, then a good alternative to using Array.Parallel.map would be to use tasks:

open System.Threading.Tasks

let rec quicksort (list: int list) =
  match list with
  | [] -> [] 
  | pivot :: tail ->
      let lower, upper = List.partition (fun x -> x < pivot) tail
      let lowerRes = Task.Factory.StartNew(fun _ -> quicksort lower)
      let upperRes = quicksort upper
      lowerRes.Result @ [pivot] @ upperRes

Tasks let you start work in background using StartNew and then wait for result by accessing the Result property. I think this would be more appropriate in scenarios like this. Array.Parallel.map is more intended for doing parallel processing over larger arrays.

Upvotes: 2

hvester
hvester

Reputation: 1628

Parallelizing compute-bound code, such as sorting, should be done rather with Array.Parallel.map instead of Async.Parallel, which is for improving throughput of IO-bound code.

You could parallelize your function as follows with Array.Parallel.map.

let rec quicksort (list: int list) =
    match list with
    | [] -> [] /
    | pivot :: tail ->
        let lower, upper = List.partition (fun x -> x < pivot) tail
        let sortedArrays = Array.Parallel.map quicksort [| lower; upper |]
        sortedArrays.[0] @ [pivot] @ sortedArrays.[1]

However, you should NOT do this, because the overhead of parallelization is much higher than the benefit of parallelization and the parallelized version is actually much slower.

If you want to speed up quicksort algorithm biggest gains can be achieved by avoiding allocating objects (lists) during the algorithm. Using an array and mutating it in place is the way to go :)

Upvotes: 2

Related Questions