list - El enlace `len=length xs` y luego el cálculo de` len` hace que GHC consuma mucha RAM

haskell ghci

Question

Encontré algo extraño sobre GHCi y las listas.

Este comando tarda algún tiempo en ejecutarse y simplemente devuelve la respuesta correcta.

ghci> length [1..10^8]
100000000

Sin embargo, vincular esto con una variable y ejecutar hace que GHC consuma aproximadamente 5 GiB de RAM sin liberar hasta que finalice la sesión de GHCi. Escribiendo :quit después de que consume 3 GiB más antes de salir.

ghci> len = length [1..10^8]
ghci> len
-- Consumes 5 GiB
100000000
ghci> :quit
-- Consumes 3 GiB
-- Exits

¿Esto es normal? ¿Cuál es la diferencia entre los comandos?

La versión de GHC es 8.2.2.

Answer 1

Actualización: la optimización realizada por -O0 es un poco diferente de la que entendí por primera vez. Además, agregó una nota sobre la presentación de un nuevo error Trac.

Puedo reproducir esto en GHC 8.2.2. La evaluación directa de la expresión (o el uso de let para enlazarla a una variable y luego evaluarla) se completa rápidamente:

Prelude> length [1..10^8]
10000000 -- pretty fast
Prelude> let len = length [1..10^8]
Prelude> len
10000000 -- pretty fast
Prelude>

Sin embargo, usando la sintaxis let -free:

Prelude> len = length [1..10^8]
Prelude> len
10000000
Prelude>

toma más tiempo y asigna una gran cantidad de memoria que no se libera hasta que finaliza la sesión.

Tenga en cuenta que esto es específico de GHCi y el modo interactivo: en un programa Haskell real y compilado, no habría ningún problema. La compilación de lo siguiente se ejecutará rápidamente y no consumirá el exceso de memoria:

len = length [1..10^8]
main = print len

Para comprender lo que sucede, debe comprender que Haskell es capaz de realizar dos optimizaciones potenciales de este código:

1. Puede crear explícitamente una lista lenta y comenzar a calcular su longitud, pero determinar que una vez que se haya contado el comienzo de la lista, esos elementos no serán necesarios nuevamente, lo que permitirá que se recojan de inmediato.
2. Puede determinar que no es necesario crear una lista y, a través de un proceso conocido como "fusión de lista", cree un código compilado que cuente directamente desde 1 hasta 10 ^ 8 sin intentar colocar esos números en ningún tipo de estructura de datos.

Cuando este código se compila con optimizaciones ( -O1 o -O2 ), GHC realizará la optimización # 2. La versión compilada se ejecutará rápidamente en una pequeña cantidad de memoria constante (un par de megabytes residentes para el tiempo de ejecución). Si ejecuta esto con:

$ time ./Length +RTS -s

para recopilar estadísticas, encontrará que GHC todavía está asignando aproximadamente 1.6 gigabytes de almacenamiento dinámico, pero esto en realidad es para almacenar los valores de los Integer individuales a medida que se incrementan. (Dado que los valores en Haskell son inmutables, se debe asignar un nuevo Integer para cada incremento). Si obliga a que el tipo sea Int :

len = length [(1::Int)..10^8]

entonces el programa asignará solo unos pocos kilobytes de pila, y podrá ver que realmente no hay una lista asignada.

Resulta que cuando este código se compila sin optimizaciones ( -O0 ), GHC solo realiza la optimización # 1 (como lo señala @Carl), pero logra hacer un muy buen trabajo, tanto que incluso aunque Las estadísticas de GHC muestran una gran cantidad de asignación de almacenamiento dinámico, el programa aún se ejecuta con bastante rapidez con una huella de memoria muy pequeña.

Sin embargo, cuando este código se compila a byte-code en GHCi, no solo se usa la optimización # 1, sino que GHC no hace un trabajo tan bueno como recolectar la lista. Se genera una enorme lista de varios gigabytes, y el principio es la recolección de basura casi tan rápido como se genera. El uso de la memoria termina siendo bastante grande, pero al menos es relativamente constante.

Puedes ver esto activando las estadísticas de tiempo / memoria:

> :set +s
> length [1..10^8]
100000000
(1.54 secs, 7,200,156,128 bytes)
>

Esto significa que este código realmente asigna una lista de 7.2 gigabytes; afortunadamente, puede desecharse casi tan rápido como se genera, por lo que la memoria en uso por el proceso GHCi después de este cálculo todavía será razonablemente modesta.

Verás que:

> let len = length [1..10^8]
> len

y:

> len = length [1..10^8]
> len

mastique exactamente la misma cantidad de memoria (aproximadamente 7.2 gigas).

La diferencia es que, por alguna razón, la versión para let permite que la lista se recoja como se cuenta, y la versión sin let no lo hace.

Al final, esto es casi seguro que es un error de GHCi. Puede estar relacionado con uno de los errores de fuga de espacio existentes que se han reportado (por ejemplo, Trac #12848 o #14336 ), o tal vez sea uno nuevo. Decidí archivarlo como #14789 , así que tal vez alguien lo eche un vistazo.