Warum ist dieser F # -Code so langsam?

127

Eine Levenshtein-Implementierung in C # und F #. Die C # -Version ist zehnmal schneller für zwei Zeichenfolgen mit etwa 1500 Zeichen. C #: 69 ms, F # 867 ms. Warum? Soweit ich das beurteilen kann, machen sie genau das Gleiche? Es spielt keine Rolle, ob es sich um ein Release oder ein Debug-Build handelt.

BEARBEITEN: Wenn jemand hierher kommt, der speziell nach der Implementierung "Entfernung bearbeiten" sucht, ist diese fehlerhaft. Arbeitscode ist hier .

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
quelle
7
Was ist der Leistungsunterschied bei Inline?
Gradbot

Antworten:

202

Das Problem ist, dass die min3Funktion als generische Funktion kompiliert wird, die einen generischen Vergleich verwendet (ich dachte, dies wird nur verwendet IComparable, aber es ist tatsächlich komplizierter - es würde einen strukturellen Vergleich für F # -Typen verwenden und es ist eine ziemlich komplexe Logik).

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

In der C # -Version ist die Funktion nicht generisch (es dauert nur int). Sie können die F # -Version verbessern, indem Sie Typanmerkungen hinzufügen (um dasselbe wie in C # zu erhalten):

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

... oder indem Sie min3as machen inline(in diesem Fall wird es bei Verwendung darauf spezialisiert sein int):

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

Für eine zufällige Zeichenfolge mit streiner Länge von 300 erhalte ich die folgenden Zahlen:

> 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
quelle
1
Warum kompiliert F # min3 nicht als eine Funktion, die int benötigt? Es kennt bereits genug Typinformationen zur Kompilierungszeit, um dies zu tun. So würde es funktionieren, wenn min3 eine C ++ - Vorlagenfunktion wäre, daher bin ich etwas verwirrt darüber, warum F # dies nicht tut.
Sashang
42
F # schließt daraus, dass es so allgemein wie möglich ist, z. B. "für alle Typen X, die den Vergleich unterstützen". inlinefunktioniert wie eine C ++ - Vorlage, die sich auf die Aufrufseite spezialisiert hat int.
Brian
13
C ++ - Vorlagen verhalten sich im Wesentlichen wie F # inline. Der Grund, warum das Standardverhalten anders ist, liegt darin, dass es auf .NET-Generika aufbaut, die von der Laufzeit verarbeitet werden (und möglicherweise nicht so gut zum Schreiben von generischem numerischem Code geeignet sind). Die Verwendung des C ++ - Verhaltens in F # würde jedoch zu einem Aufblähen des Codes führen, da F # viel häufiger Generika verwendet.
Tomas Petricek
4
Die Semantik von C ++ - Vorlagen kann sogar in C ++ zu einem Aufblähen des Codes führen, und das Fehlen einer bequemen Möglichkeit, auf einen Laufzeitmechanismus umzusteigen, um dies zu vermeiden, ist manchmal problematisch. Die Angst vor aufgeblähtem Code ist jedoch normalerweise irrational - im Allgemeinen funktionieren C ++ - Vorlagen gut.
Steve314
@ Steve314: Es ist im Allgemeinen auch leicht zu vermeiden, indem der gesamte Code, der keinen abhängigen Typ verwendet, überarbeitet wird, sodass der Code nicht für verschiedene Instanziierungen dupliziert wird.
ildjarn