Re: Why is there a space leak here?
S. Alexander Jacobson [EMAIL PROTECTED] writes: On 6 Jun 2001, Carl R. Witty wrote: S. Alexander Jacobson [EMAIL PROTECTED] writes: For example w/ foldl: foldl + 0 [1..1] foldl (+) ((+) 0 1) [2..1] foldl (+) ((+) ((+) 0 1) 2) [3..1] 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? It's complicated. You can't (in general) know whether application of a function will increase or decrease the space used. If you were running out of space, would you just search the whole unevaluated program graph for reductions which somehow seemed likely to reduce the space used? Would you add such reduction nodes to some global list at the time they were created? I'm not clear why you can't in general notice that you are using more space after function application than before. I it hard to see why a program couldn't do the analysis I just did on foldl. I wasn't worried about foldl; you assumed that (+) 0 1 got smaller if you carried out the application. Even for (+) on Integer, this is not guaranteed (for large integers, if something else happens to be holding on to the summands, evaluating the addition can increase total space usage). You could accumulate statistics on funtions that increase/decrease space used at runtime and evaluate those that do reduce space used... Right, that's the sort of thing I meant about likely above. But how do you find such function applications in the global program graph, if you seem to be running low on space? (And you also need to realize that some functions might usually have small outputs, and sometimes have large outputs.) One portable way to implement a memoizing function in Haskell (if the domain of the function is countable) is to lazily build a data structure that contains the results of the function on every possible argument. Then you evaluate the portions of the data structure that you need; the result on each argument is only evaluated once. This probably would count as a growing expression, and it's certainly possible that the function on some arguments would be bottom. I don't think I understood this. Can you clarify? Let me know if JCAB's response wasn't enough here. Carl Witty ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
On 6 Jun 2001, Carl R. Witty wrote: S. Alexander Jacobson [EMAIL PROTECTED] writes: For example w/ foldl: foldl + 0 [1..1] foldl (+) ((+) 0 1) [2..1] foldl (+) ((+) ((+) 0 1) 2) [3..1] 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? It's complicated. You can't (in general) know whether application of a function will increase or decrease the space used. If you were running out of space, would you just search the whole unevaluated program graph for reductions which somehow seemed likely to reduce the space used? Would you add such reduction nodes to some global list at the time they were created? I'm not clear why you can't in general notice that you are using more space after function application than before. I it hard to see why a program couldn't do the analysis I just did on foldl. You could accumulate statistics on funtions that increase/decrease space used at runtime and evaluate those that do reduce space used... 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? It's certainly possible. You are trading off the likelihood that an exploding expression contains a bottom against the liklihood that the programmer would prefer the exploding expression not to explode. Much of this type of work can be done as test-time warnings One portable way to implement a memoizing function in Haskell (if the domain of the function is countable) is to lazily build a data structure that contains the results of the function on every possible argument. Then you evaluate the portions of the data structure that you need; the result on each argument is only evaluated once. This probably would count as a growing expression, and it's certainly possible that the function on some arguments would be bottom. I don't think I understood this. Can you clarify? -Alex- ___ S. Alexander Jacobson Shop.Com 1-646-638-2300 voiceThe Easiest Way To Shop (sm) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here? (fwd)
Hi Claus, I've had a look at this example in GHood, and you are right, nhc98 does seem to create several copies of v-in. import Observe foo1 m = take m (observe v-out v) where v = 1 : concat (map triple (observe v-in v)) triple x = [x,x,x] main = printO $ (foo1 100::[Int]) Perhaps Malcolm can explain what nhc98 does with this example? At a guess, I think the answer lies in lambda-lifting. nhc98 -c Leak.hs +CTS -lift -CTS shows this code for `v' (reformatted a little to make it easier to read): Main.Prelude.173.v = \ v223 v224 - Prelude.: (Prelude._apply1 (Prelude.fromInteger v223) 1L) (Prelude._apply1 (Prelude.concat) (Prelude.map (Main.Prelude.174.triple) (Observe.observe (Observe.Observable.Prelude.[] v224) (LAMBDA225) (Prelude._apply2 (Main.Prelude.173.v) v223 v224 v takes two arguments; v223 represents the numeric dictionary, and v224 the Observer dictionary. The recursive reference to v is not a cyclic pointer to a constant structure, but actually a function call. I believe the real culprit is that nhc98 does not implement the monomorphism restriction. IIRC, the DMR applies to every group of simple pattern bindings at the same let-bound scope, not just the top-level, so really we ought to default-away the dictionaries, which would solve this particular space oddity. Regards, Malcolm ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
S. Alexander Jacobson [EMAIL PROTECTED] writes: For example w/ foldl: foldl + 0 [1..1] foldl (+) ((+) 0 1) [2..1] foldl (+) ((+) ((+) 0 1) 2) [3..1] 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? It's complicated. You can't (in general) know whether application of a function will increase or decrease the space used. If you were running out of space, would you just search the whole unevaluated program graph for reductions which somehow seemed likely to reduce the space used? Would you add such reduction nodes to some global list at the time they were created? 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? It's certainly possible. One portable way to implement a memoizing function in Haskell (if the domain of the function is countable) is to lazily build a data structure that contains the results of the function on every possible argument. Then you evaluate the portions of the data structure that you need; the result on each argument is only evaluated once. This probably would count as a growing expression, and it's certainly possible that the function on some arguments would be bottom. 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... In general, this problem is uncomputable. It might be possible to come up with some useful approximation, but I bet that's a very difficult research problem. Carl Witty ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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 100))
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
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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..1]
foldl (+) ((+) 0 1) [2..1]
foldl (+) ((+) ((+) 0 1) 2) [3..1]
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 100))
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
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
___
S. Alexander Jacobson Shop.Com
1-646-638-2300 voiceThe Easiest Way To Shop (sm)
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
On Tue, 5 Jun 2001, Tom Moertel wrote: 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: So the problem isn't Hugs but rather the definition of v, which grows faster than it can be consumed. Tom How come then that the very program compiled under nhc98 evaluates without any problem, with memory usage below 1M during its execution? Wojciech Moczydlowski, Jr ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
Wojciech Moczydlowski, Jr wrote: How come then that the very program compiled under nhc98 evaluates without any problem, with memory usage below 1M during its execution? My claim was that v (as defined) grew faster than it could be consumed, not that (length (foo1 n)) couldn't be evaluated in constant space. Even so, your results suggest that nhc98 is doing something interesting. Does the memory usage remain constant even if you take 10 or 100 times the number of elements? If so, perhaps nhc98 is smart enough to know that length (take n x) = n for all infinite lists x. It might apply those smarts to optimize out the expansion of v in foo1 when foo1's result is used as the argument of length. Out of curiosity, what happens if you consume those elements with foldl' (+) 0 rather than length? Alternatively, if nhc98 were smart enough to prove that foo1 n = replicate n 1 it could do away with v altogether, which would also explain the interesting behavior. And if nhc does *that*, my hat's off to the nhc98 folks. Or, if your constants are hard-coded, perhaps nhc98 is evaluating the (length foo1 100) expression at compile time. What happens to memory consumption if foo1's argument is supplied at run time? Or maybe I'm mistaken about v. Wouldn't be the first time I've done something boneheaded. ;-) In any case, I am curious about what nhc98 is doing internally. Any ideas? Cheers, Tom ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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 100))
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
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
I'd love it if someone could write a tutorial paper on space leaks. Even with the explanations that have been provided, I find it difficult to understand why expressions get evaluated in a particular order and why garbage collections happen at a given point. Dominic. - 21st century air travel http://www.britishairways.com ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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. I think there have been several good explanations already, or is there anything wrong with them? As Olaf pointed out, one might use GHood for the job: http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/GHood/ An example on how to add observations in this case, and how to interpret the results might be helpful to those who haven't used GHood. 1. Code: import Observe foo1 m = take m (observe v-out v) where v = 1 : concat (map triple (observe v-in v)) triple x = [x,x,x] main = printO $ (foo1 100::[Int]) 2. Interpretation: Using Hugs to generate the observations, you should see the two views of v evolving just as other mails in this thread have explained, i.e., v-out grows at three times the rate of v-in. Remembering that these are two views of the same structure, the problem is that generating v-out depends on v-in, which is v-out;-) which means that the program execution should hold on to whatever v-out delivers until observers of v-in are through with it. In simpler words: v-out to v-in: you ain't seen nothing yet!. 3. Variation: Wojciech suggested that nhc's behaviour seems to differ slightly, which prompted me to try whether this would be visible in GHood. For explanation: Hood is portable, in that it works with most Haskell implementations (special version make use of more features, when available, and cater for renamed IOExtras..), but as it instruments those Haskell implementations to do its work, its observations can actually depend on what the implementation does. As GHood shows you observations in more detail, you'll see even more differences (such as: evaluation order of additions in nhc98 seems to depend on the type;-). Trying the code above with nhc98-1.02 and the matching variant of Observe.lhs, you'll see something odd: instead of two views of v evolving in parallel, further copies of the v-in-view are created. So, every three elements in v-out, we need another element of v-in(1), every three elements in v-in(1), we seem to need another element of v-in(2), etc. Perhaps Malcolm can explain what nhc98 does with this example? Oh, and for all the honchos Alastairs referred to: I seem to remember that the work on preserving cycles with lazy memo functions also had some comments about avoiding unnecessary growth of cyclic structures. Can anyone figure out how to apply that to this example (or tell me that it is impossible)? Hth, Claus PS: Getting new email in before sending this off, I see that some explainers now refer to themselves as foolish, but I'll send this off anyway, at the risk of adding myself to that foolish Haskell programmers club:-) ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
Tom Moertel wrote: Mark Tullsen wrote: 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. Whoops. Now don't I feel foolish. As far as I can tell, your argument would also apply to foo2, which doesn't have a space leak. Hmmm... Let's see. foo2 m = take m v where v = 1 : flatten (map single v) single x = [x] v = 1 : flatten (map single v) = 1 : flatten (map single (1 : flatten (map single v))) = 1 : flatten (single 1 : map single (flatten (map single v))) = 1 : flatten ([1] : map single (flatten (map single v))) = 1 : 1 : flatten (map single (flatten (map single v))) = Aaaarrh! You're right. Now don't I feel double foolish. :P Okay, then, what is the *right* way to reason about these things? Cheers, Tom Tom, I don't know if this approach is the *right* way but it's one way. This approach is very brute force, and I'm sure there are experts out there who can think and reason at a much higher level than this. But the brute force approach is this: Start evaluating your program symbolically You can do this at the source level using a CBN (call-by-need) calculus. If the program (the program in CBN includes the heap) starts growing in size faster than expected then you have a space leak. Simple, but a bit tedious. It would be great if we had a tool that could output such a trace. - Mark ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Sent: Tuesday, May 29, 2001 12:49 AM Subject: Re: Why is there a space leak here? David Bakin [EMAIL PROTECTED] 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 100)) 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 100)) 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 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Why is there a space leak here?
David Bakin wrote: 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.) You can use GHood, http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/GHood/ . It animates the evaluation process at a given point in the program. It doesn't show unevaluated expressions, but for most purposes you don't need to see them. Most important is to see when which subexpression is evaluated. (an older version of Hood, which is distributed with nhc, also has an animation facility) At some time we also hope to provide such an animation viewer for our Haskell tracer Hat. The trace already contains all the necessary information. Ciao, Olaf -- OLAF CHITIL, Dept. of Computer Science, University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Why is there a space leak here?
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 100)) I eventually run out of cells but (length (foo2 100)) 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 -- This has a space leak, e.g., when reducing (length (foo1 100))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 100))foo2 m = take m v where v = 1 : flatten (map single v) single x = [x] -- flatten a list-of-listsflatten :: [[a]] - [a]flatten [] = []flatten ([]:xxs) = flatten xxsflatten ((x':xs'):xxs) = x' : flatten' xs' xxsflatten' [] xxs = flatten xxsflatten' (x':xs') xxs = x': flatten' xs' xxs
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 100)) | 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 100)) | 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 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Why is there a space leak here?
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 100)) | 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 100)) | foo1 m (...the only difference below:) | single x = [x] Greetings :-) Michal Gajda [EMAIL PROTECTED] *knowledge-hungry student* ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Why is there a space leak here?
Michal Gajda writes: | On Tue, 29 May 2001, Tom Pledger wrote: : | 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. I counted from 0. Scouts' honour. Call (!!) as a witness. ;-) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Why is there a space leak here?
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 [EMAIL PROTECTED] To: David Bakin [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] 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 100)) | 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 100)) | 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 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
