¿Por qué el indicador de rigor hace que el uso de la memoria aumente?

Question

Los dos programas siguientes se diferencian sólo por la bandera rigurosidad en la variable st

testStrictL.hs $ gato

module Main (main) where 

import qualified Data.Vector as V 
import qualified Data.Vector.Generic as GV 
import qualified Data.Vector.Mutable as MV 

len = 5000000 

testL = do 
    mv <- MV.new len 
    let go i = do 
      if i >= len then return() else 
      do let st = show (i+10000000) -- no strictness flag 
       MV.write mv i st 
       go (i+1) 
    go 0 
    v <- GV.unsafeFreeze mv :: IO (V.Vector String) 
    return v 

main = 
    do 
    v <- testL 
    print (V.length v) 
    mapM_ print $ V.toList $ V.slice 4000000 5 v 

testStrictS.hs $ gato

module Main (main) where 

import qualified Data.Vector as V 
import qualified Data.Vector.Generic as GV 
import qualified Data.Vector.Mutable as MV 

len = 5000000 

testS = do 
    mv <- MV.new len 
    let go i = do 
      if i >= len then return() else 
      do let !st = show (i+10000000) -- this has the strictness flag 
       MV.write mv i st 
       go (i+1) 
    go 0 
    v <- GV.unsafeFreeze mv :: IO (V.Vector String) 
    return v 

main = 
    do 
    v <- testS 
    print (V.length v) 
    mapM_ print $ V.toList $ V.slice 4000000 5 v 

Compilación y ejecución de estos programas en dos Ubuntu 10.10 con ghc 7.03 Obtengo los siguientes resultados

 
$ ghc --make testStrictL.hs -O3 -rtsopts 
[2 of 2] Compiling Main    (testStrictL.hs, testStrictL.o) 
Linking testStrictL ... 
$ ghc --make testStrictS.hs -O3 -rtsopts 
[2 of 2] Compiling Main    (testStrictS.hs, testStrictS.o) 
Linking testStrictS ... 
$ ./testStrictS +RTS -sstderr 
./testStrictS +RTS -sstderr 
5000000 
"14000000" 
"14000001" 
"14000002" 
"14000003" 
"14000004" 
    824,145,164 bytes allocated in the heap 
    1,531,590,312 bytes copied during GC 
    349,989,148 bytes maximum residency (6 sample(s)) 
     1,464,492 bytes maximum slop 
      656 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 1526 collections,  0 parallel, 5.96s, 6.04s elapsed 
    Generation 1:  6 collections,  0 parallel, 2.79s, 4.36s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.77s ( 2.64s elapsed) 
    GC time 8.76s (10.40s elapsed) 
    EXIT time 0.00s ( 0.13s elapsed) 
    Total time 10.52s (13.04s elapsed) 

    %GC time  83.2% (79.8% elapsed) 

    Alloc rate 466,113,027 bytes per MUT second 

    Productivity 16.8% of total user, 13.6% of total elapsed 

$ ./testStrictL +RTS -sstderr 
./testStrictL +RTS -sstderr 
5000000 
"14000000" 
"14000001" 
"14000002" 
"14000003" 
"14000004" 
     81,091,372 bytes allocated in the heap 
    143,799,376 bytes copied during GC 
     44,653,636 bytes maximum residency (3 sample(s)) 
     1,005,516 bytes maximum slop 
       79 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 112 collections,  0 parallel, 0.54s, 0.59s elapsed 
    Generation 1:  3 collections,  0 parallel, 0.41s, 0.45s elapsed 

    INIT time 0.00s ( 0.03s elapsed) 
    MUT time 0.12s ( 0.18s elapsed) 
    GC time 0.95s ( 1.04s elapsed) 
    EXIT time 0.00s ( 0.06s elapsed) 
    Total time 1.06s ( 1.24s elapsed) 

    %GC time  89.1% (83.3% elapsed) 

    Alloc rate 699,015,343 bytes per MUT second 

    Productivity 10.9% of total user, 9.3% of total elapsed 

¿Podría alguien explicar por qué la bandera de rigor parece causar que el programa use tanta memoria ? Este simple ejemplo surgió de mis intentos de comprender por qué mis programas usan tanta memoria cuando leen archivos grandes de 5 millones de líneas y crean vectores de registros.

Answer 1

El problema aquí es principalmente que está utilizando el String (que es un alias para [Char]) tipo que, debido a su representación como una lista no estricta de solo Char s requiere 5 palabras por caracteres en el montón de memoria (ver también this blog article para algunas comparaciones huella de memoria)

en el caso perezoso, que básicamente almacena un golpe seco sin evaluar que apunta a la (compartido) función de evaluación show . (+10000000) y un número entero que varía, mientras que en el caso estricto de las cuerdas completas compuestas de 8 caracteres parecen estar materializados (por lo general, el patrón de explosión solo forzaría al constructor de lista más externo :, es decir, el primer carácter de unvago, para ser evaluado), que requiere mucho más espacio de pila cuanto más largas sean las cadenas.

Almacenando 5000000 String -tipo de cadenas de longitud 8 por lo tanto requiere 5000000 * 8 * 5 = 200000000 palabras, que en 32 bits corresponden a aproximadamente ~ 763 MiB. Si los dígitos Char se comparten, solo necesita 3/5 de eso, es decir ~ 458 MiB, que parece coincidir con la sobrecarga de memoria observada.

Si reemplaza el String por algo más compacto, como un Data.ByteString.ByteString se dará cuenta de que la sobrecarga de la memoria será aproximadamente una magnitud menor en comparación a cuando se utiliza una llanura String.