On Tue, 29 May 2001, Tom Pledger wrote:

David Bakin writes:

a) Look at how much of the list needs to exist at any one time.

| -- 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]

When you consume the (3N)th cell of v, you can't yet garbage collect the Nth cell because it will be needed for generating the (3N+1)th, (3N+2)th and (3N+3)th.

So, as you proceed along the list, about two thirds of it must be retained in memory.

Last sentence seems false. You free up Nth cell of v when you finish with 3Nth cell of result.

| -- This has no space leak, e.g., when reducing (length (foo2 1000000)) | foo1 m (...the only difference below:) | single x = [x]

Greetings :-) Michal Gajda korek@icm.edu.pl *knowledge-hungry student*

Ah, thank you for pointing out concat to me. (Oddly, without knowing about concat, I had tried foldr1 (++) and also foldl1 (++) but got the same space problem and so tried to 'factor it out'.) OK, now I see what's going on - your explanation is good, thanks. Which of the various tools built-in or added to Hugs, GHC, NHC, etc. would help me visualize what's actually going on here? I think Hood would (using a newer Hugs, of course, I'm going to try it). What else? -- Dave ----- Original Message ----- From: "Tom Pledger" To: "David Bakin" Cc: Sent: Monday, May 28, 2001 1:59 PM Subject: Why is there a space leak here?

David Bakin writes: : | 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

a) Look at how much of the list needs to exist at any one time.

| -- 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]

When you consume the (3N)th cell of v, you can't yet garbage collect the Nth cell because it will be needed for generating the (3N+1)th, (3N+2)th and (3N+3)th.

So, as you proceed along the list, about two thirds of it must be retained in memory.

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

By contrast, when you consume the (N+1)th cell of this v, you free up the Nth, so foo2 runs in constant space.

| -- flatten a list-of-lists | flatten :: [[a]] -> [a] :

Rather like concat?

Regards, Tom

That's a very nice visualization - exactly the kind of thing I was hoping for. I grabbed your papers and will look over them for more information, thanks very much for taking the trouble! The animations you sent me - and the ones on your page - are really nice; it would be nice to have a system like HOPS available with GHC/GHCi (I understand it is more than the visualization system, but that's a really useful part of it). (I also found out that Hood didn't help for this particular purpose - though now that I see how easy it is to use I'll be using it all the time. But it is carefully designed to show you ("observe") exactly what has been evaluated at a given point in the program. Thus you can't use it (as far as I can tell) to show the data structures that are accumulating that haven't been processed yet - which is what you need to know to find a space problem.) -- Dave ----- Original Message ----- From: To: Cc: Sent: Tuesday, May 29, 2001 12:49 AM Subject: Re: Why is there a space leak here?

David Bakin writes:

...

Which of the various tools built-in or added to Hugs, GHC, NHC, etc.

would

...

help me visualize what's actually going on here? I think Hood would (using a newer Hugs, of course, I'm going to try it). What else?

I just used my old ghc-4.06 add-in ``middle-end'' ``MHA'' to generate a HOPS module from David's message (slightly massaged, appended below), and then used HOPS to generate two animations:

http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo1_20.ps.gz http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo2_20.ps.gz

Hold down the space key in ghostview to get the animation effect!

The left ``fan'', present in both examples, is the result list, and only takes up space in reality as long as it is used. The right ``fan'', visible only in foo1, contains the cycle of the definition of v, and represents the space leak. The take copies cons node away from the cycle.

The HOPS input was generated automatically by an unreleased GHC ``middle end'' that is still stuck at ghc-4.06.

The homepage of my term graph programming system HOPS is:

http://ist.unibw-muenchen.de/kahl/HOPS/

Wolfram

...

module Bakin where

-- This has a space leak, e.g., when reducing (length (foo1 1000000))

...

foo1 :: Int -> [Int] foo1 m = take m v where v = 1 : flatten (map triple v) triple x = [x,x,x]

-- This has no space leak, e.g., when reducing (length (foo2 1000000))

...

foo2 :: Int -> [Int] foo2 m = take m v where v = 1 : flatten (map single v) single x = [x]

-- flatten a list-of-lists

...

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