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 :)

Answer 1

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#.