Why is my recursion faster than Array.exists?

Question

I am pretty new to F#. I'm trying to understand how I can get a fast code in F#. For this, I tried to write two methods (IsPrime1 and IsPrime2) for benchmarking. My code is:

// Learn more about F# at http://fsharp.net
open System
open System.Diagnostics

#light

let isDivisible n d = n % d = 0
let IsPrime1 n =
    Array.init (n-2) ((+) 2) |> Array.exists (isDivisible n) |> not

let rec hasDivisor n d =
    match d with
    | x when x < n -> (n % x = 0) || (hasDivisor n (d+1)) 
    | _ -> false

let IsPrime2 n =
    hasDivisor n 2 |> not


let SumOfPrimes max = 
    [|2..max|] |> Array.filter IsPrime1 |> Array.sum

let maxVal = 20000

let s = new Stopwatch()
s.Start()

let valOfSum = SumOfPrimes maxVal

s.Stop()

Console.WriteLine valOfSum
Console.WriteLine("IsPrime1: {0}", s.ElapsedMilliseconds)

//////////////////////////////////
s.Reset()
s.Start()

let SumOfPrimes2 max = 
    [|2..max|] |> Array.filter IsPrime2 |> Array.sum

let valOfSum2 = SumOfPrimes2 maxVal

s.Stop()

Console.WriteLine valOfSum2
Console.WriteLine("IsPrime2: {0}", s.ElapsedMilliseconds)

Console.ReadKey()

IsPrime1 takes 760 ms while IsPrime2 takes 260ms for the same result.

What's going on here and how I can make my code even faster?

The slower version allocates a gigantic array and then goes through it - this is slow - your direct version is effectively keeping a number in a register — John Palmer, Sep 12 '12 at 04:00

pad · Accepted Answer · 2012-09-12T13:08:27.057

In IsPrime2, you don't construct a huge array so you could avoid allocating, explicitly traversing and garbage collecting this array. Remember that you call IsPrime1/IsPrime2 function max-1 times in SumOfPrimes so there are many instances of such array. Avoiding creating explicit data structures could be used as an optimization technique.

Here are some small optimizations which could be done on your code.

1) To check for divisors in hasDivisors, you only have to check up to sqrt(n) and skip all even numbers. If no divisor found, the checked number is prime.

let rec hasDivisor2 n d =
    match d with
    | x when x <= int(sqrt(float n)) -> (n % x = 0) || (hasDivisor2 n (d+2)) 
    | _ -> false

let IsPrime3 n =
    n = 2 || (n%2 <> 0 && not (hasDivisor2 n 3))

2) For SumOfPrimes, you could eliminate the intermediate array and also skip all even numbers (they couldn't be prime anyway).

let sumOfPrimes isPrime max = 
    [|2..max|] |> Array.filter isPrime|> Array.sum

let sumOfPrimes2 isPrime max = 
    let mutable sum = 2L
    for i in 3..2..max do
        if isPrime i then
            sum <- sum + int64 i
    sum

3) I did a small change so that isPrime is passed as an argument. In this way, you can measure your code more easily:

let time fn =
    let sw = new System.Diagnostics.Stopwatch()
    sw.Start()
    let f = fn()
    sw.Stop()
    printfn "Time taken: %.2f s" <| (float sw.ElapsedMilliseconds)/1000.0
    f

let maxVal = 200000

let p2 = time (fun () -> sumOfPrimes IsPrime2 maxVal)
let p3 = time (fun () -> sumOfPrimes2 IsPrime3 maxVal)

The new sumOfPrimes2 function with IsPrime3 is blazingly fast. It took 0.05 seconds on my machine for maxVal = 200000 while the original version took 7.45 seconds.

It turns out that the imperative version using mutable variables is the faster one. It is kind of frustating to me. However, thanks for your answer! — TapiocaCom, Sep 12 '12 at 12:31
Also, it turns out that IsPrime3 is buggy: it returns true for 4, for example. — TapiocaCom, Sep 12 '12 at 12:51
I fixed this mistake. It doesn't affect results of `sumOfPrimes`, does it? — pad, Sep 12 '12 at 13:09
@user38397 Just a thought--there's nothing wrong with mutating values (even in F#) for the sake of performance but one needs to consider the trade-offs. Mutating values can lead to possible side-effect errors--not a small consideration. And code with mutable values is harder to reason about. Mutation isn't bad--uncontrolled mutation which isn't intentional and deliberate on the part of the developer is bad. — Onorio Catenacci, Sep 13 '12 at 15:27
@user38397, @onorio-catenacci: You could also rewrite `for` loop using recursion. It will be both fast and immutable. I didn't do it due to laziness. — pad, Sep 13 '12 at 17:02
You're right, and I just rewrote the code and it is now recursive and very fast. I appreciate your answer. — TapiocaCom, Sep 16 '12 at 16:23

score 0 · Answer 2 · edited May 23 '17 at 11:55

The reason for the speed difference is that the slow code does something like this:

if n%a.[1] = 0 || n%a.[2]=0 ...

wheras the fast code does:

if n%2=0 || n%(2+1)=0 ...

In the fast case we don't need to go to memory to get the next factor. We also avoid having to build the array in the fast case

Here is my generic very fast F# code to build up a table of primes (from this answer: https://stackoverflow.com/a/12014908/124259):

#time "on"

let limit = 1000000
//returns an array of all the primes up to limit
let table =
    let table = Array.create limit true //use bools in the table to save on memory
    let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
    let mutable curfactor = 1;
    while curfactor < tlimit-2 do
        curfactor <- curfactor+2
        if table.[curfactor]  then //simple optimisation
            let mutable v = curfactor*2
            while v < limit do
                table.[v] <- false
                v <- v + curfactor
    let out = Array.create (100000) 0 //this needs to be greater than pi(limit)
    let mutable idx = 1
    out.[0]<-2
    let mutable curx=1
    while curx < limit-2 do
        curx <- curx + 2
        if table.[curx] then
            out.[idx]<-curx
            idx <- idx+1
    out

Why is my recursion faster than Array.exists?

2 Answers2