hubFS: THE place for F#

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:

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:

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

Thanks Don! I figured that
a) I musts be doing something wrong, or
b) it just isn't possible to do a recursive definition inside a workflow.

I will put some pressure on my colleagues to get you to come to JAOO in Aarhus next year - unfortunately I couldn't persuade them to give me a plane ticket to Sydney this year :-/. I will be working on getting some more functional programming in the tracks - there is a profound lack of that, I think. Too much Ruby and agile, too little FP.
By the way, have you been working with Eric Meijer on designing F#? I know he is a big fan of Haskell, and a self-proclaimed "serial language designer" :-)

Looking forward to the CTP, indeed! Not just because of recursive functions in workflows, but because of the entire package.
Anyone knows when? Or is it a big secret so far? :-)