performance - programacion - ¿La programación funcional de Scala es más lenta que la codificación tradicional?

programacion funcional ventajas y desventajas

Question

En uno de mis primeros intentos de crear código funcional, encontré un problema de rendimiento.

Empecé con una tarea común: multiplicar los elementos de dos matrices y resumir los resultados:

var first:Array[Float] ...
var second:Array[Float] ...    
var sum=0f; 
for (ix<-0 until first.length) 
    sum += first(ix) * second(ix);

Así es como reformé el trabajo:

sum = first.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

Cuando comparé los dos enfoques, ¡el segundo método toma 40 veces más tiempo para completarse!

¿Por qué el segundo método toma mucho más tiempo? ¿Cómo puedo reformar el trabajo para que sea eficiente a la velocidad y use un estilo de programación funcional?

Answer 1

Aquí está la solución dbyrnes con matrices (suponiendo que se utilicen matrices) y simplemente iterar sobre el índice:

def multiplyAndSum (l1: Array[Int], l2: Array[Int]) : Int = 
{
    def productSum (idx: Int, sum: Int) : Int = 
        if (idx < l1.length)
            productSum (idx + 1, sum + (l1(idx) * l2(idx))) else 
                sum
    if (l2.length == l1.length) 
        productSum (0, 0) else 
    error ("lengths don''t fit " + l1.length + " != " + l2.length) 
}


val first = (1 to 500).map (_ * 1.1) toArray                                                
val second = (11 to 510).map (_ * 1.2) toArray     
def loopi (n: Int) = (1 to n).foreach (dummy => multiplyAndSum (first, second))
println (timed (loopi (100*1000)))

Eso necesita alrededor de 1/40 del tiempo del enfoque de lista. No tengo 2.8 instalado, por lo que debe probar @tailrec usted mismo. :)

Answer 2

Don Stewart tiene una buena respuesta, pero puede no ser obvio cómo pasar de un ciclo a tres crea un factor de desaceleración de 40. Añadiré a su respuesta que Scala compila códigos de byte JVM, y no solo el compilador de Scala no fusiona los tres bucles en uno, sino que el compilador de Scala casi con certeza está asignando todas las matrices intermedias. Notoriamente, las implementaciones de la JVM no están diseñadas para manejar las tasas de asignación requeridas por los lenguajes funcionales . La asignación es un costo significativo en los programas funcionales, y esa es una de las transformaciones de fusión de bucles que Don Stewart y sus colegas han implementado para Haskell son tan poderosas: eliminan muchas asignaciones. Cuando no tienes esas transformaciones, además de que estás usando un asignador caro como el que se encuentra en una JVM típica, de ahí viene la gran ralentización.

Scala es un gran vehículo para experimentar con el poder expresivo de una mezcla inusual de ideas de lenguaje: clases, mixins, módulos, funciones, etc. Pero es un lenguaje de investigación relativamente joven, y se ejecuta en JVM, por lo que no es razonable esperar un gran rendimiento, excepto en el tipo de código que las JVM son buenas. Si quieres experimentar con la combinación de ideas de lenguaje que ofrece Scala, es un diseño realmente interesante, pero no esperes el mismo rendimiento en código funcional puro que obtendrías con un compilador maduro para un lenguaje funcional, como GHC o MLton .

¿Es la programación funcional scala más lenta que la codificación tradicional?

No necesariamente Cosas que hacer con funciones de primera clase, coincidencia de patrones y currying no necesitan ser especialmente lentos. Pero con Scala, más que con otras implementaciones de otros lenguajes funcionales, realmente hay que tener cuidado con las asignaciones, que pueden ser muy costosas.

Answer 3

Este es un microbenchmark, y depende de cómo el compilador optimice tu código. Tienes 3 bucles compuestos aquí,

cremallera . mapa . doblez

Ahora, estoy bastante seguro de que el compilador de Scala no puede fusionar esos tres bucles en un solo bucle, y el tipo de datos subyacente es estricto, por lo que cada (.) Corresponde a una matriz intermedia que se está creando. La solución imperativa / mutable reutilizaría el búfer cada vez, evitando las copias.

Ahora, una comprensión de lo que significa la composición de esas tres funciones es clave para entender el rendimiento en un lenguaje de programación funcional, y de hecho, en Haskell, esos tres bucles se optimizarán en un solo bucle que reutilizará un búfer subyacente, pero Scala no puede hacer ese.

Sin embargo, hay ventajas en seguir el enfoque del combinador: al distinguir esas tres funciones, será más fácil paralelizar el código (reemplazar el mapa con parMap, etc.). De hecho, dado el tipo de matriz correcto (como una matriz paralela ), un compilador suficientemente inteligente podrá paralelizar automáticamente su código, produciendo más ganancias de rendimiento.

Entonces, en resumen:

• traducciones ingenuas pueden tener copias inesperadas e ineficiencias
• los compiladores inteligentes de FP eliminan esta sobrecarga (pero Scala aún no puede)
• apegarse al enfoque de alto nivel vale la pena si quieres redirigir tu código, por ejemplo, para paralelizarlo

Answer 4

Hice algunas variaciones de esto con Scala 2.8. La versión en bucle es tal como la escribe, pero la versión funcional es ligeramente diferente:

(xs, ys).zipped map (_ * _) reduceLeft(_ + _)

Corrí con Double en lugar de Float, porque actualmente la especialización solo aparece para Double. Luego probé con matrices y vectores como el tipo de operador. Además, probé las variantes en caja que funcionan en java.lang.Double en lugar de los primitivos dobles para medir el efecto del boxeo de tipo primitivo y unboxing. Esto es lo que obtuve (ejecutando Java VM del servidor de la versión 1.6_10, Scala 2.8 RC1, 5 ejecuciones por prueba).

loopArray 461 437 436 437 435 reduceArray 6573 6544 6718 6828 6554 loopVector 5877 5773 5775 5791 5657 reduceVector 5064 4880 4844 4828 4926 loopArrayBoxed 2627 2551 2569 2537 2546 reduceArrayBoxed 4809 4434 4496 4434 4365 loopVectorBoxed 7577 7450 7456 7463 7432 reduceVectorBoxed 5116 4903 5006 4957 5122

Lo primero que hay que notar es que, con diferencia, la mayor diferencia se encuentra entre los bucles primitivos de la matriz y la reducción funcional de la matriz primitiva. Se trata de un factor de 15 en lugar de los 40 que ha visto, lo que refleja mejoras en Scala 2.8 sobre 2.7. Aún así, los bucles primitivos de matriz son los más rápidos de todas las pruebas, mientras que los primitivos se reducen más lentamente. La razón es que las matrices de Java primitivas y las operaciones genéricas simplemente no encajan muy bien. Acceder a los elementos de las matrices primitivas de Java desde funciones genéricas requiere una gran cantidad de boxeo / unboxing y, a veces incluso requiere reflexión. Las versiones futuras de Scala se especializarán en la clase Array y luego deberíamos ver algunas mejoras. Pero ahora eso es lo que es.

Si pasas de matrices a vectores, notas varias cosas. Primero, ¡la versión reducida ahora es más rápida que el ciclo imperativo! Esto se debe a que Vector reduce puede hacer uso de operaciones masivas eficientes. En segundo lugar, la reducción vectorial es más rápida que la reducción de matriz, lo que ilustra la sobrecarga inherente que las matrices de tipos primitivos presentan para funciones genéricas de orden superior.

Si elimina la sobrecarga del boxeo / unboxing al trabajar solo con los valores java.lang.Double encuadrados, la imagen cambia. Ahora reducir las matrices es un poco menos de 2 veces más lento que el bucle, en lugar de las 15 veces anteriores. Esto se aproxima más a la sobrecarga inherente de los tres bucles con estructuras de datos intermedios en lugar del bucle fusionado de la versión imperativa. Looping sobre vectores es ahora, con mucho, la solución más lenta, mientras que la reducción de vectores es un poco más lenta que la reducción de matrices.

Entonces, la respuesta general es: depende. Si tiene bucles estrechos sobre matrices de valores primitivos, nada supera un bucle imperativo. Y no hay problema en escribir los bucles porque no son ni más largos ni menos comprensibles que las versiones funcionales. En todas las demás situaciones, la solución FP parece competitiva.

Answer 5

La biblioteca de colecciones de Scala es completamente genérica, y las operaciones proporcionadas se eligen para la capacidad máxima, no para la velocidad máxima. Entonces, sí, si usa un paradigma funcional con Scala sin prestar atención (especialmente si usa tipos de datos primitivos), su código tardará más tiempo en ejecutarse (en la mayoría de los casos) que si usa un paradigma imperativo / iterativo sin prestar atención .

Dicho esto, puede crear fácilmente operaciones funcionales no genéricas que funcionen rápidamente para su tarea deseada. En el caso de trabajar con pares de carrozas, podríamos hacer lo siguiente:

class FastFloatOps(a: Array[Float]) {
  def fastMapOnto(f: Float => Float) = {
    var i = 0
    while (i < a.length) { a(i) = f(a(i)); i += 1 }
    this
  }
  def fastMapWith(b: Array[Float])(f: (Float,Float) => Float) = {
    val len = a.length min b.length
    val c = new Array[Float](len)
    var i = 0
    while (i < len) { c(i) = f(a(i),b(i)); i += 1 }
    c
  }
  def fastReduce(f: (Float,Float) => Float) = {
    if (a.length==0) Float.NaN
    else {
      var r = a(0)
      var i = 1
      while (i < a.length) { r = f(r,a(i)); i += 1 }
      r
    }
  }
}
implicit def farray2fastfarray(a: Array[Float]) = new FastFloatOps(a)

y luego estas operaciones serán mucho más rápidas. (Más rápido aún si usa Double y 2.8.RC1, porque entonces las funciones (Double,Double)=>Double estarán especializadas, no serán genéricas; si está utilizando algo antes, puede crear su propia abstract class F { def f(a: Float) : Float } y luego llame con la new F { def f(a: Float) = a*a } lugar de (a: Float) => a*a .)

De todos modos, el punto es que no es el estilo funcional lo que hace que la codificación funcional en Scala sea lenta, sino que la biblioteca está diseñada con la máxima potencia / flexibilidad en mente, no la velocidad máxima. Esto es sensato, ya que los requisitos de velocidad de cada persona suelen ser sutilmente diferentes, por lo que es difícil cubrir a todos extraordinariamente bien. Pero si es algo que está haciendo algo más que un poco, puede escribir sus propias cosas donde la penalización de rendimiento para un estilo funcional es extremadamente pequeña.

Answer 6

Las razones principales por las cuales estos dos ejemplos son tan diferentes en velocidad son:

• cuanto más rápido uno no utiliza ningún genérico, por lo que no enfrenta el boxeo / unboxing.
• cuanto más rápido uno no crea colecciones temporales y, por lo tanto, evita copias de memoria adicionales.

Consideremos el más lento por partes. Primero:

first.zip(second)

Eso crea una nueva matriz, una matriz de Tuple2 . Tuple2 todos los elementos de ambas matrices en objetos Tuple2 , y luego copiará una referencia a cada uno de estos objetos en una tercera matriz. Ahora, observe que Tuple2 está parametrizado, por lo que no puede almacenar Float directamente. En su lugar, se crean nuevas instancias de java.lang.Float para cada número, los números se almacenan en ellos, y luego se almacena una referencia para cada uno en el Tuple2 .

map{ case (a,b) => a*b }

Ahora se crea una cuarta matriz. Para calcular los valores de estos elementos, necesita leer la referencia a la tupla de la tercera matriz, leer la referencia al java.lang.Float almacenado en ellos, leer los números, multiplicar, crear un nuevo java.lang.Float para almacenar el resultado, y luego reenviar esta referencia, que será eliminada de nuevo para ser almacenada en la matriz (las matrices no se borran).

Sin embargo, no hemos terminado. Aquí está la siguiente parte:

reduceLeft(_+_)

Ese es relativamente inofensivo, excepto que todavía crea boxeo / unboxing y java.lang.Float en la iteración, ya que reduceLeft recibe una reduceLeft , que está parametrizada.

Scala 2.8 introduce una característica llamada especialización que eliminará muchos de estos boxeo / unboxing. Pero consideremos versiones alternativas más rápidas. Podríamos, por ejemplo, hacer un map y reduceLeft en un solo paso:

sum = first.zip(second).foldLeft(0f) { case (a, (b, c)) => a + b * c }

Podríamos usar view (Scala 2.8) o projection (Scala 2.7) para evitar crear colecciones intermedias por completo:

sum = first.view.zip(second).map{ case (a,b) => a*b }.reduceLeft(_+_)

Este último no ahorra mucho, en realidad, así que creo que la falta de rigor se "pierde" bastante rápido (es decir, uno de estos métodos es estricto incluso en una vista). También hay una forma alternativa de comprimir que no es estricta (es decir, evita algunos resultados intermedios) de manera predeterminada:

sum = (first,second).zipped.map{ case (a,b) => a*b }.reduceLeft(_+_)

Esto da un resultado mucho mejor que el anterior. Mejor que el foldLeft , aunque no por mucho. Desafortunadamente, no podemos combinar zipped con foldLeft porque el primero no es compatible con este último.

El último es el más rápido que pude obtener. Más rápido que eso, solo con especialización. Ahora, Function2 resulta ser especializada, pero para Int , Long y Double . Las otras primitivas quedaron fuera, ya que la especialización aumenta el tamaño del código de forma bastante espectacular para cada primitiva. En mis pruebas, aunque Double está tomando más tiempo. Eso podría ser el resultado de que sea el doble de tamaño, o podría ser algo que estoy haciendo mal.

Entonces, al final, el problema es una combinación de factores, incluida la producción de copias intermedias de elementos, y la forma en que Java (JVM) maneja primitivas y genéricas. Un código similar en Haskell usando supercompilación sería igual a cualquier cosa menos que ensamblador. En JVM, debe conocer las ventajas y desventajas y estar preparado para optimizar el código crítico.

Answer 7

No soy un programador experto de Scala, por lo que probablemente haya un método más eficiente, pero ¿qué tal algo así? Esto puede ser optimizado para llamadas de cola, por lo que el rendimiento debería ser correcto.

def multiply_and_sum(l1:List[Int], l2:List[Int], sum:Int):Int = {
    if (l1 != Nil && l2 != Nil) {
        multiply_and_sum(l1.tail, l2.tail, sum + (l1.head * l2.head))
    }
    else {
        sum
    }
}

val first = Array(1,2,3,4,5)
val second = Array(6,7,8,9,10)
multiply_and_sum(first.toList, second.toList, 0)  //Returns: 130

Answer 8

Para responder la pregunta en el título: las construcciones funcionales simples pueden ser más lentas que imperativas en la JVM.

Pero, si consideramos solo constructos simples, entonces podríamos descartar todos los lenguajes modernos y apegarnos a C o ensamblador. Si mira el tiroteo en el lenguaje de programación, C siempre gana.

Entonces, ¿por qué elegir un idioma moderno? Porque le permite expresar un diseño más limpio. Un diseño más limpio conduce a mejoras en el rendimiento en la operación general de la aplicación. Incluso si algunos métodos de bajo nivel pueden ser más lentos. Uno de mis ejemplos favoritos es el rendimiento de BuildR vs. Maven. BuildR está escrito en Ruby, un lenguaje lento e interpretado. Maven está escrito en Java. Una compilación en BuildR es dos veces más rápida que Maven. Esto se debe principalmente al diseño de BuildR, que es liviano en comparación con el de Maven.

Answer 9

Su solución funcional es lenta porque está generando estructuras de datos temporales innecesarias. La eliminación de estos se conoce como deforestación y se lleva a cabo fácilmente en los lenguajes funcionales más estrictos al convertir sus funciones anónimas en una sola función anónima y usar un único agregador. Por ejemplo, su solución escrita en F # usando zip , map y reduce :

let dot xs ys = Array.zip xs ys |> Array.map (fun (x, y) -> x * y) -> Array.reduce ( * )

puede reescribirse utilizando fold2 para evitar todas las estructuras de datos temporales:

let dot xs ys = Array.fold2 (fun t x y -> t + x * y) 0.0 xs ys

Esto es mucho más rápido y se puede hacer la misma transformación en Scala y en otros lenguajes funcionales estrictos. En F #, también puede definir fold2 como en inline para tener la función de orden superior en línea con su argumento funcional con lo cual recupera el rendimiento óptimo del ciclo imperativo.