
Question:
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(); 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)); } }
An then
C# = 510ms
c++ = 130ms
F# = 185ms
Java = Stackoverflow :)
Is it the power of F# (except small amount of code) If we want to use .Net and gain a bit faster execution? Can I optimalize any of these codes (especially F#) ?
UPDATE. I got rid off Console.WriteLine and run the C# code without the debugger: C# = 400ms
Solution:1
I believe that in this case, the difference between C# and F# is thanks to tail-call optimization.
A tail-call is when you have a recursive call that is done as "the last thing" in a function. In this case, F# doesn't actually generate a call instruction, but instead compiles the code into a loop (because the call is the "last thing", we can reuse the current stack frame and just jump to the beginning of the method).
In your implementation of ackermann
, two of the calls are tail-calls 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 invokes a "call" instruction (much?) less often.
In generall, the performance profile is roughly the same as performance profile of C#. There are quite a few posts related to F# vs. C# performance here:
Solution:2
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 )
Solution:3
Not directly related to the question, but interesting enough to mention: try this version
let rec ackermann2 m n = 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's almost 50% faster than your version when calculating ackermann 3 12.
I can't quite explain why there's such a performance difference. I guess it has something to do with the F# compiler translating the match expression to a switch statement instead of a series of if statements. Putting the (m=0,n=0) test first may also have helped.
Solution:4
For F# you may want to try the inline keyword.
Also, as the previous poster mentioned, the C# and F# versions differ due to the Console.WriteLine statements.
Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
EmoticonEmoticon