inmutabilidad - objeto inmutable java

Programación funcional: ¿la inmutabilidad es costosa? (9)

La pregunta está en dos partes. El primero es conceptual. El siguiente analiza la misma pregunta más concretamente en Scala.

¿El uso de estructuras de datos inmutables en un lenguaje de programación hace que la implementación de ciertos algoritmos / lógica sea inherentemente más costosa desde el punto de vista de la computación en la práctica? Esto se basa en el hecho de que la inmutabilidad es un principio básico de los lenguajes puramente funcionales. ¿Hay otros factores que impactan en esto?
Tomemos un ejemplo más concreto. Quicksort generalmente se enseña e implementa usando operaciones mutables en una estructura de datos en memoria. ¿Cómo se implementa esto de una manera funcional PURA con una carga computacional y de almacenamiento comparable a la versión mutable. Específicamente en Scala. He incluido algunas referencias crudas a continuación.

Más detalles:

Vengo de un fondo de programación imperativa (C ++, Java). He estado explorando la programación funcional, específicamente Scala.

Algunos de los principios primarios de la programación funcional pura:

Las funciones son ciudadanos de primera clase.
Las funciones no tienen efectos secundarios y, por lo tanto, los objetos / estructuras de datos son immutable .

Aunque las JVMs modernas son extremadamente eficientes con la creación de objetos y la recolección de basura es muy económica para objetos de vida corta, probablemente sea mejor minimizar la creación de objetos ¿no? Al menos en una aplicación de un solo subproceso donde la simultaneidad y el bloqueo no son un problema. Como Scala es un paradigma híbrido, uno puede elegir escribir un código imperativo con objetos mutables si es necesario. Pero, como alguien que ha pasado muchos años intentando reutilizar objetos y minimizar la asignación. Me gustaría una buena comprensión de la escuela de pensamiento que ni siquiera permitiría eso.

Como un caso específico, me sorprendió un poco este fragmento de código en este tutorial 6 . Tiene una versión Java de Quicksort seguida de una aseada implementación de Scala de la misma.

Aquí está mi intento de comparar las implementaciones. No he hecho perfiles detallados. Pero, supongo que la versión de Scala es más lenta porque el número de objetos asignados es lineal (uno por llamada de recursión). ¿Hay alguna posibilidad de que las optimizaciones de las llamadas finales entren en juego? Si estoy en lo cierto, Scala admite optimizaciones de llamadas finales para llamadas auto recursivas. Entonces, solo debería ayudarlo. Estoy usando Scala 2.8.

Versión de Java

public class QuickSortJ { public static void sort(int[] xs) { sort(xs, 0, xs.length -1 ); } static void sort(int[] xs, int l, int r) { if (r >= l) return; int pivot = xs[l]; int a = l; int b = r; while (a <= b){ while (xs[a] <= pivot) a++; while (xs[b] > pivot) b--; if (a < b) swap(xs, a, b); } sort(xs, l, b); sort(xs, a, r); } static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }

Versión Scala

object QuickSortS { def sort(xs: Array[Int]): Array[Int] = if (xs.length <= 1) xs else { val pivot = xs(xs.length / 2) Array.concat( sort(xs filter (pivot >)), xs filter (pivot ==), sort(xs filter (pivot <))) } }

Código Scala para comparar implementaciones

import java.util.Date import scala.testing.Benchmark class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark { val ints = new Array[Int](100000); override def prefix = name override def setUp = { val ran = new java.util.Random(5); for (i <- 0 to ints.length - 1) ints(i) = ran.nextInt(); } override def run = sortfn(ints) } val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" ) val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " ) benchImmut.main( Array("5")) benchMut.main( Array("5"))

Resultados

Tiempo en milisegundos durante cinco carreras consecutivas

Immutable/Functional/Scala 467 178 184 187 183 Mutable/Imperative/Java 51 14 12 12 12

Dado que hay algunos conceptos erróneos volando por aquí, me gustaría aclarar algunos puntos.

El quicksort "en el lugar" no está realmente en el lugar (y el quicksort no está, por definición, en su lugar). Requiere almacenamiento adicional en forma de espacio de pila para el paso recursivo, que es del orden de O (log n ) en el mejor de los casos, pero O ( n ) en el peor de los casos.
Implementar una variante funcional de quicksort que opera en arrays derrota el propósito. Las matrices nunca son inmutables.
La implementación funcional "adecuada" de quicksort usa listas inmutables. Por supuesto, no está en su lugar, pero tiene el mismo tiempo de ejecución asintótico en el peor de los casos ( O ( n ^ 2)) y la complejidad del espacio ( O ( n )) como la versión in situ de procedimiento.
En promedio, su tiempo de ejecución todavía está a la par con el de la variante in situ ( O ( n log n )). Su complejidad de espacio, sin embargo, sigue siendo O ( n ).

Hay dos desventajas obvias de una implementación funcional de quicksort. A continuación, consideremos esta implementación de referencia en Haskell (No sé Scala ...) de la introducción de Haskell :

qsort [] = [] qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater where lesser = (filter (< x) xs) greater = (filter (>= x) xs)

La primera desventaja es la elección del elemento de pivote , que es muy inflexible. La fuerza de las implementaciones modernas de soluciones rápidas depende en gran medida de una elección inteligente del pivote (compárese con "Ingeniería de una función de clasificación" por Bentley et al. ). El algoritmo anterior es pobre en ese sentido, lo que degrada considerablemente el rendimiento promedio.
En segundo lugar, este algoritmo usa la concatenación de listas (en lugar de la construcción de listas) que es una operación O ( n ). Esto no afecta la complejidad asintótica, pero es un factor mensurable.

Una tercera desventaja está algo oculta: a diferencia de la variante "en el lugar", esta implementación continuamente solicita memoria del montón para las células cons de la lista y potencialmente dispersa la memoria por todo el lugar. Como resultado, este algoritmo tiene una localidad de memoria caché muy pobre . No sé si los asignadores inteligentes en lenguajes de programación funcionales modernos pueden mitigar esto, pero en las máquinas modernas, las fallas en la memoria caché se han convertido en una de las principales causas de muerte.

¿Cuál es la conclusión? A diferencia de otros, no diría que el quicksort es intrínsecamente imperativo y es por eso que funciona mal en un entorno de PF. Muy por el contrario, diría que el quicksort es un ejemplo perfecto de un algoritmo funcional: se traduce sin problemas en un entorno inmutable, su tiempo de ejecución asintótico y la complejidad del espacio están a la par con la implementación de procedimientos, e incluso su implementación de procedimientos emplea la recursión.

Pero este algoritmo todavía funciona peor cuando está restringido a un dominio inmutable. La razón de esto es que el algoritmo tiene la peculiar propiedad de beneficiarse de una gran cantidad de ajustes (a veces de bajo nivel) que solo se pueden realizar de manera eficiente en las matrices. Una descripción ingenua del quicksort omite todas estas complejidades (tanto en la variante funcional como en la de procedimiento).

Después de leer "Dirigir una función de ordenación", ya no puedo considerar el quicksort como un algoritmo elegante. Implementado de manera eficiente, es un desastre torpe, una obra de un ingeniero, no de un artista (¡no devaluar la ingeniería! Esto tiene su propia estética).

Pero también me gustaría señalar que este punto es particular de quicksort. No todos los algoritmos son susceptibles al mismo tipo de ajustes de bajo nivel. Muchos algoritmos y estructuras de datos realmente se pueden expresar sin pérdida de rendimiento en un entorno inmutable.

Y la inmutabilidad incluso puede disminuir los costos de rendimiento al eliminar la necesidad de copias costosas o sincronizaciones entre hilos.

Entonces, para responder la pregunta original, " ¿la inmutabilidad es cara? "- En el caso particular de quicksort, hay un costo que es de hecho el resultado de la inmutabilidad. Pero en general, no .

El costo de la inmutabilidad en Scala

Aquí hay una versión que es casi tan rápida como la de Java. ;)

object QuickSortS { def sort(xs: Array[Int]): Array[Int] = { val res = new Array[Int](xs.size) xs.copyToArray(res) (new QuickSortJ).sort(res) res } }

Esta versión hace una copia de la matriz, la clasifica utilizando la versión de Java y devuelve la copia. Scala no te obliga a usar una estructura inmutable internamente.

Entonces, el beneficio de Scala es que puede aprovechar la mutabilidad e inmutabilidad como mejor le parezca. La desventaja es que si lo haces mal no obtendrás los beneficios de la inmutabilidad.

Hay un montón de cosas mal con esto como un punto de referencia de la programación funcional. Los puntos destacados incluyen:

Está utilizando primitivas, que pueden tener que estar en caja / sin caja. No estás tratando de probar la sobrecarga de envolver objetos primitivos, estás tratando de probar la inmutabilidad.
Has elegido un algoritmo en el que la operación in situ es inusualmente efectiva (y probablemente). Si desea demostrar que existen algoritmos que son más rápidos cuando se implementan de forma mutable, entonces esta es una buena opción; de lo contrario, es probable que esto sea engañoso.
Estás utilizando la función de sincronización incorrecta. Use System.nanoTime .
El punto de referencia es demasiado corto para que pueda estar seguro de que la compilación de JIT no será una parte importante del tiempo medido.
La matriz no se divide de manera eficiente.
Las matrices son mutables, por lo que usarlas con FP es una comparación extraña de todos modos.

Entonces, esta comparación es una gran ilustración de que debe entender su lenguaje (y algoritmo) en detalle para escribir código de alto rendimiento. Pero no es una muy buena comparación de FP vs. no FP. Si quieres eso, echa un vistazo a Haskell vs. C ++ en Computer Computer Benchmark Game . El mensaje para llevar a casa es que la penalización no es más que un factor de 2 o 3, pero realmente depende. (No hay promesas de que los Haskell hayan escrito los algoritmos más rápidos posibles, pero al menos algunos de ellos probablemente lo hayan intentado. Por otra parte, algunas de las Haskell llaman a las bibliotecas C ...)

Ahora, supongamos que quiere un punto de referencia más razonable de Quicksort, reconociendo que este es probablemente uno de los peores casos para FP vs. algoritmos mutables e ignorando el problema de la estructura de datos (es decir, pretendiendo que podemos tener una matriz inmutable):

object QSortExample { // Imperative mutable quicksort def swap(xs: Array[String])(a: Int, b: Int) { val t = xs(a); xs(a) = xs(b); xs(b) = t } def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) { val pivot = xs((l+r)/2) var a = l var b = r while (a <= b) { while (xs(a) < pivot) a += 1 while (xs(b) > pivot) b -= 1 if (a <= b) { swap(xs)(a,b) a += 1 b -= 1 } } if (l<b) muQSort(xs)(l, b) if (b<r) muQSort(xs)(a, r) } // Functional quicksort def fpSort(xs: Array[String]): Array[String] = { if (xs.length <= 1) xs else { val pivot = xs(xs.length/2) val (small,big) = xs.partition(_ < pivot) if (small.length == 0) { val (bigger,same) = big.partition(_ > pivot) same ++ fpSort(bigger) } else fpSort(small) ++ fpSort(big) } } // Utility function to repeat something n times def repeat[A](n: Int, f: => A): A = { if (n <= 1) f else { f; repeat(n-1,f) } } // This runs the benchmark def bench(n: Int, xs: Array[String], silent: Boolean = false) { // Utility to report how long something took def ptime[A](f: => A) = { val t0 = System.nanoTime val ans = f if (!silent) printf("elapsed: %.3f sec/n",(System.nanoTime-t0)*1e-9) ans } if (!silent) print("Scala builtin ") ptime { repeat(n, { val ys = xs.clone ys.sorted }) } if (!silent) print("Mutable ") ptime { repeat(n, { val ys = xs.clone muQSort(ys)() ys }) } if (!silent) print("Immutable ") ptime { repeat(n, { fpSort(xs) }) } } def main(args: Array[String]) { val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar) val unsorted = letters.grouped(5).map(_.mkString).toList.toArray repeat(3,bench(1,unsorted,silent=true)) // Warmup repeat(3,bench(10,unsorted)) // Actual benchmark } }

Tenga en cuenta la modificación del Quicksort funcional, por lo que solo pasa por los datos una vez, si es posible, y la comparación con el ordenamiento incorporado. Cuando lo ejecutamos obtenemos algo como:

Scala builtin elapsed: 0.349 sec Mutable elapsed: 0.445 sec Immutable elapsed: 1.373 sec Scala builtin elapsed: 0.343 sec Mutable elapsed: 0.441 sec Immutable elapsed: 1.374 sec Scala builtin elapsed: 0.343 sec Mutable elapsed: 0.442 sec Immutable elapsed: 1.383 sec

Entonces, además de aprender que intentar escribir su propio género es una mala idea, encontramos que hay una penalización de ~ 3x para un quicksort inmutable si este último se implementa con cuidado. (También podría escribir un método trisect que devuelva tres matrices: las menores, iguales y mayores que el pivote. Esto puede acelerar un poco más las cosas).

La inmutabilidad no es costosa. Sin duda, puede ser costoso si mide un pequeño subconjunto de las tareas que tiene que hacer un programa, y elige una solución basada en la mutabilidad para arrancar, como la medición de la oferta rápida.

Para decirlo de manera simple, no se usa la ordenación rápida cuando se usan lenguajes puramente funcionales.

Consideremos esto desde otro ángulo. Consideremos estas dos funciones:

// Version using mutable data structures def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = { def posIndex(i: Int): Int = { if (i < arr.length) { if (p(arr(i))) i else posIndex(i + 1) } else { -1 } } var index = posIndex(0) if (index < 0) Array.empty else { var result = new Array[T](arr.length - index) Array.copy(arr, index, result, 0, arr.length - index) result } } // Immutable data structure: def tailFrom[T](list: List[T], p: T => Boolean): List[T] = { def recurse(sublist: List[T]): List[T] = { if (sublist.isEmpty) sublist else if (p(sublist.head)) sublist else recurse(sublist.tail) } recurse(list) }

Compare eso, y encontrará que el código que usa estructuras de datos mutables tiene un rendimiento mucho peor, porque necesita copiar la matriz, mientras que el código inmutable no tiene que preocuparse por eso.

Cuando programa con estructuras de datos inmutables, estructura su código para aprovechar sus puntos fuertes. No es simplemente el tipo de datos, o incluso los algoritmos individuales. El programa será diseñado de una manera diferente.

Por eso el benchmarking generalmente no tiene sentido. O eliges algoritmos que son naturales para un estilo u otro, y ese estilo gana, o comparas la aplicación completa, que a menudo no es práctica.

No creo que la versión de Scala sea recursiva en la cola, ya que estás usando Array.concat .

Además, solo porque este es un código de Scala idiomático, esto no significa que sea la mejor manera de hacerlo.

La mejor manera de hacerlo sería usar una de las funciones de clasificación integradas de Scala. De esta forma obtienes la garantía de inmutabilidad y sabes que tienes un algoritmo rápido.

Consulte Pregunta de desbordamiento de pila ¿ Cómo ordeno una matriz en Scala? para un ejemplo.

Ordenar una matriz es, como, la tarea más imprescindible en el universo. No es de extrañar que muchas estrategias / implementaciones elegantes e inmutables fracasen en una microbanda de ''ordenar una matriz''. Sin embargo, esto no implica que la inmutabilidad sea costosa "en general". Hay muchas tareas en las que las implementaciones inmutables tendrán un rendimiento comparable al de las mutables, pero la ordenación de arreglos a menudo no es una de ellas.

Se ha dicho que la programación OO utiliza la abstracción para ocultar la complejidad, y la programación funcional utiliza la inmutabilidad para eliminar la complejidad. En el mundo híbrido de Scala, podemos usar OO para ocultar el código imperativo, dejando el código de la aplicación más acertado. De hecho, las bibliotecas de colecciones utilizan un montón de código imperativo, pero eso no significa que no debemos usarlas. Como otros han dicho, usado con cuidado, realmente obtienes lo mejor de ambos mundos aquí.

Se sabe que QuickSort es más rápido cuando se realiza en el lugar, por lo que esta no es una comparación justa.

Habiendo dicho eso ... Array.concat? Si nada más, está mostrando cómo un tipo de colección optimizado para la programación imperativa es particularmente lento cuando intenta usarlo en un algoritmo funcional; casi cualquier otra opción sería más rápido!

Otro punto muy importante a considerar, tal vez el problema más importante cuando se comparan los dos enfoques es: "¿Qué tan bien se escala esto a múltiples nodos / núcleos?"

Lo más probable es que, si está buscando una vía rápida inmutable, lo haga porque realmente desea una conexión rápida paralela. Wikipedia tiene algunas citas sobre este tema: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

La versión scala puede simplemente bifurcarse antes de que se repita la función, lo que le permite ordenar muy rápidamente una lista que contiene miles de millones de entradas si tiene suficientes núcleos disponibles.

En este momento, la GPU en mi sistema tiene 128 núcleos disponibles si solo pudiera ejecutar el código Scala en él, y esto está en un sistema de escritorio simple dos años atrás de la generación actual.

¿Cómo se compara eso con el enfoque imperativo de subproceso único? Me pregunto ...

Quizás la pregunta más importante es por lo tanto:

"Dado que los núcleos individuales no van a ser más rápidos, y la sincronización / bloqueo presenta un verdadero desafío para la paralelización, ¿es costosa la mutabilidad?"

Si simplemente está reescribiendo sus algoritmos imperativos y estructuras de datos en un lenguaje funcional, de hecho será costoso e inútil. Para hacer que las cosas brillen, debe usar las funciones disponibles solo en la programación funcional: persistencia de estructuras de datos, evaluaciones diferidas, etc.