Performance comparison of different implementations

SieveOfEratosthenes.fsx

// R imperative version (count prime numbers)
// sieb4 <- function(N) {
//   
//   if (N < 2L) return(integer())
//   if (N == 2L) return(2L)
//   toCheck <- seq_len(N)
//   toCheck[1L] <- 0L
//   toCheck[c(FALSE, TRUE)] <- 0L
//   
//   i <- 3L
//   while (i <= N) {
//     if (toCheck[i] > 0L) {
//       j <- i + i
//       while (j <= N) {
//         toCheck[j] <- 0L
//         j <- j + i
//       }
//     }
//     i <- i + 1L
//   }
//   
//   c(2L, toCheck[toCheck != 0L])
// }
// sieb4(10)


module Perf =
    open System.Diagnostics
    
    let measure name f =
        let sw = Stopwatch()
        sw.Start()
        let res = f()
        sw.Stop()
        printfn "%50s  --  %fs" name sw.Elapsed.TotalSeconds
        res


let siebWhile n =
    let toCheck = Array.zeroCreate<int> (n + 1)
    let crossedV = -1
    
    let mutable i = 2
    while i <= n do
    //for i in 2..n do
        if toCheck.[i] <> crossedV then
            toCheck.[i] <- i
            
            let mutable j = i + i
            while j <= n do
            //for j in (i+i).. i .. n do
                toCheck.[j] <- crossedV
                j <- j + i
        i <- i + 1
    toCheck

let siebFor n =
    let toCheck = Array.zeroCreate<int> (n + 1)
    let crossedV = -1
    
    for i in 2..n do
        if toCheck.[i] <> crossedV then
            toCheck.[i] <- i
            
            for j in (i+i).. i .. n do
                toCheck.[j] <- crossedV
    toCheck

let siebIter n =
    let toCheck = Array.zeroCreate<int> (n + 1)
    let crossedV = -1
    
    toCheck
    |> Array.iteri (fun i v ->
        if i < 2 then ()
        elif toCheck.[i] <> crossedV then
            toCheck.[i] <- i
            
            for j in (i+i).. i .. n do
                toCheck.[j] <- crossedV
        else ())
    toCheck

let siebPIter n =
    let toCheck = Array.zeroCreate<int> (n + 1)
    let crossedV = -1
    
    toCheck |> Array.Parallel.iteri (fun i v ->
        if i < 2 then ()
        elif toCheck.[i] <> crossedV then
            toCheck.[i] <- i

            for j in (i+i).. i .. n do
                toCheck.[j] <- crossedV
        else ())
    toCheck

let siebRec n =
    let toCheck = Array.zeroCreate<int> (n + 1)
    let crossedV = -1

    // F# has tail call optimizations and can transform that into a whie loop
    let rec loopi i =
        if i <= n then
            if toCheck.[i] <> crossedV then
                toCheck.[i] <- i
                
                let rec loopj j =
                    if j <= n then
                        toCheck.[j] <- crossedV
                        loopj (j+i)
                loopj (2*i)
            loopi (i+1)
    loopi (2)
    
    // return
    toCheck


let filterPrim v = v |> Array.filter (fun x -> x > 0)

let n = 50_000_000
(fun () -> siebWhile n) |> Perf.measure "while loop" |> filterPrim
(fun () -> siebFor n) |> Perf.measure "for loop" |> filterPrim
(fun () -> siebIter n) |> Perf.measure "Array.iteri (outer) for loop (inner)" |> filterPrim
(fun () -> siebPIter n) |> Perf.measure "Array.Parallel.iteri (outer) for loop (inner)" |> filterPrim
(fun () -> siebRec n) |> Perf.measure "Tail recursion (both)" |> filterPrim
printfn ""
printfn ""