performance - Scala: rendimiento de objetos mutables e inmutables-OutOfMemoryError

garbage-collection mutability

Question

Quería comparar las características de rendimiento de immutable.Map y mutable.Map en Scala para una operación similar (es decir, fusionar muchos mapas en uno solo. Consulte esta pregunta ). Tengo lo que parecen ser implementaciones similares para mapas mutables e inmutables (ver más abajo).

Como prueba, generé una Lista que contiene 1,000,000 de Mapa de un solo elemento [Int, Int] y pasé esta lista a las funciones que estaba probando. Con suficiente memoria, los resultados fueron sorprendentes: ~ 1200ms para mutable.Map, ~ 1800ms para immutable.Map, y ~ 750ms para una implementación imperativa utilizando mutable.Map: no estoy seguro de qué es lo que explica la enorme diferencia, pero siéntase libre de comenta sobre eso, también.

Lo que me sorprendió un poco, tal vez porque estoy siendo un poco espeso, es que con la configuración de ejecución predeterminada en IntelliJ 8.1, ambas implementaciones mutables alcanzaron un OutOfMemoryError, pero la colección inmutable no lo hizo. La prueba inmutable se ejecutó hasta su finalización, pero lo hizo muy lentamente: toma aproximadamente 28 segundos. Cuando aumenté el máximo de memoria JVM (a unos 200 MB, sin saber dónde está el umbral), obtuve los resultados anteriores.

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

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

Implementaciones a continuación. (Nota: no afirmo que estas sean las mejores implementaciones posibles. No dude en 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 cuál sea el tipo real de Mapa que está utilizando. Probablemente HashMap . Ahora, las estructuras mutables como esa obtienen un rendimiento al asignar previamente la memoria que espera usar. Se está uniendo a un millón de mapas, por lo que el mapa final será algo grande. Veamos cómo se agregan 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)
} 

Ver el 2 * en la línea de cambio de resize ? El HashMap mutable crece al duplicarse cada vez que se queda sin espacio, mientras que el inmutable es bastante conservador en el uso de la memoria (aunque las claves existentes normalmente ocuparán 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 (los pares 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 evita eso. Desafortunadamente, la proyección se basa en Stream , que no es muy confiable para nuestros propósitos en Scala 2.7.x. Aún así, intente esto en su lugar:

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

Una Stream no calcula un valor hasta que se necesita. El recolector de basura también debe recopilar los elementos no utilizados, siempre y cuando no guarde una referencia a la cabeza del Stream , lo que parece ser el caso en su algoritmo.

EDITAR

Como complemento, una comprensión de rendimiento / rendimiento toma una o más colecciones y devuelve una nueva colección. Con la frecuencia 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 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 usa en los primeros dos algoritmos (menos la palabra clave mutable ):

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

El operador foldLeft , aquí escrito con su /: sinónimo, se invocará en el objeto devuelto por el para-comprensión. Recuerde que a : 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 a foldLeft . El primer generador en esta comprensión es m <- listOfMaps . Sabemos que listOfMaps es una colección de tipo List [X], donde X no es realmente relevante aquí. El resultado de una comprensión en una List es siempre otra List . Los otros generadores no son relevantes.

Entonces, tome esta List , obtenga todas las claves / valores dentro de cada Map que es un componente de esta List , y haga una nueva List con todo eso. Por eso 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 solo del tamaño de cada elemento de listOfMaps , 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 la projection .

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

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

Además, map , flatMap y filter of a Stream devuelven un nuevo Stream , lo que significa que puede encadenarlos todos sin hacer una sola copia de la List que los creó. Dado que las comprensiones con yield utilizan estas mismas funciones, el uso de Stream en el interior evita copias innecesarias de datos.

Ahora, supongamos que escribiste algo como esto:

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

En este caso no estás ganando nada. Después de asignar el 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, tendrá una copia completa de los datos.

Ahora considere la forma original:

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

En este caso, el Stream se utiliza al mismo tiempo que se calcula. Veamos brevemente cómo se 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ío, simplemente devuelva el acumulador. De lo contrario, calcule un nuevo acumulador ( f(z, head) ) y luego páselo y la función a la tail de la Stream .

Sin embargo, una vez que f(z, head) haya ejecutado, no quedará ninguna referencia a la head . O, en otras palabras, nada en el programa apuntará a la head del Stream , y eso significa que el recolector de basura puede recogerlo, liberando así la memoria.

El resultado final es que cada elemento producido por la comprensión de comprensión existirá solo brevemente, mientras que usted lo utiliza para calcular el acumulador. Y así es como se guarda guardando una copia de sus datos completos.

Finalmente, está la pregunta de por qué el tercer algoritmo no se beneficia de él. Bueno, el tercer algoritmo no usa el yield , por lo que no se realiza ninguna copia de ningún tipo de datos. En este caso, el uso de projection solo agrega una capa de indirección