Making a .Net (C # F #) function call VS C ++

Question

Since F # 2.0 has become part of VS2010, I am showing interest in F #. I wondered what was the point of using it. I read a little and I made a benchmark for measuring function calls. I used the Ackerman function :)

FROM#

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 mn = 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(); printfn "F# ackermann(3,10) = %d" x printfn "Time required for execution: %f" stopWatch.Elapsed.TotalMilliseconds 

Java

 public class Main { 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; } public static void main(String[] args) { System.out.println(Main.ackermann(3,10)); } } 

And then
C # = 510ms
C ++ = 130ms
F # = 185 ms
Java = Stackoverflow :)

Is this the power of F # (except for a bit of code). Should we want to use .Net and speed things up a bit? Can I optimize any of these codes (especially F #)?

UPDATE I got rid of Console.WriteLine and ran C # code without debugger: C # = 400 ms

Answer 1

I believe that in this case the difference between C # and F # is to optimize the tail call.

A tail call is when you have a recursive call that is executed as the "last thing" in a function. In this case, F # does not actually generate a call command, but instead compiles the code into a loop (since the call is the "last thing", we can reuse the current stack stack and just skip to the beginning of the method)

In your ackermann implementation ackermann two of the calls are callbacks, and only one of them is not (the one where the result is passed as an argument to another ackermann call). This means that the F # version actually calls the “call” statement (much?) Less often.

In general, the performance profile is about the same as the C # performance profile. There are quite a few posts related to the performance of F # and C # here:

• Is F # Better Than C # For Math?

Answer 2

This is a kind of function call, due to the fact that this is a common method of reducing function calls.

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

 open System.Collections.Generic let memoize2 f = let cache = Dictionary<_, _>() fun xy -> if cache.ContainsKey (x, y) then cache.[(x, y)] else let res = fxy cache.[(x, y)] <- res res // Ackermann let rec ackermann = memoize2 (fun mn -> 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 ) 

Answer 3

Not directly related to the issue, but interesting enough to mention: try this version

 let rec ackermann2 mn = match m,n with | 0,0 -> 0 | 0,n -> n+1 | m,0 -> ackermann2 (m-1) 1 | m,n -> ackermann2 (m-1) (ackermann2 m (n-1)) 

On my PC (VS2010, F # interactive) it is almost 50% faster than your version when calculating ackermann 3 12.

I can not explain why there is such a difference in performance. I assume this has something to do with the F # compiler translating the match expression into a switch statement instead of a series of if statements. Perhaps it also helped to run the test (m = 0, n = 0).

Answer 4

For F #, you can try the inline keyword.

Also, as mentioned in a previous post, C # and F # versions are different due to Console.WriteLine statements.