
On 2007-10-04, Ronald Guida
I need some help with space and time leaks.
I know of two types of space leak. The first type of leak occurs when a function uses unnecessary stack or heap space.
GHCi> sum [1..10^6] *** Exception: stack overflow
Apparently, the default definition for "sum" has a space leak. I can define my own sum in terms of strict foldl ...
sum' xs = foldl' (+) 0 xs
... and it doesn't overflow the stack.
GHCi> sum' [1..10^6] 500000500000 (0.27 secs, 112403416 bytes)
GHCi> sum' [1..10^7] 50000005000000 (2.73 secs, 1161223384 bytes)
GHCi> sum' [1..10^8] 5000000050000000 (27.83 secs, 11645261144 bytes)
I think there's still a space leak; I don't understand why GHCi using 10^8, 10^9, 10^10 bytes of memory for these calculations.
This isn't a space leak. The memory reported is the total amount of allocation done, not the most used at a given time. A C program that did "x = malloc(20); free(x); x = malloc(20); free(x);" would be reporting 40. The run-time system is essentially constructing all of these Integers (and functions returning them) at one point or another, and these need to be represented. Compare with "last" on these structures: Prelude> last [1..10^6] 1000000 (0.06 secs, 40895096 bytes) Prelude> last [1..10^7] 10000000 (0.50 secs, 402118492 bytes) Prelude> last [1..10^8] 100000000 (4.74 secs, 4016449660 bytes) -- Aaron Denney -><-