Scala: Mutable vs. Inmutable Object Performance - OutOfMemoryError

Question

Quería comparar las características de rendimiento de inmutable.Map y mutable.Map en Scala para una operación similar (es decir, combinar muchos mapas en uno solo. Consulte this question). Tengo lo que parecen ser implementaciones similares para mapas mutables e inmutables (ver abajo).

Como prueba, generé una lista que contiene 1,000,000 de un solo ítem Map [Int, Int] y pasé esta lista a las funciones que estaba probando. Con suficiente memoria, los resultados no fueron sorprendentes: ~ 1200ms para mutable.Map, ~ 1800ms para inmutable.Map, y ~ 750ms para una implementación imperativa usando mutable.Mapa - no estoy seguro de qué es lo que explica la gran diferencia, pero no dude en comenta sobre eso, también.

Lo que me sorprendió un poco, quizás porque estoy un poco grueso, es que con la configuración de ejecución predeterminada en IntelliJ 8.1, ambas implementaciones mutables golpean un OutOfMemoryError, pero la colección inmutable no lo hizo. La prueba inmutable sí se completó, pero lo hizo muy lentamente: lleva unos 28 segundos. Cuando aumenté la memoria JVM máxima (a aproximadamente 200 MB, no estoy seguro de dónde está el umbral), obtuve los resultados anteriores.

De todos modos, esto es lo que realmente quiero saber:

¿Por qué las implementaciones mutables quedado sin memoria, pero la implementación inmutable no lo hace? Sospecho que la versión inmutable permite que el recolector de elementos no utilizados se ejecute y libere memoria antes de que las implementaciones mutables lo hagan, y todas esas recolecciones de basura explican la lentitud de la ejecución de poca memoria inmutable, pero me gustaría obtener una descripción más detallada explicación que eso.

Implementaciones abajo. (Nota: Yo no pretendo que estas son las mejores implementaciones posibles Siéntase libre de sugerir mejoras..)

def mergeMaps[A,B](func: (B,B) => B)(listOfMaps: List[Map[A,B]]): Map[A,B] = 
    (Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) { (acc, kv) => 
     acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv) 
    } 

    def mergeMutableMaps[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = 
    (mutable.Map[A,B]() /: (for (m <- listOfMaps; kv <- m) yield kv)) { (acc, kv) => 
     acc + (if (acc.contains(kv._1)) kv._1 -> func(acc(kv._1), kv._2) else kv) 
    } 

    def mergeMutableImperative[A,B](func: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A,B] = { 
    val toReturn = mutable.Map[A,B]() 
    for (m <- listOfMaps; kv <- m) { 
     if (toReturn contains kv._1) { 
     toReturn(kv._1) = func(toReturn(kv._1), kv._2) 
     } else { 
     toReturn(kv._1) = kv._2 
     } 
    } 
    toReturn 
    } 

Answer 1

Bueno, realmente depende de lo que el tipo real del mapa que está utilizando. Probablemente HashMap. Ahora, las estructuras mutables como esa ganan rendimiento al preasignar la memoria que espera usar. Estás uniendo un millón de mapas, por lo que el mapa final será algo grande. Vamos a ver cómo se añaden estas claves/valores:

protected def addEntry(e: Entry) { 
    val h = index(elemHashCode(e.key)) 
    e.next = table(h).asInstanceOf[Entry] 
    table(h) = e 
    tableSize = tableSize + 1 
    if (tableSize > threshold) 
    resize(2 * table.length) 
} 

Véase el 2 * en la línea resize? El mutable HashMap crece duplicándose cada vez que se queda sin espacio, mientras que el inmutable es bastante conservador en el uso de memoria (aunque las claves existentes ocuparán normalmente el doble del espacio cuando se actualicen).

Ahora, en cuanto a otros problemas de rendimiento, está creando una lista de claves y valores en las dos primeras versiones. Eso significa que, antes de unirse a cualquier mapa, ¡ya tiene cada Tuple2 (pares de clave/valor) en la memoria dos veces! Además de la sobrecarga de List, que es pequeña, pero estamos hablando de más de un millón de elementos multiplicados por la sobrecarga.

Es posible que desee utilizar una proyección que lo evite. Lamentablemente, la proyección se basa en Stream, que no es muy confiable para nuestros propósitos en Scala 2.7.x. Aún así, probar este lugar:

for (m <- listOfMaps.projection; kv <- m) yield kv 

Un Stream no calcula un valor hasta que se necesite. El recolector de basura también debe recopilar los elementos no utilizados, siempre y cuando no guardes una referencia al encabezado Stream, que parece ser el caso en tu algoritmo.

EDITAR

Como complemento, una para/rendimiento comprensión toma una o más colecciones y regresar una nueva colección. Siempre que tenga sentido, la colección que regresa es del mismo tipo que la colección original. Entonces, por ejemplo, en el siguiente código, la comprensión forzada crea una nueva lista, que luego se almacena dentro de l2. No es val l2 = que crea la nueva lista, sino la comprensión.

val l = List(1,2,3) 
val l2 = for (e <- l) yield e*2 

Ahora, veamos el código que se utiliza en los dos primeros algoritmos (menos el mutable palabra clave):

(Map[A,B]() /: (for (m <- listOfMaps; kv <-m) yield kv)) 

El operador foldLeft, aquí escrito con su /: sinónimo, se invocarán en el objeto devuelto por la comprensión forzosa. Recuerde que un : al final de un operador invierte el orden del objeto y los parámetros.

Ahora, consideremos qué objeto es este, en el que se llama foldLeft. El primer generador en este for-comprensión es m <- listOfMaps. Sabemos que listOfMaps es una colección de tipo Lista [X], donde X no es realmente relevante aquí. El resultado de una comprensión forzosa en un List es siempre otro List. Los otros generadores no son relevantes.

Por lo tanto, se toma esta List, obtiene todas las claves/valores dentro de cada Map que es un componente de este List, y hacer una nueva List con todo eso. Es por eso que estás duplicando todo lo que tienes.

(de hecho, es incluso peor que eso, porque cada generador crea una nueva colección; las colecciones creadas por el segundo generador son sólo el tamaño de cada elemento de la listOfMaps sin embargo, y se descartan inmediatamente después de su uso)

La siguiente pregunta - en realidad, la primera, pero fue más fácil invertir la respuesta - es cómo ayuda el uso de projection.

Cuando llama al projection en un List, devuelve un objeto nuevo, del tipo Stream (en Scala 2.7.x). Al principio, puede pensar que esto solo empeorará las cosas, porque ahora tendrá tres copias del List, en lugar de una sola. Pero un Stream no está precalculado. Es perezosamente calculado.

Lo que significa esto es que el objeto resultante, la Stream, no es una copia de la List, sino, más bien, una función que se puede utilizar para calcular la Stream cuando sea necesario. Una vez calculado, el resultado se mantendrá para que no sea necesario volver a calcularlo.

Además, map, flatMap y filter de toda una Stream devolver una nueva Stream, lo que significa que todos ellos puede encadenar juntos sin hacer una sola copia del List el que los creó. Dado que for-comprehensions con yield utiliza estas mismas funciones, el uso de Stream dentro de la evita copias innecesarias de datos.

Ahora, supongamos que usted escribió algo como esto:

val kvs = for (m <- listOfMaps.projection; kv <-m) yield kv 
(Map[A,B]() /: kvs) { ... } 

En este caso, no está ganando nada. Después de asignar Stream a kvs, los datos aún no se han copiado. Sin embargo, una vez que se ejecuta la segunda línea, kvs habrá calculado cada uno de sus elementos y, por lo tanto, contendrá una copia completa de los datos.

Consideremos ahora la forma original ::

(Map[A,B]() /: (for (m <- listOfMaps.projection; kv <-m) yield kv)) 

En este caso, el Stream se usa al mismo tiempo que se calcula. Veamos brevemente cómo se define foldLeft para un Stream:

override final def foldLeft[B](z: B)(f: (B, A) => B): B = { 
    if (isEmpty) z 
    else tail.foldLeft(f(z, head))(f) 
} 

Si el Stream está vacía, simplemente devuelva el acumulador. De lo contrario, calcule un nuevo acumulador (f(z, head)) y luego páselo y la función al tail del Stream.

Una vez que se haya ejecutado f(z, head), no habrá ninguna referencia restante al head. O, en otras palabras, nada en ninguna parte del programa apunta al head del Stream, y eso significa que el recolector de basura puede recopilarlo, liberando así la memoria.

El resultado final es que cada elemento producido por la comprensión forzada existirá solo brevemente, mientras que usted lo usa para calcular el acumulador. Y así es como guarda guardando una copia de toda su información.

Finalmente, está la cuestión de por qué el tercer algoritmo no se beneficia de ello. Bueno, el tercer algoritmo no usa yield, por lo que no se está realizando ninguna copia de ningún dato. En este caso, usar projection solo agrega una capa indirecta.