F# Idiomatic Performance

Question

I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.

I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:

(BenchmarkDotNet v0.11.2)

Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.

Here is the idiomatic code:

// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed = 
    let nextTen seed ten = 
        let x = (seed) + (ten * 10)
        [x + 1; x + 3; x + 7; x + 9]
    let candidates = [for x in 0..9 do yield! nextTen seed x ]
    match candidates with 
    | 1::xs -> xs  //skip 1 for candidates
    | _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list = 
    let isComposite candidate = 
        primes |> List.exists (fun p -> candidate % p = 0 )
    candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option = 
    match nth with 
        | 0 -> None
        | 1 -> Some 2
        | _ ->
            let rec sieve seed primes candidates = 
                match candidates with 
                | [] -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
                | p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
                | p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
                    sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
                | p::xs -> 
                    sieve seed (p::primes) xs


            Some (sieve 0 [3; 5] [])

And here is the imperative:

type prime = 
    struct 
        val BaseNumber: int
        val mutable NextMultiple: int
        new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
        //next multiple that is odd; (odd plus odd) is even plus odd is odd
        member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this 
    end

let prime nth : int option = 
    match nth with 
    | 0 -> None
    | 1 -> Some 2
    | _ ->
        let nth' = nth - 1 //not including 2, the first prime
        let primes = Array.zeroCreate<prime>(nth')
        let mutable primeCount = 0
        let mutable candidate = 3 
        let mutable isComposite = false
        while primeCount < nth' do

            for i = 0 to primeCount - 1 do
                if primes.[i].NextMultiple = candidate then
                    isComposite <- true
                    primes.[i] <- primes.[i].incrMultiple()

            if isComposite = false then 
                primes.[primeCount] <- new prime(candidate)
                primeCount <- primeCount + 1

            isComposite <- false
            candidate <- candidate + 2

        Some primes.[nth' - 1].BaseNumber

Answer 1

So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.

For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.

type prime = {BaseNumber: int; mutable NextNumber: int}
let isComposite (primes:prime list) candidate = 
    let rec inner primes candidate =
        match primes with 
        | [] -> false
        | p::ps ->
            match p.NextNumber = candidate with
            | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
                      inner ps candidate |> ignore
                      true
            | false -> inner ps candidate
    inner primes candidate


let prime nth: int option = 
    match nth with 
    | 0 -> None
    | 1 -> Some 2
    | _ -> 
            let rec findPrime (primes: prime list) (candidate: int) (n: int) = 
                match nth - n with 
                | 1 -> primes
                | _ -> let isC = isComposite primes candidate
                       if (not isC) then
                           findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
                       else
                           findPrime primes (candidate + 2) n
            let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
                    |> List.head
            Some(p.BaseNumber)

Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.