haskell - ¿Cuánta memoria usa un thunk?

lazy-evaluation

Question

Digamos que tengo un gran número (millones / billones +) de estas simples estructuras de datos Foo :

data Foo = Foo
    { a :: {-# UNPACK #-}!Int
    , b :: Int
    }

Con tantos de estos flotando, se hace necesario pensar cuánta memoria consumen.

En una máquina de 64 bits, cada Int es de 8 bytes, por lo que solo toma 8 bytes (porque es estricta y no está empaquetada). ¿Pero cuánta memoria ocupará b ? Me imagino que esto cambiaría dependiendo de si el thunk está evaluado o no, ¿verdad?

Me imagino que en el caso general esto es imposible de decir, porque b podría depender de cualquier cantidad de posiciones de memoria que solo permanecen en la memoria en caso de que b necesite ser evaluada. Pero, ¿y si b solo dependiera (una operación muy cara) a ? Entonces, ¿hay una forma determinista de decir cuánta memoria se usará?

Answer 1

Además de la respuesta del usuario239558, y en respuesta a su comentario allí, me gustaría señalar algunas herramientas que le permiten inspeccionar la representación del montón de su valor, encontrar respuestas a preguntas como esta y ver el efecto de las optimizaciones y diferentes formas de compilar.

ghc-datasize

te dice el tamaño de un cierre. Aquí puede ver que (en una máquina de 64 bits) en forma evaluada y después de la recolección de basura, Foo 1 2 requiere 24 bytes por sí solo y, incluidas las dependencias, 40 bytes en total:

Prelude GHC.DataSize Test> let x = Foo 1 2 Prelude GHC.DataSize Test> x Foo {a = 1, b = 2} Prelude GHC.DataSize Test> System.Mem.performGC Prelude GHC.DataSize Test> closureSize x 24 Prelude GHC.DataSize Test> recursiveSize x 40

Para reproducir esto, debe cargar la definición de datos en forma compilada con -O ; de lo contrario, el pragma {-# UNPACK #-} no tiene efecto.

Ahora vamos a crear un procesador y veremos que el tamaño aumenta considerablemente:

Prelude GHC.DataSize Test> let thunk = 2 + 3::Int Prelude GHC.DataSize Test> let x = Foo 1 thunk Prelude GHC.DataSize Test> x `seq` return () Prelude GHC.DataSize Test> System.Mem.performGC Prelude GHC.DataSize Test> closureSize x 24 Prelude GHC.DataSize Test> recursiveSize x 400

Ahora esto es bastante excesivo. La razón es que este cálculo incluye referencias a cierres estáticos, diccionarios de clase de Num y similares, y generalmente el bytecode de GHCi no está muy optimizado. Así que vamos a poner eso en un programa Haskell apropiado. Corriendo

main = do
    l <- getArgs
    let n = length l
    n `seq` return ()
    let thunk = trace "I am evaluated" $ n + n
    let x = Foo 1 thunk
    a x `seq` return ()
    performGC
    s1 <- closureSize x
    s2 <- closureSize thunk
    r <- recursiveSize x
    print (s1, s2, r)

da (24, 24, 48) , por lo que ahora el valor de Foo se compone de Foo y un thunk. ¿Por qué solo el thunk, no debería haber una referencia para n agregar otros 16 bytes? Para responder a esto, necesitamos una mejor herramienta:

ghc-heap-view

Esta biblioteca (por mí) puede investigar el montón y decirle exactamente cómo se representan sus datos allí. Entonces, agregue esta línea al archivo de arriba:

buildHeapTree 1000 (asBox x) >>= putStrLn . ppHeapTree

obtenemos (cuando pasamos cinco parámetros al programa) el resultado Foo (_thunk 5) 1 . Tenga en cuenta que el orden de los argumentos se intercambia en el montón, porque los punteros siempre vienen antes que los datos. La llanura 5 indica que el cierre del thunk almacena su argumento unboxed.

Como último ejercicio, verificamos esto haciendo que el thunk sea perezoso en n : Ahora

main = do
    l <- getArgs
    let n = length l
    n `seq` return ()
    let thunk = trace "I am evaluated" $ n
    let x = Foo 1 thunk
    a x `seq` return ()
    performGC
    s1 <- closureSize x
    s2 <- closureSize thunk
    s3 <- closureSize n
    r <- recursiveSize x
    buildHeapTree 1000 (asBox x) >>= putStrLn . ppHeapTree
    print (s1, s2, s3, r)

proporciona una representación de montón de Foo (_thunk (I# 4)) 1 con un cierre separado para n (como lo indica la presencia del constructor I# ) y muestra los tamaños esperados para los valores y su total, (24,24,16,64) .

Ah, y si este sigue siendo un nivel demasiado alto, getClosureRaw te da los bytes brutos.

Answer 2

Si se evalúa b , será un puntero a un objeto Int . El puntero es de 8 bytes, y el objeto Int consta de un encabezado que tiene 8 bytes, y el Int# que es de 8 bytes.

Entonces, en ese caso, el uso de memoria es el objeto Foo (encabezado 8, 8 Int , puntero 8) + Int caja (8 encabezado, 8 Int# ).

Cuando b está evaluado, el puntero de 8 bytes en Foo apuntará a un objeto Thunk . El objeto Thunk representa una expresión no evaluada. Al igual que el objeto Int , este objeto tiene un encabezado de 8 bytes, pero el resto del objeto consta de las variables libres en la expresión no evaluada.

Entonces, en primer lugar, la cantidad de variables libres contenidas en este objeto thunk depende de la expresión que crea el objeto Foo. Las diferentes formas de crear un Foo harán que se creen objetos thunk de tamaños potencialmente diferentes.

Luego, en segundo lugar, las variables libres son todas las variables que se mencionan en la expresión no evaluada que se toman de fuera de la expresión, llamada entorno de un cierre . Son una especie de parámetros de la expresión y deben almacenarse en algún lugar, y así se almacenan en el objeto thunk.

De modo que puede ver los lugares reales donde se invoca el constructor Foo y observar el número de variables libres en el segundo parámetro para estimar el tamaño del procesador.

Un objeto Thunk es realmente lo mismo que un cierre en la mayoría de los otros lenguajes de programación, con una diferencia importante. Cuando se evalúa, puede sobrescribirse con un puntero de redireccionamiento al objeto evaluado. Por lo tanto, es un cierre que memoriza automáticamente su resultado.

Este puntero de redireccionamiento apuntará al objeto Int (16 bytes). Sin embargo, el thunk ahora "muerto" será eliminado en la próxima recolección de basura. Cuando el GC copie a Foo, hará que el punto b de Foo se dirija directamente al objeto Int, haciendo que el procesador no sea referenciado y, por lo tanto, basura.