Euler 23 in C#: 0.2 seconds, in F#: 30.5 seconds. Why?

Question

I am not really satisfied with my F# solution to this problem because I can't find a beautiful & fast solution, but that's not the issue here. The issue is, I translated the solution to C# for the heck of it, and it is fast. Like, really fast, comparatively.

I can't figure out why. Yes, I've been to Reflector, C# code looks very similar, can't say I really understand IL but it looks kinda like the same. The only thing I can think of is performance of F# int[] against C# List.

So here it goes:

F#

module Euler023

let divisorsSum n =
  let mutable sum = 1
  let limit = (int (sqrt(float n)))
  for i in [2..limit] do
    if n%i=0 then sum <- sum+i+n/i
  if (limit*limit)=n then sum-limit else sum

let isAbundant x = (divisorsSum x)>x
let abundants  = [1..28123] |> List.filter isAbundant |> List.toArray
let domain = System.Collections.BitArray(28124)

let rec loopUntil i j =
    if i=abundants.Length then ()
    elif j=abundants.Length then loopUntil (i+1) (i+1)
    else
      let sum = abundants.[i]+abundants.[j] 
      if sum<28124 then 
        domain.Set(sum, true)
        loopUntil i (j+1)
      else 
        loopUntil (i+1) (i+1)

let solve  =    loopUntil 0 0
            [1..28123] |> List.filter (fun x -> domain.Get(x)=false) |> List.sum

C#

static int divisorsSum(int n)
{
    int sum = 0;
    var limit = (int)Math.Sqrt(n);

    for (int i=2;i<=limit;++i) if (n%i==0) sum += i + n/i;

    if ((limit * limit) == n) return sum-limit;

    return sum;
}

static List<int> getAbundants(int ceiling)
{
    var ret = new List<int>();

    for (int i = 1; i < ceiling; ++i) if (divisorsSum(i) > i) ret.Add(i);

    return ret;
}

 static void Main(string[] args)
 {

     var abundants = getAbundants(28124);
     var bitField = new bool[28124];

     for (int i = 0; i < abundants.Count; ++i)
         for (int j = i; j < abundants.Count; ++j)
         {
             var sum = abundants[i] + abundants[j];
             if (sum < 28124) bitField[sum] = true;
             else break;
         }

     var total = 0;
     for (int i = 0; i < 28124; ++i) if (bitField[i]==false) total += i;

}

Update

The project containing this code consists of a separate file for each problem (EulerXXX.fs) + the main program file. Main program file is as follows

module Program =


let stopWatch = System.Diagnostics.Stopwatch()
let mutable totalTime = System.TimeSpan()

let inline tick()
 = 
    stopWatch.Stop();
    totalTime <- totalTime.Add stopWatch.Elapsed
    printfn " -> Elapsed: %2.2f sec Total: %2.2f s" stopWatch.Elapsed.TotalSeconds  totalTime.TotalSeconds
    stopWatch.Restart()

let _ = 

    stopWatch.Start()
    printf "Euler001 solution: %A" Euler001.solve
    tick()
    printf "Euler002 solution: %A" Euler002.solve
    tick()
    printf "Euler003 solution: %A" Euler003.solve
    tick()
    printf "Euler004 solution: %A" Euler004.solve
    tick()
    printf "Euler005 solution: %A" Euler005.solve
    tick()
    printf "Euler006 solution: %A" Euler006.solve
    tick()
    printf "Euler007 solution: %A" Euler007.solve
    tick()
    printf "Euler008 solution: %A" Euler008.solve
    tick()
    printf "Euler009 solution: %A" Euler009.solve
    tick()
    printf "Euler010 solution: %A" Euler010.solve
    tick()
    printf "Euler011 solution: %A" Euler011.solve
    tick()
    printf "Euler012 solution: %A" Euler012.solve
    tick()
    printf "Euler013 solution: %A" Euler013.solve
    tick()
    printf "Euler014 solution: %A" Euler014.solve
    tick()
    printf "Euler015 solution: %A" Euler015.solve
    tick()
    printf "Euler016 solution: %A" Euler016.solve
    tick()
    printf "Euler017 solution: %A" Euler017.solve
    tick()
    printf "Euler018 solution: %A" Euler018.solve
    tick()
    printf "Euler019 solution: %A" Euler019.solve
    tick()
    printf "Euler020 solution: %A" Euler020.solve
    tick()
    printf "Euler021 solution: %A" Euler021.solve
    tick()
    printf "Euler022 solution: %A" Euler022.solve
    tick()
    printf "Euler023 solution: %A" Euler023.solve
    tick()
    printf "Euler024 solution: %A" Euler024.solve
    tick()
    printf "Euler059 solution: %A" Euler059.solve
    tick()
    printf "Euler067 solution: %A" Euler067.solve
    tick()
    stopWatch.Stop()
    System.Console.ReadLine()

The output of the program is as follows:

Euler001 solution: 233168 -> Elapsed: 0.02 sec Total: 0.02 s
Euler002 solution: 4613732 -> Elapsed: 0.03 sec Total: 0.04 s
...
Euler022 solution: 871198282 -> Elapsed: 0.02 sec Total: 4.11 s
Euler023 solution: 4179871 -> Elapsed: 81.11 sec Total: 85.22 s
Euler024 solution: [2; 7; 8; 3; 9; 1; 5; 4; 6; 0] -> Elapsed: 0.01 sec Total: 85.23 s
...
Euler067 solution: [7273] -> Elapsed: 0.01 sec Total: 85.31 s

So the problem is not in project parameters. Also, if I copy code from Euler023 to Program it will run instantly. The question is, why does this slowdown happen only for this problem?

Have you considered using a profiler to find out which bit of your statement that actually takes time? =) — J. Steen, Aug 20 '12 at 11:05
I don't need to profile it, loopUntil is slow. It is slow regardless of what is in it. The question is, if the C# from the Reflector is pretty much the same, why? And second, how do you implement a nested loop with a break in F# that is not dead slow? — CxDoo, Aug 20 '12 at 13:02
@Hans - there is no recursion here, it's just a fancy way of writing while loops. With abundants.Length at ~ 7k you need a stack 24 million times whatever deep. It wouldn't be slow, it'd explode pretty much immediatelly. — CxDoo, Aug 21 '12 at 06:37
On my FSI, the F# code takes 2.5 seconds, 1.5 of them because of `abundants`'s initiation. `loopUntil 0 0` takes 0.35 seconds. — Ramon Snir, Aug 21 '12 at 07:00
Ok, I found out that this snippet in a separate project runs fast. As a part of a project containing all other Euler solutions (even with everything else commented out) it is slow. — CxDoo, Aug 21 '12 at 07:58
@CxDoo: It doesn't make sense. If your project doesn't use other Euler solutions, those solutions have no effect to execution time. Maybe there is difference between configurations of two projects. — pad, Aug 21 '12 at 08:59

pad · Accepted Answer · 2013-01-11T15:52:40.140

Your F# version isn't slow at all; it takes 0.44 seconds in F# Interactive on my machine. I don't know how you could observe such a slowness (30.5 seconds). If you compile and run the code, make sure that you're in Release mode and turning on optimization and tail call elimination.

However, you still can optimize further by eliminating the use of redundant intermediate collections.

A. Change (redundant) list [2..limit] to range expression 2..limit in divisorsSum:

for i in 2..limit do
    if n%i=0 then sum <- sum+i+n/i

B. Generate array of abundants without creating the big list (more faithful to C# version):

let abundants = 
    let arr = ResizeArray(28123)
    for i in 1..28123 do
        if isAbundant i then arr.Add i
    arr.ToArray()

C. Calculate solve without creating the big list:

let solve = 
    loopUntil 0 0
    let mutable sum = 0
    for i in 1..28123 do
       if not <| domain.Get(i) then
            sum <- sum + i
    sum

The new F# version is 4x faster than the original one; it takes about 0.1 seconds to complete.

UPDATE:

Your measurement is inaccurate. First, you measured time difference between two calls of printing values. Second, EulerXXX.solve are values; so they are pre-calculated when you compiled your program. You should declare EulerXXX.solve as functions:

let solve() = ...

and measure execution time of function calls:

let time fn =
    let sw = new System.Diagnostics.Stopwatch()
    sw.Start()
    let f = fn()
    sw.Stop()
    printfn "Time taken: %.2f s" <| (float sw.ElapsedMilliseconds)/1000.0
    f

let s023 = time Euler023.solve
printf "Euler023 solution: %A" s023

This actually did it, but I still don't get why. I had solve as a value in Program module and it was fast. I had timing functions commented out. — CxDoo, Aug 21 '12 at 11:49

Euler 23 in C#: 0.2 seconds, in F#: 30.5 seconds. Why?

F#

C#

Update

1 Answers1

Linked