Why is there a space leak here?

[Mark Tullsen]

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 <davidbak@cablespeed.com> writes:
> 
> > Why is there a space leak in foo1 but not in foo2?  (I.e., in Hugs
> > Nov '99) foo1 eats cells (and eventually runs out) where foo2
> > doesn't.  That is, if I do (length (foo1 1000000)) I eventually run
> > out of cells but (length (foo2 1000000)) runs fine (every GC returns
> > basically the same amount of space).  Something must be wrong in
> > flatten but it follows the pattern of many functions in the prelude
> > (which I'm trying to learn from).  I have been puzzling over this
> > for nearly a full day (getting this reduced version from my own code
> > which wasn't working).  In general, how can I either a) analyze code
> > looking for a space leak or b) experiment (e.g., using Hugs) to find
> > a space leak?  Thanks!  -- Dave
> 

I certainly don't have tons of experience tracking down and fixing 
space leaks.  But I can show you how one could attack the problem 
in a brute-force kind of way.  Let's use the following definitions
(from Alastair) to make things simpler:

flatten :: [[a]] -> [a]
flatten []       = []
flatten ([]:xss) = flatten xss
flatten ((x:xs):xss) = x : flatten (xs:xss)

-- This has a space leak, e.g., when reducing (length (foo2 1000000))
foo2 m
  = take m v
    where
      v = 1 : flatten (map double v)
      double x = [x,x]

-- This has no space leak, e.g., when reducing (length (foo3 1000000))
foo3 m
  = take m v
    where
      v = 1 : f1 (map single v)
      single x = [x]

We just start evaluating the program by hand and observe what's happening.
I'm being a little informal in my hand evaluations (and there's probably
a number of mistakes) but I think I've done well enough to visualize the
space behavior of these programs.

Regarding my derivations:
  * I'm using let's to simulate the sharing done by something like the STG
    machine.  If you're curious about why exactly evaluation is proceeding
    as it is, you might want to look at some of the work on "call by need 
    calculi".

  * I'm showing the evaluation steps using "p1 -> p2" to indicate that
    p1 reduces to p2.  Also, I "embed" evaluation steps into programs 
    as follows so as to save repetition (where C[] is any context):
       C[    p1
          -> p2
        ]
    which is the same as
      C[p1] -> C[p2]
    Hopefully the indentation will disambiguate things.

So, let's simulate the evaluation of (length $ foo3 100):

   length $ foo3 100
-> foldl' (\n _ -> n + 1) 0 $
       foo3 100
    -> take 100 v
    -> let v  = 1 : v2
           v2 = flatten (map single v)
       in take 100 (1:v2)
       -> 1 : take 99 v2
-> foldl' (\n _ -> n + 1) 1 $
       let v  = 1 : v2
           v2 = flatten (map single v)
             -> flatten (map single (1:v2))
             -> flatten ([1] : map single v2))
             -> 1 : flatten ([] : map single v2))
       in take 99 v2
    -> 
       let v  = 1 : v2
           v2 = 1 : v3
           v3 = flatten ([] : map single v2))
       in take 99 (1 : v3)
    ->                                                 {GC}
       let v2 = 1 : v3
           v3 = flatten ([] : map single v2))
       in take 99 (1 : v3)
       -> 1 : take 98 v3
-> foldl' (\n _ -> n + 1) 2 $
       let v2 = 1 : v3
           v3 = flatten ([] : map single v2))
             -> flatten (map single v2))
       in take 98 v3

So, there is no space leak here because at this point we have a program
which is the same as a previous program (up to variable naming and integer
values).  So the program isn't growing.

Note that for every foldl' reduction, there will be a GC (garbage collection)
step.

Now, let's simulate the evaluation of (length $ foo2 100):

   length $ foo2 100
-> foldl' (\n _ -> n + 1) 0 $
       foo2 100
    -> take 100 v
    -> let v  = 1 : v2
           v2 = flatten (map double v)
       in take 100 (1:v2)
       -> 1 : take 99 v2
-> foldl' (\n _ -> n + 1) 1 $
      let v  = 1 : v2
          v2 = flatten (map double v)
            -> flatten (map double (1:v2))
            -> flatten ([1,1] : map double v2)
            -> 1 : flatten ([1] : map double v2)
       in take 99 v2
    ->
      let v  = 1 : v2
          v2 = 1 : v3
          v3 = flatten ([1] : map double v2)
      in take 99 (1 : v3)
      -> 1 : take 98 v3
    ->                                             {GC}
      let v2 = 1 : v3
          v3 = flatten ([1] : map double v2)
      in take 99 (1 : v3)
      -> 1 : take 98 v3
-> foldl' (\n _ -> n + 1) 2 $
      let v2 = 1 : v3
          v3 = flatten ([1] : map double v2)
            -> 1 : flatten ([] : map double v2)
      in take 98 v3
   ->
      let v2 = 1 : v3
          v3 = 1 : v4
          v4 = flatten ([] : map double v2)
      in take 98 (1:v4)
      -> 1 : take 97 v4
-> foldl' (\n _ -> n + 1) 3 $
      let v2 = 1 : v3
          v3 = 1 : v4
          v4 = flatten ([] : map double v2)
            -> flatten (map double v2)
            -> flatten (map double (1:v3))
            -> flatten ([1,1] : map double v3)
            -> 1 : flatten ([1] : map double v3)
      in take 97 v4
   -> 
      let v2 = 1 : v3
          v3 = 1 : v4
          v4 = 1 : v5
          v5 = flatten ([1] : map double v3)
      in take 97 (1:v5)
   ->                                              {GC}
      let v3 = 1 : v4
          v4 = 1 : v5
          v5 = flatten ([1] : map double v3)
      in take 97 (1:v5)
      -> 1 : take 96 v5
-> foldl' (\n _ -> n + 1) 4 $
      let v3 = 1 : v4
          v4 = 1 : v5
          v5 = flatten ([1] : map double v3)
            -> 1 : flatten ([] : map double v3)
      in take 96 v5
   ->
      let v3 = 1 : v4
          v4 = 1 : v5
          v5 = 1 : v6
          v6 = flatten ([] : map double v3)
      in take 96 (1:v6)
      -> 1 : take 95 v6
-> foldl' (\n _ -> n + 1) 5 $
      let v3 = 1 : v4
          v4 = 1 : v5
          v5 = 1 : v6
          v6 = flatten ([] : map double v3)
      in take 95 v6

I've done a few more reduction steps here.  Note that for every two foldl'
reductions there is only one {GC} step!  So, the program is growing.
Thus, we have a space leak.

- Mark