Why is there a space leak here?

[Mark Tullsen]

Tom,

I noticed this post after I had just posted my own response.

You have to realize that Alastair Reid is one of the truly
great Haskell programmers on planet earth.  I'm serious.  
So, when he says "incredibly subtle space leak" I wouldn't 
expect the solution to be simple.  As far as I can tell, your 
argument would also apply to foo2, which doesn't have a space leak.

I'd be happy to be proven wrong, but I think this space leak
really /is/ subtle and in order to see the problem seems to
require some /tedious/ hand-reductions, taking into account both 
the sharing and the strictness properties.  See my recent posting
for a very brute-force "analysis".

- Mark

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