- A+

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(); } } } `

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.