Sí, en particular GHC realiza análisis rigor, que puede reducir drásticamente el uso de espacio de un programa con la pereza no intencionada de O (n)-O (1).
Por ejemplo, considere este programa trivial:
$ cat LazySum.hs
main = print $ sum [1..100000]
Desde sum
no asume que el operador de suma es estricta, (que podría ser utilizado con una instancia de Num
para los que (+)
es perezoso), causará una gran cantidad de thunks para ser asignados. Sin las optimizaciones habilitadas, el análisis de rigurosidad no se realiza.
$ 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
Sin embargo, si se compila con optimizaciones se activa, el analizador de rigurosidad determinará que ya que estamos utilizando el operador de suma para Integer
, que es conocido por ser estricto, el compilador sabe que es seguro para evaluar la se dispara antes de tiempo, y entonces el programa se ejecuta en un espacio constante.
$ 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
Tenga en cuenta que podemos obtener espacio constante, incluso sin optimizaciones, si añadimos el rigor de nosotros mismos:
$ 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
Rigor tiende a ser un problema más grande que las llamadas de la cola, que aren't really a useful concept in Haskell, debido a la evaluación de Haskell modelo.
¿Qué garantiza el estándar Haskell sobre las llamadas de cola? –
@DanielWagner: Bueno, en realidad no se mencionan directamente, ya que en realidad no se aplica al modelo de evaluación de Haskell. Parece que no puedo encontrar una buena referencia en este momento, pero estoy bastante seguro de que se garantiza que algo como 'foldl '(+) 0 [1..100000]' se ejecute en un espacio constante. – hammar
Eso debería ser 'foldl '(+) 0 [1..n]'. Todo es constante cuando se fija el tamaño de la entrada :) – hammar