Why is F# so much slower than C#? (prime number benchmark)

I thought that F# was meant to be faster than C#, I made a probably bad benchmark tool and C# got 16239ms while F# did way worse at 49583ms. Could somebody explain why this is? I'm considering leaving F# and going back to C#. Is it possible to get the same result in F# with way faster code?

Here is the code I used, I made it as equal as I possibly could.

F# (49583ms)

open System
open System.Diagnostics

let stopwatch = new Stopwatch()
stopwatch.Start()

let mutable isPrime = true

for i in 2 .. 100000 do
    for j in 2 .. i do
        if i <> j && i % j = 0 then
            isPrime <- false
    if isPrime then
        printfn "%i" i
    isPrime <- true

stopwatch.Stop()
printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds

Console.ReadKey() |> ignore

C# (16239ms)

using System;
using System.Diagnostics;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            bool isPrime = true;

            for (int i = 2; i <= 100000; i++)
            {
                for (int j = 2; j <= i; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine(i);
                }
                isPrime = true;
            }
            stopwatch.Stop();
            Console.WriteLine("Elapsed time: " + stopwatch.ElapsedMilliseconds + "ms");
            Console.ReadKey();
        }
    }
}

Solution

The F# program is slower because your programs are not equivalent. Your C# code has a break statement in the inner for loop, but your F# program does not. Thus, for every even number, the C# code will stop after checking for divisibility by 2, while the F# program will check every number from 2 to i. With such a large difference in work done, it's actually surprising that the F# code is only three times slower!

Now, F# deliberately does not have a break statement, so you can't quite translate the C# code directly to F#. But you can use functions that include short-circuiting logic. For example, in the comments, Aaron M. Eshbach suggested the following:

{2 .. 100000}
|> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))
|> Seq.iter (printfn "%i")

This uses Seq.forall, which does do short-circuiting: it will check each input in the sequence against the condition, and if the condition ever returns false, it will stop and make no more checks. (Because functions in the Seq module are lazy and will do no more work than absolutely required to get their output). This is like having a break in your C# code.

I'll go through this step by step so you can see how it works:

{2 .. 100000}

This creates a lazy sequence of ints that starts at 2 and goes up to (and including) 100000.

|> Seq.filter (fun i -> (some expression involving i))

I've broken the next line into two sections: the outer Seq.filter part, and the inner expression involving i. The Seq.filter part takes the sequence and filters it: for every item in the sequence, call it i and evaluate the expression. If that expression evaluates to true, then keep the item and pass it through to the next step in the chain. If the expression is false, then throw that item away.

Now, the expression involving i is:

{2 .. i-1} |> Seq.forall (fun j -> i % j <> 0)

This first constructs a lazy sequence that starts at 2 and goes up to i minus one, inclusive. (Or you could think of it as starting at 2 and going up to i, but not including i). It then checks whether every item of that sequence fulfills a certain condition (that's the Seq.forall function). And, as an implementation detail of Seq.forall, because it's lazy and does no more work than it absolutely has to, the minute it finds a false result it will stop and not go through the input sequence any longer. (Because once you find a single counter-example, it is no longer possible for the forall function to return true, so it stops as soon as its result is known.) And what is the expression being checked in Seq.forall? It's fun j -> i % j <> 0. So j is the inner loop variable, i is the outer variable (the one assigned in the Seq.filter part), and the logic is just the same as your C# loops.

Now, remember that we're inside a Seq.filter here. So if the Seq.forall returns true, then Seq.filter will keep the value of i. But if Seq.forall returns false, then Seq.filter will discard this value of i from passing through to the next step.

Finally, we have this line as the next (and final) step:

|> Seq.iter (printfn "%i")

What this does is pretty much exactly the same as:

for number in inputSoFar do
    printfn "%i" number

The (printfn "%i") call might look unusual to you if you're new to F#. This is currying, and it's a very useful concept and one that it's important to get used to. So spend some time thinking about this: in F#, the following two lines of code are completely equivalent:

(fun y -> someFunctionCall x y)
(someFunctionCall x)

So fun item -> printfn "%i" item can always be replaced by printfn "%i. And Seq.iter is the equivalent of a for loop:

inputSoFar |> Seq.iter (someFunctionCall x)

is exactly equivalent to:

for item in inputSoFar do
    someFunctionCall x item

So there you have it: why your F# program is slower, and also how to write an F# program that will follow the same logic as the C# one, but will have the equivalent of a break statement in it.