Realización de llamadas a función .Net (C# F #) VS C++

Question

Desde que F # 2.0 se ha convertido en parte de VS2010, me intereso por F #. Me pregunté de qué serviría. Leí un poco e hice un punto de referencia para medir llamadas de funciones. he utilizado la función de Ackermann :)

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

Una continuación
C# = 510ms
C++ = 130 ms
F # = 185ms
Java = Stackoverflow :)

¿Es el poder de F # (excepto pequeña cantidad de código) Si queremos usar .Net y obtener una ejecución un poco más rápida? ¿Puedo optimizar cualquiera de estos códigos (especialmente F #)?

ACTUALIZACIÓN. Me liberé de Console.WriteLine y ejecuté el código C# sin el depurador: C# = 400ms

Answer 1

Creo que en este caso, la diferencia entre C# y F # es gracias a la optimización de la cola de llamadas.

Una llamada de cola es cuando tiene una llamada recursiva que se hace como "lo último" en una función. En este caso, F # no genera realmente una instrucción de llamada, sino que compila el código en un bucle (porque la llamada es la "última cosa", podemos reutilizar el marco de pila actual y simplemente saltar al principio del método) .

En su implementación de ackermann, dos de las llamadas son tail-calls y solo una de ellas no (la que pasa el resultado como argumento a otra llamada ackermann). Esto significa que la versión de F # en realidad invoca una instrucción de "llamada" (¿mucho?) Con menos frecuencia.

En general, el perfil de rendimiento es más o menos el mismo que el perfil de rendimiento de C#. Hay un buen número de puestos relacionados con F # C# vs actuación aquí:

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

Answer 2

Para F # es posible que desee probar la palabra clave en línea.

Además, como se menciona en el póster anterior, las versiones C# y F # difieren debido a las instrucciones Console.WriteLine.

Answer 3

Esto es un tipo de llamada de función relacionada, ya que es un método común para reducir llamadas de función.

Puede hacer que este tipo de función recursiva vaya más rápido por medio de la memorización (almacenamiento en caché). También puede hacer esto en C# (example). Tengo 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 
    ) 

Answer 4

no directamente relacionados con la cuestión, pero lo suficientemente interesante mencionar: tratar esta versión

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

En mi PC (VS2010, F # interactiva) que es casi un 50% más rápido que su versión en el cálculo de Ackermann 3 12.

No puedo explicar por qué existe tal diferencia de rendimiento. Supongo que tiene algo que ver con el compilador de F # al traducir la expresión de coincidencia a una declaración de cambio en lugar de una serie de sentencias if. Poner la prueba (m = 0, n = 0) primero también puede haber ayudado.