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.

Answer 2

At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.

Your wiki reference says it best:

This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:

Trial division is the most laborious but easiest to understand of the integer factorization algorithms.

And is effectively what you're doing in your filter.

let isComposite candidate =  
    primes |> List.exists (fun p -> candidate % p = 0 )