Euler Project Problem 14 in F# - An exercise in optimization

The coding “coding-experiments” blog presents two alterative solutions to the “Euler Project Problem 14” (http://projecteuler.net/print.php?id=14):

http://coding-experiments.blogspot.com/2008/03/projecteulernet-problem-14-csharp-vs.html

 /o:p

His F# solution is around 55 times slower in than the C# version, the implication being that while F# is elegant, it’s also slow. My problem with this conjecture is that that the implementation of the F# version is considerably different to the implementation of the C# version. So lets have a look at the two different version, first the F#:

    let seq_length n = /o:p

        n |> /o:p

        Seq.unfold(fun x -> /o:p

                    match x with/o:p

                    | x when x = 0L -> None/o:p

                    | x when x = 1L -> Some((1L,0L))/o:p

                    | x when x%2L=0L -> Some((x,x/2L))/o:p

                    | _ -> Some((x,3L*x + 1L))/o:p

                    ) |> Seq.length/o:p

                    /o:p

    [for i in 1L..1000000L -> (i, seq_length i)]/o:p

    |> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al) )/o:p

    |> (fun (x,y) -> x ) |> print_any/o:p

 /o:p

Then the C#:

class Euler14 {/o:p

  static long CountTerms(long x, ref long[] terms) {/o:p

    long tc = 1;/o:p

    long k = x;/o:p

 /o:p

    while (k != 1) {/o:p

      tc++;/o:p

      k = (k % 2 == 0) ? k / 2 : 3 * k + 1;/o:p

      if (k <= x) {/o:p

        if (terms[k] > 0) {/o:p

          terms[x] = terms[k] + tc;/o:p

          return terms[x];/o:p

        }/o:p

      }/o:p

    }/o:p

 /o:p

    terms[x] = tc;/o:p

 /o:p

    return terms[x];/o:p

  }/o:p

 /o:p

  static long LongestSeq() {/o:p

    long max = 1000000;/o:p

    long[] termcount = new long[max + 1];/o:p

    long tcmax = 0;/o:p

    long c = 0;/o:p

    long ix = 0;/o:p

 /o:p

    for (int i = 1; i <= max; i++) {/o:p

      c = CountTerms(i, ref termcount); if (c > tcmax) {/o:p

        tcmax = c;/o:p

        ix = i;/o:p

      }/o:p

    }/o:p

 /o:p

    return ix;/o:p

  }/o:p

 /o:p

  static void Main(string[] args) {/o:p

    Console.WriteLine(LongestSeq());/o:p

  }/o:p

}

The C# executes in around 0.7 second on my machine, while the F# as given takes a whopping 29 seconds. The first thing to notice about the F# implementation is that we calculate and store the entire sequence then we calculate its length by walking the sequence again. Since we’re not interested in the sequence – just its length we can cut the time down by calculating the length straight off, this cuts us down to about 8 seconds:

let rec seq_length x n =/o:p

    match x with/o:p

    | x when x = 0L -> (n + 1)/o:p

    | x when x = 1L -> seq_length 0L (n + 1)/o:p

    | x when x%2L=0L ->seq_length (x/2L) (n + 1)/o:p

    | _ -> seq_length (3L*x + 1L) (n + 1)     /o:p

 /o:p

let rec loop i imax n =/o:p

  let n’ = seq_length i 0/o:p

  let imax, n = if n’ > n then i, n’ else imax, n/o:p

  if i < 1000000L then loop (i + 1L) imax n else imax/o:p

  /o:p

print_any (loop 1L 0L 0)

So even though that’s a big improvement, still no cigar. If we look more closely at the C# version, we see it plays a clever trick, it uses an array to memorise the lengths of sequences, so once we find a number we’ve already calculated we’ve no need to calculate it again. The simplest way to implement memorization is to use a System.Collections.Generic.Dicrionary:

#light/o:p

open System.Collections.Generic/o:p

 /o:p

let dict = new Dictionary< int64, int >()/o:p

 /o:p

let seq_length x n =/o:p

    let updateDict n =/o:p

        dict.Add(x, n)/o:p

        n/o:p

    let rec seq_length x n =/o:p

        if dict.ContainsKey(x) then/o:p

            updateDict (n + dict.[x])/o:p

        else/o:p

            match x with/o:p

            | x when x = 0L -> updateDict (n + 1)/o:p

            | x when x = 1L -> seq_length 0L (n + 1)/o:p

            | x when x%2L=0L ->seq_length (x/2L) (n + 1)/o:p

            | _ -> seq_length (3L*x + 1L) (n + 1)/o:p

    seq_length x n/o:p

 /o:p

let rec loop i imax n =/o:p

    let n’= seq_length i 0/o:p

    let imax, n = if n’ > n then i, n’ else imax, n/o:p

    if i < 1000000L then loop (i + 1L) imax n else imax/o:p

 /o:p

print_any (loop 1L 0L 0)

This takes us down to around 2.2 seconds – better but still a little way off the C# version. A bit educated guess work leads us to think this version is probably slower because, a) we used a dictionary instead of an array (although much move convent to use), b) we access tuples inside a loop cause objects to be created and we need to access properties (call methods) to retrieve the values. Cutting this out we arrive at an algorithm that is pretty much the same as the C#:

#light/o:p

let transform n = if n%2L = 0L then n/2L else n*3L+1L/o:p

 /o:p

let rec seq_length x k n memo =/o:p

  if k = 1L then/o:p

    memo.(x) <- (n+1)/o:p

    (n+1)/o:p

  else if k < 1000000L then/o:p

    let foo = memo.[int k]/o:p

    if foo > 0 then/o:p

      memo.(x) <- foo + n/o:p

      foo + n/o:p

    else/o:p

      seq_length x (transform k) (n+1) memo/o:p

  else seq_length x (transform k) (n+1) memo/o:p

 /o:p

let rec loop i imax n memo =/o:p

  let n’ = seq_length i (int64 i) 0 memo/o:p

  if i < 1000000 then/o:p

    if n’ > n then loop (i+1) i n’ memo else loop (i+1) imax n memo/o:p

  else imax/o:p

 /o:p

print_any (loop 1 1 0 (Array.create 1000001 0))

This executes in around 1 second on my machine. If we add the compile flags “–standalone -O3” we see the execution time go down to 0.85 seconds, I feel it may be possible to get closer that this but I have run out of ideas (for now). So while 0.15 seconds is significantly slower that the C# version (~21%) it’s pretty acceptable margin, and the advantages we are still considerable shorter, 23 lines versus ~60 lines.

So there you go, I think we can still safely claim that F# has a performance profile similar to C#. Having we lost some of our elegance by using arrays for memorisation, well probably, but for my money we’re still a lot more elegant and understandable that the C# version.

Thanks to Lars Nilsson, who gave me plenty of ideas to help with the optimization!

Feedback:

Feedback was imported from my only blog engine, it’s no longer possible to post feedback here.

How not to reverse a list - Chris Smith’s completely unique view

Brian McNamara, the latest addition to our stellar F# dev team, wrote up a great blog post on some pitfalls

ocaml vs. F# for big integer &amp;#8230; surprising performance test! &amp;laquo; khi&amp;#8217;s life with an ech - http://khigia.wordpress.com/2008/03/30/ocaml-vs-f-for-big-integer-surprising-performance-test/

ocaml vs. F# for big integer &amp;#8230; surprising performance test! &amp;laquo; khi&amp;#8217;s life with an ech