Alex Rivera | Logout

Performance of .Net function calling (C# F#) VS C++

Asked 2010-07-13T22:09:47.830
9

Since F# 2.0 has become a part of VS2010 I take an interest in F#. I wondered what's the point of using it. I'd read a bit and I made a benchmark to measure functions calling. I have used Ackermann's function :)

C#

sealed class Program
{
    public static int ackermann(int m, int n)
    {
        if (m == 0)
            return n + 1;
        if (m > 0 && n == 0)
        {
            return ackermann(m - 1, 1);
        }
        if (m > 0 && n > 0)
        {
            return ackermann(m - 1, ackermann(m, n - 1));
        }
        return 0;
    }

    static void Main(string[] args)
    {

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();
        Console.WriteLine("C# ackermann(3,10) = " + Program.ackermann(3, 10));
        stopWatch.Stop();

        Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");
        Console.ReadLine();
    }
}

C++

class Program{
public:
static inline int ackermann(int m, int n)
{
  if(m == 0)
       return n + 1;
  if (m > 0 && n == 0)
  {
      return ackermann(m - 1, 1);
  }
  if (m > 0 && n > 0)
  {
      return ackermann(m - 1, ackermann(m, n - 1));
  }
  return 0;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 clock_t start, end;

  start = clock();
 std::cout << "CPP: ackermann(3,10) = " << Program::ackermann(3, 10) << std::endl;
 end = clock();
 std::cout << "Time required for execution: " << (end-start) << " ms." << "\n\n";
 int i;
 std::cin >> i;
 return 0;
}

F#

// Ackermann
let rec ackermann m n  =
  if m = 0 then n + 1
  elif m > 0 && n = 0 then ackermann (m - 1) 1
  elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
  else 0

open System.Diagnostics;
let stopWatch = Stopwatch.StartNew()
let x = ackermann 3 10 
stopWatch.Stop();

print
Edit
Report

1 Answer

6

This is kind of function calling related since it's a common method to reduce function calls.

You can make this type of recursive function go faster by way of memoization (caching). You can also do this in C# (example.) I got 18ms.

open System.Collections.Generic

let memoize2 f =
    let cache = Dictionary<_, _>()
    fun x y ->
        if cache.ContainsKey (x, y) then 
            cache.[(x, y)]
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// Ackermann
let rec ackermann =
    memoize2 (fun m n ->
        if m = 0 then n + 1
        elif m > 0 && n = 0 then ackermann (m - 1) 1
        elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
        else 0
    )
answered 2010-07-14T00:21:30.170

Your Answer