¿Por qué este código F # es tan lento?

127

Una implementación de Levenshtein en C # y F #. La versión C # es 10 veces más rápida para dos cadenas de aproximadamente 1500 caracteres. C #: 69 ms, F # 867 ms. ¿Por qué? Por lo que puedo decir, ¿hacen exactamente lo mismo? No importa si es una versión Release o Debug build.

EDITAR: Si alguien viene aquí buscando específicamente la implementación Editar distancia, está roto. El código de trabajo está aquí .

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
fuente
77
¿Cuál es la diferencia de rendimiento en línea?
gradbot

Respuestas:

202

El problema es que la min3función se compila como una función genérica que usa una comparación genérica (pensé que esto solo usa IComparable, pero en realidad es más complicado: usaría una comparación estructural para los tipos de F # y es una lógica bastante compleja).

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

En la versión C #, la función no es genérica (solo se necesita int). Puede mejorar la versión de F # agregando anotaciones de tipo (para obtener lo mismo que en C #):

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

... o haciendo min3como inline(en cuyo caso, se especializará intcuando se use):

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

Para una cadena aleatoria strde longitud 300, obtengo los siguientes números:

> 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
Tomás Petricek
fuente
1
¿Por qué F # no compila min3 como una función que toma int? Ya conoce suficiente información de tipo en tiempo de compilación para hacer esto. Así es como funcionaría si min3 fuera una función de plantilla de C ++, por lo que estoy un poco desconcertado sobre por qué F # no hace esto.
sashang
42
F # infiere que sea lo más genérico posible, por ejemplo, "para todos los tipos X que admiten la comparación". inlinefunciona como una plantilla de C ++, que se especializaría en intfunción del sitio de la llamada.
Brian
13
Las plantillas de C ++ se comportan esencialmente como F # 's inline. La razón por la cual el comportamiento predeterminado es diferente es porque se basa en genéricos .Net que son manejados por el tiempo de ejecución (y, posiblemente, no son tan buenos para escribir código numérico genérico). Sin embargo, el uso del comportamiento de C ++ en F # llevaría a una acumulación de código, porque F # usa genéricos mucho más.
Tomás Petricek
44
La semántica de la plantilla de C ++ puede conducir a la acumulación de código incluso en C ++, y la falta de una forma conveniente de cambiar a usar un mecanismo de tiempo de ejecución para evitar que sea una molestia a veces. Sin embargo, el miedo a la hinchazón de código suele ser irracional; en general, las plantillas C ++ funcionan bien.
Steve314
@ Steve314: En general, también es fácil de evitar refactorizando todo el código que no usa un tipo dependiente, de modo que el código no se duplique para diferentes instancias.
ildjarn