Why is there a space leak here?

[S. Alexander Jacobson]

This whole discussion seems strange...
Is laziness an operational or a semantic issue?
Why can't haskell implementations reduce some expressions to save space?
In particular, why can't haskell mark expressions that grow after
evaluation, and reduce them if too much space is being consumed.

For example w/ foldl:

foldl + 0 [1..10000]
foldl (+) ((+) 0 1) [2..10000]
foldl (+) ((+) ((+) 0 1) 2) [3..10000]

Can't the implementation notice that each iteration leads to a
larger closure and, if it is running out of space go ahead an just
evaluate (+) 0 1?

I realize that there is a risk of evaluating _|_ unnecessarily, but if you
are otherwise going to run out of memory, you might as well give it a
shot.

In practice, how often do you expect to see growing expressions that cover
a _|_ that are not actually an error in any case?

Hunting down memory leaks is already so obscure, that you might as well
take a shot at solving the problem automatically...

Alternatively, is there some magical way of warning about leaky
expressions at compile time?  You don't have to ban them, but it would be
nice if the programmer were aware of which parts of the code are likely to
grow...

-Alex-




On Tue, 5 Jun 2001, Tom Moertel wrote:

> Alastair David Reid wrote:
> >
> > Executive summary: David's program has an incredibly subtle space leak
> > in it (or I'm being incredibly dumb).  I encourage the honchos (and
> > would be honchos) to have a look.  Users of other compilers might give
> > it a shot too.
>
> > David Bakin wrote:
> >
> > Why is there a space leak in foo1 but not in foo2?
>
> The reason that foo1 "leaks" space is because the middle of v grows
> faster than its head.  So taking elements from v causes its in-memory
> footprint to grow.  To see why this is the case, evaluate foo1 by hand:
>
> > -- This has a space leak, e.g., when reducing (length (foo1 1000000))
> > foo1 m
> >   = take m v
> >     where
> >       v = 1 : flatten (map triple v)
> >       triple x = [x,x,x]
>
> Focusing on just v for now, and letting f = flatten for notation
> purposes, we have
>
> (1) v = 1 : f (map triple v)
>
> (2)   = { unwrap v }
>         1 : f (map triple (1 : f (map triple v)))
>
> (3)   = { eval map }
>         1 : f (triple 1 : map triple (f (map triple v)))
>
> (4)   = { eval triple }
>         1 : f ([1,1,1] : map triple (f (map triple v)))
>
> (5)   = { eval f (= flatten = foldr (++) []) }
>         1 : 1 : 1 : 1 : f (map triple (f (map triple v))))
>
> In order to expose elements 2-4 of v, we had to evaluate v to the extent
> that the overall expression held in memory *grew*.  Notice how in (1) we
> had a single (f (map triple ...)) expression in the tail of v but in (5)
> there are two such expressions, nested.
>
> Continuing further, if we want to expose the 5th-7th elements of v, we
> have to expand the expression yet even more.   Noticing that the (f (map
> triple v)) subexpression in (5) is identical to the tail of (1), we can
> apply the same expansion that we derived in (1)-(5) to yield
>
> (6)   = { repeat (1)-(5) for f (map triple v) in (5) }
>         1 : 1 : 1 : 1 :
>             f (map triple (1 : 1 : 1 :
>                 f (map triple (
>                     f (map triple v)))))))
>
> (7)   = { eval map }
>         1 : 1 : 1 : 1 :
>             f (triple 1 : map triple (
>                 f (map triple (
>                     f (map triple v))))))))
>
> (8)   = { eval triple }
>         1 : 1 : 1 : 1 :
>             f ([1,1,1] : map triple (
>                 f (map triple (
>                     f (map triple v))))))))
>
> (9)   = { eval f }
>         1 : 1 : 1 : 1 : 1 : 1 : 1 :
>             f (map triple (
>                 f (map triple (
>                     f (map triple v)))))))))
>
> Notice how in (9) we have three nested (f (map triple (...)))
> expressions in the tail of v whereas in (5) we had only two and in (1)
> we had but one?
>
> Now you can see why foo1 has a space "leak":  In order to take the Nth
> element of v, v's definition must be expanded to the point where there
> are 1+(N+1)/3 (f (map triple (...))) subexpressions in the tail of v
> *that will never be reached*.  In other words, v's "middle" grows faster
> than its head, ensuring that take will never consume the tail.  Taking
> elements from the head only makes the middle grow larger.  The more your
> take, the larger it grows.
>
> So the problem isn't Hugs but rather the definition of v, which grows
> faster than it can be consumed.
>
> Cheers,
> Tom
>
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>

___________________________________________________________________
S. Alexander Jacobson                   Shop.Com
1-646-638-2300 voice                    The Easiest Way To Shop (sm)