Pourquoi est-ce code F# - elle si lente?

Un Levenshtein mise en œuvre en C# et F#. La version C# est 10 fois plus rapide pour les deux chaînes d'environ 1500 caractères. C#: 69 ms, F# 867 mme. Pourquoi? Aussi loin que je peux dire, qu'ils font exactement la même chose? N'a pas d'importance si c'est une Version ou d'une version de Débogage.

EDIT: Si quelqu'un vient ici à la recherche spécifiquement pour la Distance d'Édition mise en œuvre, il est cassé. Code de travail est ici.

C#:

private static int min3(int a, int b, int c)
{
   return Math.Min(Math.Min(a, b), c);
}

public static int EditDistance(string m, string n)
{
   var d1 = new int[n.Length];
   for (int x = 0; x < d1.Length; x++) d1[x] = x;
   var d0 = new int[n.Length];
   for(int i = 1; i < m.Length; i++)
   {
      d0[0] = i;
      var ui = m[i];
      for (int j = 1; j < n.Length; j++ )
      {
         d0[j] = 1 + min3(d1[j], d0[j - 1], d1[j - 1] + (ui == n[j] ? -1 : 0));
      }
      Array.Copy(d0, d1, d1.Length);
   }
   return d0[n.Length - 1];
}

F#:

let min3(a, b, c) = min a (min b c)

let levenshtein (m:string) (n:string) =
   let d1 = Array.init n.Length id
   let d0 = Array.create n.Length 0
   for i=1 to m.Length-1 do
      d0.[0] <- i
      let ui = m.[i]
      for j=1 to n.Length-1 do
         d0.[j] <- 1 + min3(d1.[j], d0.[j-1], d1.[j-1] + if ui = n.[j] then -1 else 0)
      Array.blit d0 0 d1 0 n.Length
   d0.[n.Length-1]
Quelle est la performance de diff en ligne?

OriginalL'auteur Robert Jeppesen | 2011-05-23

  1. 196

    Le problème est que le min3 fonction est compilé comme une fonction générique qui utilise générique de comparaison (je pensais que ce n'utilise qu' IComparable, mais il est en fait plus compliqué qu'il faudrait utiliser la comparaison structurelle de types F#, et il est assez logique complexe).

    > let min3(a, b, c) = min a (min b c);;
val min3 : 'a * 'a * 'a -> 'a when 'a : comparison

    Dans la version C#, la fonction n'est pas générique (il faut juste int). Vous pouvez améliorer le F# version en ajoutant des annotations de type (pour obtenir la même chose qu'en C#):

    let min3(a:int, b, c) = min a (min b c)

    ...ou en faisant min3 comme inline (auquel cas, il sera spécialisé pour int lorsque utilisé):

    let inline min3(a, b, c) = min a (min b c);;

    Pour une chaîne de caractères aléatoires str d'une longueur de 300, - je obtenir les numéros suivants:

    > levenshtein str ("foo" + str);;
Real: 00:00:03.938, CPU: 00:00:03.900, GC gen0: 275, gen1: 1, gen2: 0
val it : int = 3

> levenshtein_inlined str ("foo" + str);;
Real: 00:00:00.068, CPU: 00:00:00.078, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 3
    Pourquoi ne pas F# compiler min3 comme une fonction qui prend un int? Il sait déjà suffisamment d'informations de type au moment de la compilation pour ce faire. C'est de cette façon que cela fonctionnerait si min3 était en C++ une fonction de modèle, donc je suis un peu perplexe quant à la raison pour laquelle F# ne pas le faire.
    F# déduit d'être aussi générique que possible, par exemple, "pour tous les types de X qui soutiennent la comparaison". inline fonctionne comme un C++ template, qui se spécialise à int basé sur le site d'appel.
    Les modèles C++ se comportent essentiellement comme F#'s inline. La raison pour laquelle le comportement par défaut est différent, c'est parce qu'il s'appuie sur .Net génériques qui sont gérées par le moteur d'exécution (et, sans doute, ne sont pas très bon pour l'écriture générique code numérique). En utilisant le C++ comportement en F#, cependant, conduire à l'augmentation du code, car F# utilise les médicaments génériques beaucoup plus.
    C++ modèle sémantique peut conduire à l'augmentation du code, même en C++, et le manque de moyen pratique pour passer à l'aide d'un mécanisme pour éviter qu'est un souci à la fois. Cependant, la crainte de l'augmentation du code est normalement irrationnel - de façon générale, les modèles C++ fonctionne bien.
    Il est aussi généralement facile de les éviter par la refactorisation tous les code qui n'utilise pas de type de charge, de sorte que le code n'est pas dupliqué pour les différentes instanciations.

    OriginalL'auteur Tomas Petricek