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

Question

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

Answer 1

As other mentioned the code is not doing the same thing and you need to employ techniques to ensure that the inner loop is stopped after a prime is found.

In addition, you are printing values to standard out. This is usually not desired when you are doing CPU performance tests as a significant amount of time might be I/O skewing the results of the tests.

Anyway, even though there is an accepted answer I decided to tinker a bit with this as well to see compare the different proposed solutions with some of my own.

The performance run is in x64 mode on .NET 4.7.1.

I compared the different proposed F# solutions plus some of my own variants:

Running 'Original(F#)' with 100000 (10512)...
  ... it took 14533 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Original(C#)' with 100000 (10512)...
  ... it took 1343 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Aaron' with 100000 (10512)...
  ... it took 5027 ms with (3, 1, 0) cc and produces 9592 GOOD primes
Running 'SteveJ' with 100000 (10512)...
  ... it took 1640 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo1' with 100000 (10512)...
  ... it took 1908 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo2' with 100000 (10512)...
  ... it took 970 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Simple' with 100000 (10512)...
  ... it took 621 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'PushStream' with 100000 (10512)...
  ... it took 1627 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Unstalling' with 100000 (10512)...
  ... it took 551 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Vectors' with 100000 (10512)...
  ... it took 1076 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'VectorsUnstalling' with 100000 (10512)...
  ... it took 1072 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'BestAttempt' with 100000 (10512)...
  ... it took 4 ms with (0, 0, 0) cc and produces 9592 GOOD primes  

1. Original(F#) - The original F# code by OP changed to not use stdout
2. Original(C#) - The original C# code by OP changed to not use stdout
3. Aaron - The idiomatic approach using Seq. As expected Seq and performance usually don't go well together.
4. SteveJ - @SteveJ tried to mimic the C# code in F#
5. Dumetrulo1 - @dumetrulo implemented the algorithm in tail recursion
6. Dumetrulo2 - @dumetrulo improved the algorithm by stepping +2 instead of +1 (don't need to check even numbers).
7. Simple - My attempt to use a similar approach to Dumetrulo2 with tail recursion.
8. PushStream - My attempt to use a simplistic push stream (Seq is a pull stream)
9. Unstalling - My attempt to try to unstall the CPU in case the instructions used have latency
10. Vectors - My attempt using System.Numerics.Vectors to do multiple divisions per operation (aka SIMD). Unfortunately the vectors libary don't support mod so I had to emulate it.
11. VectorsUnstalling - My attempt to improve Vectors by trying to unstall the CPU.
12. BestAttempt - Like Simple but only checks numbers up to sqrt n when determining if is prime.

Wrapping up

1. F# loops don't have continue nor break. Tail-recursion in F# is IMO a better way to implement loops that need to break.
2. When comparing performance of languages should one compare the best possible performance or compare performance of idiomatic solutions? I personally think the best possible performance is the right way to go but I know people disagree with me (I wrote a mandelbrot version for benchmark the game for F# with comparable performance to C but it wasn't accepted because the style was seen as non-idiomatic for F#).
3. Seq in F# unfortunately adds significant overhead. I have a hard time bringing myself to use it even when the overhead is not relevant.
4. Modern CPUs instructions have different numbers for throughput and latency. This means that sometimes in order to speed up performance one need to process multiple independent samples in the inner loop to allow the out of order execution unit to reorder the program to hide the latency. If your CPU has hyper threading and you run the algorithm on multiple threads hyper threading can mitigate the latency "automatically".
5. The lack of mod of vectors prevented the attempt to use SIMD to gain any performance over the non SIMD solution.
6. If I modify Unstalling attempt to loop the same number of times as the C# code the final result is 1100 ms in F# compared to 1343 ms in C#. So F# can be made to run very much comparable to C#. If one apply a few more tricks it only takes 4 ms but it would be the same for C# as well. Anyway, pretty decent to go from almost 15 sec to 4 ms.

Hope it was interesting to someone

Full source code:

module Common = 
  open System
  open System.Diagnostics

  let now =
    let sw = Stopwatch ()
    sw.Start ()
    fun () -> sw.ElapsedMilliseconds

  let time i a =
    let inline cc i       = GC.CollectionCount i

    let ii = i ()

    GC.Collect (2, GCCollectionMode.Forced, true)

    let bcc0, bcc1, bcc2  = cc 0, cc 1, cc 2
    let b                 = now ()

    let v = a ii

    let e = now ()
    let ecc0, ecc1, ecc2  = cc 0, cc 1, cc 2

    v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2

  let limit    = 100000
  // pi(x) ~= limit/(ln limit - 1)
  // Using pi(x) ~= limit/(ln limit - 2) to over-estimate
  let estimate = float limit / (log (float limit) - 1.0 - 1.0) |> round |> int

module Original =
  let primes limit =
    let ra = ResizeArray Common.estimate

    let mutable isPrime = true

    for i in 2 .. limit do
      for j in 2 .. i do
        if i <> j && i % j = 0 then
          isPrime <- false
      if isPrime then
          ra.Add i
      isPrime <- true

    ra.ToArray ()

module SolutionAaron =
  let primes limit =
    {2 .. limit}
    |> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))
    |> Seq.toArray

module SolutionSteveJ =
  let primes limit =
    let ra = ResizeArray Common.estimate
    let mutable loop = true

    for i in 2 .. limit do
        let mutable j = 2
        while loop do
            if i <> j && i % j = 0 then
                loop <- false
            else
                j <- j + 1
                if j >= i then
                    ra.Add i
                    loop <- false
        loop <- true

    ra.ToArray ()

module SolutionDumetrulo1 =
  let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
    if i > limit then ra.ToArray ()
    elif j > i then
      ra.Add i
      isPrimeLoop ra (i + 1) 2 limit
    elif i <> j && i % j = 0 then
      isPrimeLoop ra (i + 1) 2 limit
    else
      isPrimeLoop ra i (j + 1) limit

  let primes limit =
    isPrimeLoop (ResizeArray Common.estimate) 2 2 limit

module SolutionDumetrulo2 =
  let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
    let incr x = if x = 2 then 3 else x + 2
    if i > limit then ra.ToArray ()
    elif j > i then
      ra.Add i
      isPrimeLoop ra (incr i) 2 limit
    elif i <> j && i % j = 0 then
      isPrimeLoop ra (incr i) 2 limit
    else
      isPrimeLoop ra i (incr j) limit

  let primes limit =
    isPrimeLoop (ResizeArray Common.estimate) 2 2 limit

module SolutionSimple =
  let rec isPrime i j k =
    if i < k then
      (j % i) <> 0 && isPrime (i + 2) j k
    else
      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
    if i < limit then 
      if isPrime 3 i i then
        ra.Add i
      isPrimeLoop ra (i + 2) limit
    else
      ra.ToArray ()

  let primes limit =
    let ra = ResizeArray Common.estimate
    ra.Add 2
    isPrimeLoop ra 3 limit

module SolutionPushStream =
  type Receiver<'T> = 'T -> bool
  type PushStream<'T> = Receiver<'T> -> bool

  module Details =
    module Loops =
      let rec range e r i =
        if i <= e then
          if r i then
            range e r (i + 1)
          else
            false
        else
          true

  open Details

  let range s e : PushStream<int> =
    fun r -> Loops.range e r s

  let filter p (t : PushStream<'T>) : PushStream<'T> =
    fun r -> t (fun v -> if p v then r v else true)

  let forall p (t : PushStream<'T>) : bool =
    t p

  let toArray (t : PushStream<'T>) : _ [] =
    let ra = ResizeArray 16

    t (fun v -> ra.Add v; true) |> ignore

    ra.ToArray ()

  let primes limit =
    range 2 limit
    |> filter (fun i -> range 2 (i - 1) |> forall (fun j -> i % j <> 0))
    |> toArray

module SolutionUnstalling =
  let rec isPrime i j k =
    if i + 6 < k then
      (j % i) <> 0 && (j % (i + 2)) <> 0 && (j % (i + 4)) <> 0 && (j % (i + 6)) <> 0  && isPrime (i + 8) j k
    else
      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
    if i < limit then 
      if isPrime 3 i i then
        ra.Add i
      isPrimeLoop ra (i + 2) limit
    else
      ra.ToArray ()

  let primes limit =
    let ra = ResizeArray Common.estimate
    ra.Add 2
    ra.Add 3
    ra.Add 5
    ra.Add 7
    ra.Add 11
    ra.Add 13
    ra.Add 17
    ra.Add 19
    ra.Add 23
    isPrimeLoop ra 29 limit

module SolutionVectors =
  open System.Numerics

  assert (Vector<int>.Count = 4)

  type I4 = Vector<int>

  let inline (%%) (i : I4) (j : I4) : I4 =
    i - (j * (i / j))

  let init : int [] = Array.zeroCreate 4

  let i4 v0 v1 v2 v3 =
    init.[0] <- v0
    init.[1] <- v1
    init.[2] <- v2
    init.[3] <- v3
    I4 init

  let i4_ (v0 : int) =
    I4 v0

  let zero    = I4.Zero
  let one     = I4.One 
  let two     = one + one
  let eight   = two*two*two

  let step = i4 3 5 7 9

  let rec isPrime (i : I4) (j : I4) k l =
    if l + 6 < k then
      Vector.EqualsAny (j %% i, zero) |> not && isPrime (i + eight) j k (l + 8)
    else
      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
    if i < limit then 
      if isPrime step (i4_ i) i 3 then
        ra.Add i
      isPrimeLoop ra (i + 2) limit
    else
      ra.ToArray ()

  let primes limit =
    let ra = ResizeArray Common.estimate
    ra.Add 2
    ra.Add 3
    ra.Add 5
    ra.Add 7
    ra.Add 11
    ra.Add 13
    ra.Add 17
    ra.Add 19
    ra.Add 23
    isPrimeLoop ra 29 limit

module SolutionVectorsUnstalling =
  open System.Numerics

  assert (Vector<int>.Count = 4)

  type I4 = Vector<int>

  let init : int [] = Array.zeroCreate 4

  let i4 v0 v1 v2 v3 =
    init.[0] <- v0
    init.[1] <- v1
    init.[2] <- v2
    init.[3] <- v3
    I4 init

  let i4_ (v0 : int) =
    I4 v0

  let zero    = I4.Zero
  let one     = I4.One 
  let two     = one + one
  let eight   = two*two*two
  let sixteen = two*eight

  let step = i4 3 5 7 9

  let rec isPrime (i : I4) (j : I4) k l =
    if l + 14 < k then
      // i - (j * (i / j))      
      let i0 = i
      let i8 = i + eight
      let d0 = j / i0
      let d8 = j / i8
      let n0 = i0 * d0
      let n8 = i8 * d8
      let r0 = j - n0
      let r8 = j - n8
      Vector.EqualsAny (r0, zero) |> not && Vector.EqualsAny (r8, zero) |> not && isPrime (i + sixteen) j k (l + 16)
    else
      true

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
    if i < limit then 
      if isPrime step (i4_ i) i 3 then
        ra.Add i
      isPrimeLoop ra (i + 2) limit
    else
      ra.ToArray ()

  let primes limit =
    let ra = ResizeArray Common.estimate
    ra.Add 2
    ra.Add 3
    ra.Add 5
    ra.Add 7
    ra.Add 11
    ra.Add 13
    ra.Add 17
    ra.Add 19
    ra.Add 23
    isPrimeLoop ra 29 limit

module SolutionBestAttempt =
  let rec isPrime i j k =
    if i < k then
      (j % i) <> 0 && isPrime (i + 2) j k
    else
      true

  let inline isqrt i = (i |> float |> sqrt) + 1. |> int

  let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
    if i < limit then 
      if isPrime 3 i (isqrt i) then
        ra.Add i
      isPrimeLoop ra (i + 2) limit
    else
      ra.ToArray ()

  let primes limit =
    let ra = ResizeArray Common.estimate
    ra.Add 2
    isPrimeLoop ra 3 limit

[<EntryPoint>]
let main argv =

  let testCases =
    [|
      "Original"    , Original.primes
      "Aaron"       , SolutionAaron.primes
      "SteveJ"      , SolutionSteveJ.primes
      "Dumetrulo1"  , SolutionDumetrulo1.primes
      "Dumetrulo2"  , SolutionDumetrulo2.primes
      "Simple"            , SolutionSimple.primes
      "PushStream"        , SolutionPushStream.primes
      "Unstalling"        , SolutionUnstalling.primes
      "Vectors"           , SolutionVectors.primes
      "VectorsUnstalling" , SolutionVectors.primes
      "BestAttempt"       , SolutionBestAttempt.primes
    |]

  do
    // Warm-up
    printfn "Warm up"
    for _, a in testCases do
      for i = 0 to 100 do
        a 100 |> ignore

  do
    let init ()   = Common.limit

    let expected  = SolutionSimple.primes Common.limit

    for testCase, a in testCases do
      printfn "Running '%s' with %d (%d)..." testCase Common.limit Common.estimate
      let actual, time, cc0, cc1, cc2 = Common.time init a
      let result = if expected = actual then "GOOD" else "BAD"
      printfn "  ... it took %d ms with (%d, %d, %d) cc and produces %d %s primes" time cc0 cc1 cc2 actual.Length result 

  0

Answer 2

If you want an iterative F# function completely equivalent to the for loops in C#, you can use the following tail-recursive function:

let rec isPrimeLoop i j limit =
    if i > limit then ()
    elif j > i then
        stdout.WriteLine (string i)
        isPrimeLoop (i + 1) 2 limit
    elif i <> j && i % j = 0 then
        isPrimeLoop (i + 1) 2 limit
    else
        isPrimeLoop i (j + 1) limit

As you can see, due to the way it calls itself, the isPrime flag is no longer needed. In place of the nested for loops, call it as follows:

let sw = System.Diagnostics.Stopwatch.StartNew ()
isPrimeLoop 2 2 100000
sw.Stop ()
printfn "Elapsed time: %ims" sw.ElapsedMilliseconds

PS: You can cut the time significantly by checking only the odd numbers after 2:

let rec isPrimeLoop i j limit =
    let incr x = if x = 2 then 3 else x + 2
    if i > limit then ()
    elif j > i then
        stdout.WriteLine (string i)
        isPrimeLoop (incr i) 2 limit
    elif i <> j && i % j = 0 then
        isPrimeLoop (incr i) 2 limit
    else
        isPrimeLoop i (incr j) limit

Answer 3

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.

Answer 4

I know there's an already accepted answer, but just wanted to add this.

Done a lot of C# over the years, but not much F#. The following would be more equivalent to the C# code.

open System
open System.Diagnostics

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

let mutable loop = true

for i in 2 .. 100000 do
    let mutable j = 2
    while loop do
        if i <> j && i % j = 0 then
            loop <- false
        else
            j <- j + 1
            if j >= i then
                printfn "%i" i
                loop <- false
    loop <- true

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

And in my tests on LinqPad, the above is faster than the solution suggested by Aaron M. Eshbach.

It also comes out with surprisingly similar IL.