Pourquoi ce code F # est-il si lent?

127

Une implémentation Levenshtein en C # et F #. La version C # est 10 fois plus rapide pour deux chaînes d'environ 1500 caractères. C #: 69 ms, F # 867 ms. Pourquoi? Autant que je sache, ils font exactement la même chose? Peu importe qu'il s'agisse d'une version Release ou Debug.

EDIT: Si quelqu'un vient ici pour rechercher spécifiquement l'implémentation Edit Distance, elle est cassée. Le 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]
Robert Jeppesen
la source
7
Quelle est la différence de performance en utilisant Inline?
gradbot

Réponses:

202

Le problème est que la min3fonction est compilée comme une fonction générique qui utilise une comparaison générique (je pensais que cela utilise juste IComparable, mais c'est en fait plus compliqué - cela utiliserait une comparaison structurelle pour les types F # et c'est une logique assez 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 (elle prend juste int). Vous pouvez améliorer la version F # 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 min3comme inline(dans ce cas, il sera spécialisé intlors de son utilisation):

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

Pour une chaîne aléatoire strde longueur 300, j'obtiens les nombres 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
Tomas Petricek
la source
1
Pourquoi F # ne compile-t-il pas min3 comme une fonction qui prend int? Il connaît déjà suffisamment d'informations de type au moment de la compilation pour ce faire. C'est ainsi que cela fonctionnerait si min3 était une fonction de modèle C ++, donc je suis un peu perplexe quant à la raison pour laquelle F # ne fait pas cela.
sashang
42
F # en déduit qu'il est aussi générique que possible, par exemple "pour tous les types X prenant en charge la comparaison". inlinefonctionne comme un modèle C ++, qui se spécialiserait en intfonction du site d'appel.
Brian
13
Les modèles C ++ se comportent essentiellement comme des F # inline. La raison pour laquelle le comportement par défaut est différent est qu'il s'appuie sur des génériques .Net qui sont gérés par le runtime (et, sans doute, ne sont pas si bons pour écrire du code numérique générique). Cependant, l'utilisation du comportement C ++ dans F # entraînerait un gonflement du code, car F # utilise beaucoup plus les génériques.
Tomas Petricek
4
La sémantique des modèles C ++ peut entraîner une surcharge du code même en C ++, et l'absence d'un moyen pratique de passer à l'utilisation d'un mécanisme d'exécution pour éviter cela est parfois un problème. Cependant, la peur du gonflement du code est normalement irrationnelle - généralement, les modèles C ++ fonctionnent bien.
Steve314
@ Steve314: Il est également généralement facile d'éviter en refactorisant tout le code qui n'utilise pas de type dépendant, afin que le code ne soit pas dupliqué pour différentes instanciations.
ildjarn