Performances de l'appel de fonction .Net (C# F #) VS C++

Question

Depuis que F # 2.0 fait partie de VS2010, je m'intéresse à F #. Je me demandais à quoi ça sert de l'utiliser. J'avais lu un peu et j'ai fait un benchmark pour mesurer les fonctions d'appel. Je l'ai utilisé la fonction 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)); 
    } 
} 

Un alors
C# = 510ms
C++ = 130ms
F # = 185ms
Java = Stackoverflow :)

Est-ce la puissance de F # (sauf petite quantité de code) Si nous voulons utiliser .Net et gagner une exécution un peu plus rapide? Puis-je optimiser l'un de ces codes (en particulier F #)?

MISE À JOUR. Je me suis débarrassé de Console.WriteLine et exécuter le code C# sans le débogueur: C# = 400ms

Answer 1

Je crois que dans ce cas, la différence entre C# et F # est grâce à l'optimisation de la queue-appel. Un appel de fin est lorsque vous avez un appel récursif qui est fait comme "la dernière chose" dans une fonction. Dans ce cas, F # ne génère pas réellement d'instruction d'appel, mais compile le code dans une boucle (parce que l'appel est la "dernière chose", nous pouvons réutiliser le cadre de pile actuel et passer directement au début de la méthode) . Dans votre implémentation de ackermann, deux des appels sont des appels de fin et un seul n'est pas (celui où le résultat est passé en tant qu'argument à un autre appel ackermann). Cela signifie que la version F # appelle moins souvent une instruction "call" (beaucoup?).

En général, le profil de performance est à peu près le même que le profil de performance de C#. Il y a tout à fait quelques commentaires à F # par rapport à la performance C# ici:

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

Answer 2

Pour F # vous voudrez peut-être essayer le mot-clé en ligne. En outre, comme l'affiche précédente mentionnée, les versions C# et F # diffèrent en raison des instructions Console.WriteLine.

Answer 3

Il s'agit d'une fonction d'appel liée aux fonctions, car il s'agit d'une méthode courante pour réduire les appels de fonction.

Vous pouvez rendre ce type de fonction récursive plus rapide grâce à la mémoisation (mise en cache). Vous pouvez également le faire en C# (example.) J'ai 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

pas directement lié à la question, mais assez intéressant de mentionner: essayez cette 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)) 

Sur mon PC (VS2010, F # interactive), il est presque 50% plus rapide que votre version lors du calcul ackermann 3 12.

Je ne peux pas vraiment expliquer pourquoi il y a une telle différence de performance. Je suppose que cela a quelque chose à voir avec le compilateur F # traduisant l'expression de correspondance en une instruction switch au lieu d'une série d'instructions if. Mettre le test (m = 0, n = 0) en premier peut aussi avoir aidé. Exécutez votre méthode une fois avant d'exécuter le test de performance.