Выполнение вызова функции .Net (C# F #) VS C++

Question

Поскольку F # 2.0 стал частью VS2010, я проявляю интерес к F #. Я задавался вопросом, в чем смысл использовать его. Я читал немного, и я сделал контрольный показатель для измерения вызовов функций. Я использовал функцию Аккермана :)

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)); 
    } 
} 

затем
C# = 510ms
C++ = 130ms
F # = 185ms
Java = Stackoverflow :)

Это сила F # (за исключением небольшого количества кода) Если мы хотим использовать .Net и немного ускорить выполнение? Могу ли я оптимизировать любой из этих кодов (особенно F #)?

ОБНОВЛЕНИЕ. Я избавился от Console.WriteLine и запустил код C# без отладчика: C# = 400ms

Answer 1

Я считаю, что в этом случае разница между C# и F # заключается в оптимизации хвостового вызова.

Хвост-вызов - это когда у вас есть рекурсивный вызов, который выполняется как «последняя вещь» в функции. В этом случае F # фактически не генерирует команду вызова, а вместо этого компилирует код в цикл (поскольку вызов является «последней вещью», мы можем повторно использовать текущий стек стека и просто перейти к началу метода) ,

В вашей реализации ackermann два вызова являются обратными вызовами, и только один из них не является (тот, где результат передается в качестве аргумента другому вызову ackermann). Это означает, что версия F # фактически вызывает инструкцию «вызов» (много?) Реже.

В общем случае профиль производительности примерно такой же, как и профиль производительности C#. Есть довольно много сообщений, связанных с F # против C# производительности здесь:

• Is F# really better than C# for math?

Answer 2

Для F # вы можете попробовать встроенный ключевое слово.

Кроме того, как упоминалось в предыдущем посте, версии C# и F # отличаются из-за операторов Console.WriteLine.

Answer 3

Это своего рода вызов функции, связанный с тем, что это обычный метод сокращения вызовов функций.

Вы можете сделать этот тип рекурсивной функции быстрее с помощью memoization (кеширования). Вы также можете сделать это в C# (example.) Я получил 18 мс.

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 
    ) 

Answer 4

Не напрямую связана с вопросом, но достаточно интересно отметить: попробуйте эту версию

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)) 

На моем компьютере (VS2010, F # интерактивный) это почти 50% быстрее, чем версия при расчете Ackermann 3 12.

Я не могу объяснить, почему существует такая разница в производительности. Я предполагаю, что это имеет какое-то отношение к компилятору F #, переводящему выражение соответствия в оператор switch вместо ряда операторов if. Возможно, также помогло поставить тест (m = 0, n = 0).