F# vs C# performance for prime number generator

Question

I have noticed that seemingly equivalent code in F# and C# do not perform the same. The F# is slower by the order of magnitude. As an example I am providing my code which generates prime numbers/gives nth prime number in F# and C#. My F# code is:

let rec isprime x =
primes
|> Seq.takeWhile (fun i -> i*i <= x)
|> Seq.forall (fun i -> x%i <> 0)

and primes = 
    seq {
        yield 2
        yield! (Seq.unfold (fun i -> Some(i, i+2)) 3)
                |> Seq.filter isprime
    }


let n = 1000
let start = System.DateTime.Now
printfn "%d" (primes |> Seq.nth n)
let duration = System.DateTime.Now - start
printfn "Elapsed Time: "
System.Console.WriteLine duration

And C# looks like this:

class Program
{
    static bool isprime(int n)
    {
        foreach (int p in primes())
        {
            if (p * p > n)
                return true;
            if (n % p == 0)
                return false;
        }
        return true;
    }

    static IEnumerable<int> primes()
    {
        yield return 2;
        for (int i=3; ; i+=2)
        {
            if (isprime(i))
                yield return i;
        }
    }

    static void Main(string[] args)
    {
        int n = 1000;
        var pr = primes().GetEnumerator();
        DateTime start = DateTime.Now;
        for (int count=0; count<n; count++)
        {
            pr.MoveNext();
        }
        Console.WriteLine(pr.Current);
        DateTime end = DateTime.Now;
        Console.WriteLine("Duration " + (end - start));
    }
}

When I measure for different n I get advantage for C# of at least 7x as follows:

n= 100: C#=5milsec F#=64milsec
n= 1000: C#=22milsec F#=180milsec
n= 5000: C#=280milsec F#=2.05sec
n=10000: C#=960milsec F#=6.95sec

My questions:

Are these two programs equivalent?
If yes, why aren't they compiled into a same/equivalent CLI?
If not, why not?
How can I/Can I improve my F# prime numbers generator to perform more similar to the C# one?
Generally, can I (or why can I not) always mimic C# code in F# so my F# code would perform equally fast?

Edit1: I've realized that the algorithm itself can be improved by traversing only through odd and not prime numbers in isprime, making it non-recursive, but this is kind of perpendicular fact to the questions asked :)

One obvious difference is that takewhile and then forall might potentially involve two passes over the data which could be catastrophic particularly if the sequence doesn't get cached. — John Palmer, Mar 14 '16 at 07:50
That's a really good catch! I thought the compiler would optimize it away, but on the second thought I see it wouldn't. Then what is a good way of combining Seq.takeWhile and Seq.forall? — Огњен Шобајић, Mar 14 '16 at 08:13
If you want to go crazy, try http://stackoverflow.com/questions/12014224/when-generating-primes-in-f-why-is-the-sieve-of-erosthenes-so-slow-in-this-p/12014908#12014908 — John Palmer, Mar 14 '16 at 08:17
@JohnPalmer - I'm curious what you mean about "two passes" - `primes` will only be iterated once per call to `isprime` (as can be seen by adding some `printf`s). — kvb, Mar 14 '16 at 18:09
Seq's are known to be slow. If you want to benchmark, try to avoid them. I had some parser using seq's once and it was too slow to be useful. Left to state, that it is not actually the seq's per-se, but rather the idiomatic way of using them which produces slow code. ``Seq.take 1 ...`` produces a new sequence (immutability!). <<--- overhead. — BitTickler, Mar 15 '16 at 01:29

score 20 · Accepted Answer · answered Mar 14 '16 at 18:31

This:

Are these two programs equivalent?

is a bit of a philosophical question.

It looks to me like the output of the C# and F# implementations of isprime will always agree for any given x, so in that sense they're equivalent. However, there are many differences in terms of how you've implemented them (e.g. Seq.unfold will create an intermediate IEnumerable<_> value, then Seq.filter will create another one, so you're generating a lot more short-lived objects and using a lot more function calls in the F# code), so it's not at all surprising that they're not equivalent in terms of the low-level instructions that are generated by the respective compilers.

If you want to, you can create F# code that's much more similar to the C# code, at the expense of being much more imperative and less idiomatic:

let rec primes = 
    seq {
        yield 2
        let mutable x = 3
        while true do
            if isprime x then 
                yield x
            x <- x + 2
    }
and isprime x =
    use e = primes.GetEnumerator()
    let rec loop() =
        if e.MoveNext() then
            let p = e.Current
            if p * p > x then true
            elif x % p = 0 then false
            else loop()
        else true            
    loop()

primes |> Seq.item 5000 takes about 0.6s on my machine with this implementation, compared to about 2.7s with your implementation. I think in general the code generation for F# seq expressions is often slightly worse than that of C# iterators, so I wouldn't be surprised if the C# is still somewhat quicker to run. (But also note that some idioms end up being faster in F# than in C#, so it's not the case that F# is always slower - in my experience the two languages are pretty comparable overall, and I find writing F# code much more enjoyable).

In any case, rather than sweating the details of how to make the F# compiler's output more closely match the C# compiler's, I'd recommend looking for algorithmic improvements instead. For example, simply placing a call to Seq.cache at the end of your original definition of primes makes primes |> Seq.item 5000 take only 0.062 seconds on my machine, which is dramatically faster than the original C#.

F# vs C# performance for prime number generator

1 Answers1