Comportamiento de memoria desconcertante en Haskell

Question

Estoy tratando de comparar el rendimiento de las listas y arreglos de Haskell y me encuentro con un comportamiento extraño. Observé que si creo una matriz y luego la imprimo toma 'x' MB de memoria, pero si convierto la matriz en una lista usando la función 'elems' y luego la imprime, la memoria tarda menos que 'x'. ¿No se supone que la función 'elems' crea una nueva lista de la matriz? ¿No debería tomar más espacio que la función que no crea la lista? Estoy usando los indicadores de optimización -O2 y -fspec-constr. También estoy usando la bandera -p para perfilar las funciones.

Este es el código sin lista intermedia,

fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ fun (read n)) 

Este es el código con la lista intermedia,

fun :: Int -> UArray (Int,Int) Int 
fun n = runST $ do 
     final_soln <- newArray_ ((1,1), (n, (10^n))) :: ST s ((STUArray s) (Int,Int) Int) 
     U.unsafeFreeze final_soln 

main = do 
    [n] <- getArgs 
    {-# SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt" $ show $ elems $ fun (read n)) 

Gracias de antemano

Answer 1

Hay una falta de pereza en el primera variante, y no es tu culpa. Comparar la salida de perfiles (+RTS -hd) de una carrera con el parámetro 6 da la primera pista:

es la salida de perfiles del primer código, mientras que

es el resultado de el segundo código La matriz en sí (ARR_WORDS) ocupa el mismo espacio en ambos. También verá que el primer código produce una lista grande (reconocible por el constructor :) de los constructores Int (que tienen el nombre Int#).

Ahora bien, esto no puede ser el final String como impresa, ya que eso sería Char s entonces (con el constructor C#). Tampoco puede ser la lista de elementos en la matriz, ya que la matriz contiene ceros y el recolector de basura tiene una memoria caché de Int s pequeña (en el rango [-16,16]) que usaría en lugar de asignar (o de hecho en lugar de copiar) un nuevo constructor.

También tenga en cuenta que se necesitan aproximadamente 24 MB para los constructores : y 16 MB para los constructores I#. Sabiendo que el primero requiere 3 palabras y las últimas 2 palabras, y que una palabra en mi máquina tiene 8 bytes de longitud, encontramos que la lista tiene 100000 = 10^6 elementos. Entonces, un candidato muy bueno es el rango del segundo parámetro de índice.

Entonces, ¿dónde está esta matriz? Tracemos su llamada a show:

showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS 
showsIArray p a = 
    showParen (p > 9) $ 
    showString "array " . 
    shows (bounds a) . 
    showChar ' ' . 
    shows (assocs a) 

(Código de Data.Array.Base). Claramente, el culpable debe estar en la llamada assocs, así que aquí está la fuente para que:

assocs :: (IArray a e, Ix i) => a i e -> [(i, e)] 
assocs arr = case bounds arr of 
    (l,u) -> [(i, arr ! i) | i <- range (l,u)] 

Puesto que estamos buscando la lista de índices, la llamada range parece bastante sospechoso.Para eso tenemos que mirar en la fuente de GHC.Arr (que por desgracia eglefino en mal estado):

instance (Ix a, Ix b) => Ix (a, b) where 
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] 

Y ahora hemos encontrado al culpable: Aquí, range (l2,u2) evaluará a la lista [1..1000000] y compartida para cada paso en el primer componente del índice.

Ahora supongo que tendrá curiosidad tratando de poner assocs en lugar de elems en el segundo código, y esperando la fuga de espacio allí. Pero no lo verás La razón es que show no está en línea, pero assocs se inserta, y luego también un montón de otras funciones, incluyendo range evitando de manera efectiva el intercambio. Se puede ver que (un poco) al pasar a -ddump-rule-firings GHC:

$ ghc --make -O2 -fspec-constr -ddump-rule-firings -fforce-recomp code2.hs -prof -fprof-auto 
[1 of 1] Compiling Main    (code2.hs, code2.o) 
Rule fired: SPEC GHC.Arr.$fIx(,) 
Rule fired: unpack 
Rule fired: Class op fail 
Rule fired: unpack 
Rule fired: Class op show 
Rule fired: Class op newArray_ 
Rule fired: unsafeFreeze/STUArray 
Rule fired: Class op >>= 
Rule fired: Class op >>= 
Rule fired: Class op showList 
Rule fired: Class op rangeSize 
Rule fired: Class op rangeSize 
Rule fired: Class op bounds 
Rule fired: Class op bounds 
Rule fired: Class op numElements 
Rule fired: Class op index 
Rule fired: Class op unsafeAt 
Rule fired: Class op range 
Rule fired: fold/build 
Rule fired: SPEC GHC.Real.^ 
Rule fired: unpack-list 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: foldr/app 
Rule fired: unpack-append 
Rule fired: ># 
Rule fired: ># 
Rule fired: x# <=# x# 
Rule fired: x# -# x# 
Rule fired: 0# *# x# 
Rule fired: 0# +# x# 
Linking code2 ...