Sì, in particolare GHC esegui analisi severità, che può ridurre drasticamente l'utilizzo dello spazio di un programma con pigrizia volute da O (n) a O (1).
Ad esempio, considerare questo programma banale:
$ cat LazySum.hs
main = print $ sum [1..100000]
Poiché sum
non presume che l'operatore aggiunta è rigida, (potrebbe essere utilizzato con un'istanza Num
per cui (+)
è pigrizia), causerà un numero elevato di thunk da allocare. Senza le ottimizzazioni abilitate, l'analisi della severità non viene eseguita.
$ ghc --make LazySum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main (LazySum.hs, LazySum.o)
Linking LazySum ...
$ ./LazySum +RTS -s
./LazySum +RTS -s
5000050000
22,047,576 bytes allocated in the heap
18,365,440 bytes copied during GC
6,348,584 bytes maximum residency (4 sample(s))
3,133,528 bytes maximum slop
15 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 23 collections, 0 parallel, 0.04s, 0.03s elapsed
Generation 1: 4 collections, 0 parallel, 0.01s, 0.02s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.03s elapsed)
GC time 0.05s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.06s ( 0.07s elapsed)
%GC time 83.3% (58.0% elapsed)
Alloc rate 2,204,757,600 bytes per MUT second
Productivity 16.7% of total user, 13.7% of total elapsed
Tuttavia, se si compila con le ottimizzazioni abilitata, l'analizzatore severità determinerà che, dal momento che stiamo usando l'operatore di aggiunta per Integer
, che è noto per essere rigorosi, il compilatore sa che è sicuro di valutare la thunk in anticipo, quindi il programma viene eseguito in uno spazio costante.
$ ghc --make -O2 LazySum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main (LazySum.hs, LazySum.o)
Linking LazySum ...
$ ./LazySum +RTS -s
./LazySum +RTS -s
5000050000
9,702,512 bytes allocated in the heap
8,112 bytes copied during GC
27,792 bytes maximum residency (1 sample(s))
20,320 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 18 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.01s ( 0.02s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.01s ( 0.02s elapsed)
%GC time 0.0% (2.9% elapsed)
Alloc rate 970,251,200 bytes per MUT second
Productivity 100.0% of total user, 55.0% of total elapsed
Nota che possiamo ottenere lo spazio costante anche senza ottimizzazioni, se aggiungiamo il rigore a noi stessi:
$ cat StrictSum.hs
import Data.List (foldl')
main = print $ foldl' (+) 0 [1..100000]
$ ghc --make StrictSum.hs -rtsopts -fforce-recomp
[1 of 1] Compiling Main (StrictSum.hs, StrictSum.o)
Linking StrictSum ...
$ ./StrictSum +RTS -s
./StrictSum +RTS -s
5000050000
9,702,664 bytes allocated in the heap
8,144 bytes copied during GC
27,808 bytes maximum residency (1 sample(s))
20,304 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 18 collections, 0 parallel, 0.00s, 0.00s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.00s ( 0.01s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.00s ( 0.01s elapsed)
%GC time 0.0% (2.1% elapsed)
Alloc rate 9,702,664,000,000 bytes per MUT second
Productivity 100.0% of total user, 0.0% of total elapsed
Rigore tende ad essere un problema più grande di chiamate di coda, che aren't really a useful concept in Haskell, a causa della valutazione di Haskell modello.
Che cosa garantisce lo standard Haskell sulle chiamate in coda? –
@DanielWagner: Beh, in realtà non vengono citati direttamente, poiché non si applica realmente al modello di valutazione di Haskell. Non riesco a trovare un buon riferimento al momento, ma sono abbastanza sicuro che è garantito che qualcosa come 'foldl '(+) 0 [1..100000]' gira in uno spazio costante. – hammar
Questo dovrebbe essere 'foldl '(+) 0 [1..n]'. Tutto è costante quando la dimensione dell'ingresso è fissa :) – hammar