Back to Questions
3.1k
views1
comment
Recursive Async computational expressions
f#testingworkflowsasync

Earlier this month I was parallelizing an algorithm for testing if a given number is a prime number. I started with a recursive async version, but the performance was rather poor (much worse than the original sequential version). The code for the recursive part that runs in each thread looks something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

let parIsPrime number =
    let rec recIsPrime number divisor step (asyncGroup:AsyncGroup) =
        async { do! Async.CancelCheck()
                match (number%divisor) with
                | 0UL ->    do asyncGroup.TriggerCancel()
                            return false
                | _ ->  let divisorSquared = divisor*divisor
                        match divisorSquared with
                        | _ when divisorSquared>number -> return true
                        | _ ->  return! recIsPrime number (divisor+step) step asyncGroup}
    
    try
        match (number%2UL=0UL) with //remove any even numbers
        | true -> false
        | _ ->  let nThreads = (uint64)Environment.ProcessorCount
                let asyncGroup = AsyncGroup()
                let tasks = [for i in 0UL..nThreads-1UL -> recIsPrime number (3UL+i*2UL) (nThreads*2UL) asyncGroup]
                Async.Run((Async.Parallel tasks), asyncGroup)
                |> Array.for_all (fun x -> x)
    with
    | :? OperationCanceledException -> false

Is the poor performance due to the recursive call and how workflows are handled by the compiler?

I have made another version which performs as wanted:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

let parIsPrime number =
    let stop = ref false
    let rec recIsPrime number divisor step =
        match (number%divisor) with
        | 0UL ->    stop := true
                    false
        | _ ->  let divisorSquared = (divisor*divisor)
                match divisorSquared with
                | _ when divisorSquared > number -> true
                | _ ->  match !stop with
                        | true -> false
                        | _ -> recIsPrime number (divisor+step) step

    let isPrime number start step =
        async { return recIsPrime number start step }

    match (number%2UL=0UL) with //don't bother checking even numbers
    | true -> false
    | _ ->  let nThreads = (uint64)Environment.ProcessorCount
            let tasks = [for i in 0UL..nThreads-1UL -> isPrime number (3UL+i*2UL) (nThreads*2UL)]
            Async.Run((Async.Parallel tasks))
            |> Array.for_all (fun x -> x)

But this version uses a mutable ref variable instead of (AsyncGroup).TriggerCancel() to signal a stop to all other threads if one thread finds out that the number is not a prime. This is because I couldn't figure out how to do a CancelCheck in the above version.

The reason I defined the recursive function outside the async {...} construct is because recursive definitions does not seem to be allowed inside the workflow. Any particular reason for this?

Thanks in advance. Any input would be appreciated!

.

Hi there

Recursive functions definitions will be permitted inside function definitions in the CTP release of F#.

It's OK to use an imperative "stop" flag to stop CPU-intensive synchronous code.

Kind regards

don

By on 7/30/2008 5:03 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper