Parallelising tree recursive procedure

Question

I wrote the change count problem from sicp in F# in the following way

let count_change amount = 

    let first_denomination kinds_of_coins = 
        match kinds_of_coins with
        |1->1
        |2->5
        |3->10
        |4->25
        |5->50

    let rec cc amount kinds_of_coins = 
        match (amount,kinds_of_coins) with
        |(0,_) -> 1
        |(i,j) when i<0 || j=0 -> 0
        |(_,_) -> 
            [cc amount (kinds_of_coins-1) + 
             cc (amount - (first_denomination kinds_of_coins)) kinds_of_coins] 
              |> List.fold (+) 0

    cc amount 5

I wanted to parallelize the long running task and this is what I did

let rec cc amount kinds_of_coins = 
    match (amount,kinds_of_coins) with
    |(0,_) -> 1
    |(i,j) when i<0 || j=0 -> 0
    |(_,_) -> 
      [async {return cc amount (kinds_of_coins-1)
       + cc (amount - (first_denomination kinds_of_coins)) kinds_of_coins}] 
       |> Async.Parallel |> Async.RunSynchronously |> Array.fold (+) 0

This is running slower than the first implementation by several orders. Can you please tell me how I could parallelize it more effectively.

Answer 1

I could be wrong, but I think you would need to do a breadth first traversal instead of a depth first one for parallelization to show any benefit.

Answer 2

This is not parallel at all. You just launch as parallel a single task, which is worse than doing it the straightforward way. Also, mind that your function is not tail recursive so it may not always be safe. Anyway the quickest way to introduce parallelism I can think of is:

let rec cc (amount,kinds_of_coins) = 
    match (amount,kinds_of_coins) with
    |(0,_) -> 1
    |(i,j) when i<0 || j=0 -> 0
    |(_,_) -> 
        [| (amount,(kinds_of_coins-1)); 
           ((amount - (first_denomination kinds_of_coins)), kinds_of_coins)
        |] |> Array.Parallel.map(cc) |> Array.fold (+) 0

But I don't guarantee you this will be much faster than the original.