F# vs C# performance for prime number generator

Viewed 1024

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

1 Answers
Related