[Haskell-cafe] Re: Space and time leaks

[Aaron Denney]

On 2007-10-04, Ronald Guida <ronguida at mindspring.com> wrote:
> 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
-><-