Dlaczego ten kod F # jest tak wolny?

128

Implementacja Levenshtein w językach C # i F #. Wersja C # jest 10 razy szybsza dla dwóch ciągów około 1500 znaków. C #: 69 ms, F # 867 ms. Czemu? O ile wiem, robią dokładnie to samo? Nie ma znaczenia, czy jest to wersja Release czy Debug.

EDYCJA: Jeśli ktoś przychodzi tutaj szukając implementacji Edit Distance, to jest zepsuty. Kod roboczy jest tutaj .

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
źródło
7
Jaka jest różnica wydajności przy użyciu inline?
gradbot

Odpowiedzi:

203

Problem polega na tym, że min3funkcja jest kompilowana jako funkcja ogólna, która używa ogólnego porównania (myślałem, że używa ona tylko IComparable, ale w rzeczywistości jest bardziej skomplikowana - użyłaby porównania strukturalnego dla typów F # i jest to dość złożona logika).

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

W wersji C # funkcja nie jest ogólna (po prostu bierze int). Możesz ulepszyć wersję F #, dodając adnotacje typu (aby uzyskać to samo, co w C #):

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

... lub wykonując min3jako inline(w takim przypadku będzie wyspecjalizowany, intgdy zostanie użyty):

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

W przypadku losowego ciągu stro długości 300 otrzymuję następujące liczby:

> 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
źródło
1
Dlaczego F # nie kompiluje min3 jako funkcji, która przyjmuje int? W czasie kompilacji zna już wystarczająco dużo informacji o typie, aby to zrobić. Tak by to działało, gdyby min3 była funkcją szablonu C ++, więc jestem trochę zdziwiony, dlaczego F # tego nie robi.
szarfę
42
F # wnioskuje, że jest tak ogólny, jak to tylko możliwe, np. „Dla wszystkich typów X, które obsługują porównanie”. inlinedziała jak szablon C ++, który specjalizuje się w intoparciu o witrynę wywołań.
Brian
13
Szablony C ++ zachowują się zasadniczo jak F # inline. Powodem, dla którego domyślne zachowanie jest inne, jest to, że opiera się on na typach .Net, które są obsługiwane przez środowisko wykonawcze (i prawdopodobnie nie są tak dobre do pisania ogólnego kodu numerycznego). Użycie zachowania C ++ w języku F # doprowadziłoby jednak do rozdęcia kodu, ponieważ F # używa o wiele więcej typów ogólnych.
Tomas Petricek
4
Semantyka szablonów C ++ może prowadzić do rozdęcia kodu nawet w C ++, a brak wygodnego sposobu przełączania się na używanie mechanizmu wykonawczego, aby tego uniknąć, jest czasami kłopotliwy. Jednak strach przed rozdęciem kodu jest zwykle irracjonalny - generalnie szablony C ++ działają dobrze.
Steve314
@ Steve314: Generalnie łatwo jest tego uniknąć, refaktoryzując cały kod, który nie używa zależnego typu, aby kod nie był duplikowany dla różnych instancji.
ildjarn