Programación funcional: ¿la inmutabilidad es cara? [cerrado]

La pregunta tiene dos partes. El primero es conceptual. El siguiente analiza la misma pregunta de forma más concreta en Scala.

1. ¿Usar solo 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 computacionalmente en la práctica? Esto se debe al hecho de que la inmutabilidad es un principio básico de los lenguajes puramente funcionales. ¿Hay otros factores que influyan en esto?
2. Tomemos un ejemplo más concreto. La ordenación rápida generalmente se enseña e implementa mediante operaciones mutables en una estructura de datos en memoria. ¿Cómo se implementa tal cosa de una manera funcional PURA con una sobrecarga computacional y de almacenamiento comparable a la versión mutable? Específicamente en Scala. He incluido algunos puntos de referencia crudos a continuación.

Más detalles:

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

Algunos de los principios básicos de la programación funcional pura:

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

Aunque las JVM modernas son extremadamente eficientes con la creación de objetos y la recolección de basura es muy económica para los objetos de corta duración, probablemente sea mejor minimizar la creación de objetos, ¿verdad? Al menos en una aplicación de un solo subproceso donde la concurrencia y el bloqueo no son un problema. Dado que Scala es un paradigma híbrido, se puede optar por escribir código imperativo con objetos mutables si es necesario. Pero, como alguien que ha pasado muchos años tratando de 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 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 elegante implementación de Scala de la misma.

Aquí está mi intento de comparar las implementaciones. No he realizado perfiles detallados. Pero, supongo que la versión de Scala es más lenta porque la cantidad de objetos asignados es lineal (uno por llamada de recursión). ¿Existe alguna posibilidad de que las optimizaciones de llamadas finales entren en juego? Si estoy en lo cierto, Scala admite optimizaciones de llamadas de cola 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 para cinco ejecuciones consecutivas

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

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

• La ordenación rápida "en el lugar" no está realmente en el lugar (y la ordenación rápida no está, por definición, en el 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.

• La implementación de una variante funcional de quicksort que opera en matrices frustra el propósito. Las matrices nunca son inmutables.

• La implementación funcional "adecuada" de quicksort usa listas inmutables. Por supuesto, no está en el lugar, pero tiene el mismo tiempo de ejecución asintótico del peor de los casos ( O ( n ^ 2)) y la complejidad del espacio ( O ( n )) que la versión de procedimiento en el lugar.

  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 espacial, sin embargo, sigue siendo O ( n ).

Hay dos desventajas obvias de una implementación funcional de ordenación rápida. 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)

1. La primera desventaja es la elección del elemento de pivote , que es muy inflexible. La solidez de las implementaciones modernas de ordenación rápida depende en gran medida de una elección inteligente del pivote (compare "Ingeniería de una función de ordenación" de Bentley et al. ). El algoritmo anterior es deficiente en ese sentido, lo que degrada considerablemente el rendimiento promedio.

2. En segundo lugar, este algoritmo utiliza la concatenación de listas (en lugar de la construcción de listas) que es una O ( n operación ). Esto no afecta la complejidad asintótica, pero es un factor medible.

Una tercera desventaja está algo oculta: a diferencia de la variante "en el lugar", esta implementación solicita continuamente memoria del montón para las celdas de contras de la lista y, potencialmente, dispersa la memoria por todas partes. Como resultado, este algoritmo tiene una localidad de caché muy pobre . No sé si los asignadores inteligentes en los lenguajes de programación funcional modernos pueden mitigar esto, pero en las máquinas modernas, los errores de caché se han convertido en un importante asesino del rendimiento.

Cual es la conclusion?A diferencia de otros, no diría que la ordenación rápida es inherentemente imperativa y por eso funciona mal en un entorno de FP. Muy por el contrario, diría que 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 procedimental, e incluso su implementación procedimental emplea la recursividad.

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

Después de leer “Ingeniería de una función de clasificación”, ya no puedo considerar la clasificación rápida como un algoritmo elegante. Implementado de manera eficiente, es un desastre torpe, el trabajo de un ingeniero, no de un artista (¡no para devaluar la ingeniería! Esto tiene su propia estética).

Pero también me gustaría señalar que este punto es particular para la clasificación rápida. No todos los algoritmos son aptos para el mismo tipo de ajustes de bajo nivel. Una gran cantidad de algoritmos y estructuras de datos realmente se pueden expresar sin pérdida de rendimiento en un entorno inmutable.

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

Entonces, para responder a la pregunta original, “¿ es costosa la inmutabilidad? ”- En el caso particular de quicksort, existe un costo que es de hecho el resultado de la inmutabilidad. Pero en general no .

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

• Estás usando primitivas, que pueden tener que estar en caja / sin caja. No está tratando de probar la sobrecarga de envolver objetos primitivos, está tratando de probar la inmutabilidad.
• Ha elegido un algoritmo en el que la operación en el lugar es inusualmente efectiva (y es demostrable). Si desea demostrar que existen algoritmos que son más rápidos cuando se implementan de manera mutante, esta es una buena opción; de lo contrario, es probable que esto sea engañoso.
• Está utilizando la función de sincronización incorrecta. Utilice System.nanoTime.
• El punto de referencia es demasiado corto para que pueda estar seguro de que la compilación JIT no será una parte significativa 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.

Por lo tanto, esta comparación es una excelente ilustración de que debe comprender su lenguaje (y algoritmo) en detalle para poder escribir código de alto rendimiento. Pero no es una buena comparación entre FP y no FP. Si quieres eso, echa un vistazo a Haskell vs. C ++ en el Juego de referencia de lenguajes de computadora . El mensaje para llevar a casa es que la penalización generalmente no es más de un factor de 2 o 3, pero realmente depende. (No hay promesas de que la gente de Haskell haya escrito los algoritmos más rápidos posibles, ¡pero al menos algunos de ellos probablemente lo hayan intentado! Por otra parte, algunas de las bibliotecas de llamadas de Haskell C ...)

Ahora, suponga que desea un punto de referencia más razonable de Quicksort, reconociendo que este es probablemente uno de los peores casos para FP frente a 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 para que solo revise los datos una vez, si es posible, y la comparación con el ordenamiento integrado. 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 tipo es una mala idea, encontramos que hay una penalización de ~ 3x para un ordenamiento rápido inmutable si este último se implementa con algo de cuidado. (También puede escribir un método trisecto que devuelva tres matrices: las menores que, las iguales y las mayores que el pivote. Esto podría acelerar las cosas un poco más).

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

Además, el hecho de que este sea un código Scala idiomático no significa que sea la mejor manera de hacerlo.

La mejor manera de hacer esto sería usar una de las funciones de clasificación integradas de Scala. De esa manera, obtiene la garantía de inmutabilidad y sabe que tiene un algoritmo rápido.

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

La inmutabilidad no es cara. Seguro que puede resultar caro si mide un pequeño subconjunto de las tareas que debe realizar un programa y elige una solución basada en la mutabilidad para arrancar, como la medición de clasificación rápida.

En pocas palabras, no se realiza una ordenación rápida cuando se utilizan 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)
}

Evalúe 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 necesita 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, ni siquiera los algoritmos individuales. El programa se diseñará de otra manera.

Por eso la evaluación comparativa no suele tener sentido. O elige algoritmos que son naturales para un estilo u otro, y ese estilo gana, o compara toda la aplicación, lo que a menudo no es práctico.

Ordenar una matriz es, como, la tarea más imperativa del universo. No es sorprendente que muchas estrategias / implementaciones elegantes 'inmutables' fallen mal en un microbenchmark de 'ordenar una matriz'. Sin embargo, esto no implica que la inmutabilidad sea cara "en general". Hay muchas tareas en las que las implementaciones inmutables se realizarán de manera comparable a las mutables, pero la clasificación de matrices a menudo no es una de ellas.

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

El costo de la inmutabilidad en Scala

Aquí hay una versión que es casi tan rápida que 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 ordena en su lugar usando la versión de Java y devuelve la copia. Scala no le obliga a utilizar una estructura inmutable internamente.

Entonces, el beneficio de Scala es que puede aprovechar la mutabilidad y la inmutabilidad como mejor le parezca. La desventaja es que si lo hace mal, realmente no obtiene los beneficios de la inmutabilidad.

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

Habiendo dicho eso ... ¿Array.concat? Por lo menos, estás mostrando cómo un tipo de colección optimizado para programación imperativa es particularmente lento cuando intentas usarlo en un algoritmo funcional; ¡Casi cualquier otra opción sería más rápida!

Otro punto muy importante a considerar, quizás el problema más importante al comparar los dos enfoques es: "¿qué tan bien se escala esto a varios nodos / núcleos?"

Lo más probable es que, si está buscando una clasificación rápida inmutable, lo esté haciendo porque en realidad desea una clasificació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 la función vuelva a repetirse, 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 para mí si pudiera ejecutar el código Scala en ella, y esto es en un sistema de escritorio simple dos años por detrás de la generación actual.

¿Cómo se compararía eso con el enfoque imperativo de un solo subproceso, me pregunto ...

Quizás la pregunta más importante sea, por 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, ¿la mutabilidad es costosa?"

Se ha dicho que la programación orientada a objetos 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 sin saberlo. De hecho, las bibliotecas de colecciones usan mucho código imperativo, pero eso no significa que no debamos usarlas. Como han dicho otros, usado con cuidado, realmente obtienes lo mejor de ambos mundos aquí.