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 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 -- 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] -- 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] -- 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
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
Interesting question. The functions certainly look as though either both should leak or neither should leak. As for how to chase this sort of problem, I'll try to describe everything I do in trying to chase the problem down in the hope that this might be instructive. 1) Is there really a problem? Using Feb 2001 Hugs, I run "hugs +g /tmp/leak.hs" and type length (foo1 1000000) output is: {{Gc:235464}}{{Gc:227548}}{{Gc:219900}}{{Gc:212509}}{{Gc:205364}}{{Gc:198465}}{{Gc:191793}}{{Gc:185343}}{{Gc:179119}}{{Gc:173090}}{{Gc:167274}}{{Gc:161653}}{{Gc:156217}}{{Gc:150968}}{{Gc:145888}}{{Gc:140989}}{{Gc:136245}}{{Gc:131668}}{{Gc:127238}}{{Gc:122965}}{{Gc:118832}}{{Gc:114844}}{{Gc:110976}}{{Gc:107248}}{{Gc:103648}}{{Gc:100165}}{{Gc:96796}}{{Gc:93542}}{{Gc:90391}}{{Gc:87353}}{{Gc:84419}}{{Gc:81583}}{Interrupted!} Yup, it leaks. I then quit (just to be certain), restart and type: length (foo2 1000000) output is: {{Gc:239721}}{{Gc:239718}}{{Gc:239722}}{{Gc:239725}}{{Gc:239713}}{{Gc:239717}}{{Gc:239717}}{{Gc:239722}}{{Gc:239725}}{{Gc:239713}}{{Gc:239717}}{{Gc:239717}}{{Gc:239722}}{{Gc:239725}}{Interrupted!} Nope, it doesn't leak. 2) Could it be something to do with CAFs and the monmomorphism restriction? Check the type: Main> :t foo1 foo1 :: Num a => Int -> [a] Main> :t foo2 foo2 :: Num a => Int -> [a] Same type, almost certainly not. (The fact that all definitions are of the form "foo m = ..." makes it even less likely. The fact that I tried this at all shows that I'm already grasping for straws.) 3) Could it be a bug in the garbage collector or code generator? 1) Try swapping the two definitions and see if it still leaks. Yes, still leaks. 2) Try adding a third definition in the hope that it will perturb code generation and heap allocation enough to make the problem show up. (This definition is based on "double x = [x,x]") Both foo1 (triple) and foo2 (double) leak, foo3 (single) still doesn't leak. 3) Try a different compiler (ghc) and run with +RTS -Sstderr flags: foo1: leaks (6Mb maximum residency) foo2: leaks (5Mb maximum residency) foo3: doesn't leak (1,112 bytes maximum residency) 4) Maybe there's something funny in your definition of flatten - write my own. f1 :: [[a]] -> [a] f1 [] = [] f1 ([]:xss) = f1 xss f1 ((x:xs):xss) = x : f1 (xs:xss) Nope, foo1 still leaks and foo3 doesn't leak. 5) Cut and paste code for map and take from language definition into this module in case Hugs (and GHC) are doing something funny. (The straws are getting smaller and further away.) No change. (Actually, I wrote the definitions from memory - effect should be the same.) Well, I thought I understood lazy evaluation, garbage collectors, Hugs and GHC but I'm at a complete loss for why one definition leaks and the other doesn't. I would be really fascinated to learn what is going on here. I'm attaching my revised version of David's program and David's original version. -- Alastair Reid reid@cs.utah.edu http://www.cs.utah.edu/~reid/ David's version: ---------------------------------------------------------------- -- 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] -- 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] -- 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 ---------------------------------------------------------------- The Haggoidal version: ---------------------------------------------------------------- module Main( main ) where import Prelude hiding ( take, map ) take :: Int -> [a] -> [a] take 0 xs = [] take m [] = [] take m (x:xs) | m > 0 = x : take (m-1) xs map :: (a -> b) -> ([a] -> [b]) map f [] = [] map f (x:xs) = f x : map f xs main :: IO () main = do print (length (foo1 1000000)) -- This has a space leak, e.g., when reducing (length (foo1 1000000)) foo1 m = take m v where v = 1 : f1 (map triple v) triple x = [x,x,x] -- This has no 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] -- This has no space leak, e.g., when reducing (length (foo3 1000000)) foo4 m = take m v where v = 1 : f1 (map single v) single x = [x,x,x] -- flatten a list-of-lists flatten :: [[a]] -> [a] flatten [] = [] flatten ([]:xxs) = flatten xxs flatten ((x':xs'):xxs) = x' : flatten' xs' xxs flatten' :: [a] -> [[a]] -> [a] flatten' [] xxs = flatten xxs flatten' (x':xs') xxs = x': flatten' xs' xxs f1 :: [[a]] -> [a] f1 [] = [] f1 ([]:xss) = f1 xss f1 ((x:xs):xss) = x : f1 (xs:xss) ----------------------------------------------------------------
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
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)
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
"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 1000000) 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
On Tue, 5 Jun 2001, Tom Moertel wrote:
"Wojciech Moczydlowski, Jr" wrote:
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
I was just writing that it stayed constant, when the executing program ran out of heap :). Seems that my claim about nhc98 was false - I didn't wait long enough to see the program stop. Sorry for mistaking you.
Tom
Wojciech Moczydlowski, Jr
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
Mark Tullsen <tullsen@cs.yale.edu> writes:
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.
Yeah, well, in this case this allegedly "truly great Haskell programmer" happened to be looking at the problem the wrong way. I started out assuming it was a compiler or garbage collector bug and didn't even think of trying to actually reason about the program using the CBN calculus. Blush! -- Alastair Reid ps Tell you what, I'll make up for it by making most of the fptools/hslib libraries work in Hugs. If you have read-write access to the cvs repository, all you have to do (as of 20 minutes ago) is: cvs -d <something> checkout hugs98 cvs -d <something> checkout fptools/hslibs cd hugs98/src/unix ./convert_hslibs ../../.. # path points to base of fptools tree ./configure --prefix=$HOME cd .. make install where <something> is whatever you normally use to get the CVS repository. Something like this :ext:<your username>@cvs.haskell.org:/home/cvs/root If you only have read access, you'll need to wait until it gets updated (sometime tonight) and then use :pserver:anoncvs@cvs.haskell.org:/cvs with the password "cvs".
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))) = Aaaarrggggh! 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 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))) = Aaaarrggggh! 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
From: "Tom Moertel" <tom-list-haskell@moertel.com>
Okay, then, what is the *right* way to reason about these things?
(Non?-)strictly speaking, there is no *right* way to reason about these things, as Haskell somehow seems to have neglected to acquire a semantics (blush - even Java has one, kind of..). The reason, as far as I can tell, is that everyone assumed that the core of Haskell is sufficiently similar to "standard" calculi (some of which were developed to make this so), so that those or "standard" works on implementation implicitly define what everyone assumes to be Haskell's semantics (I find it funny that the report, which equates "non-strict" and "lazy", refers to potential loss of sharing in two places, without ever bothering to explain how such sharing might come about in the first place.. or am I missing anything?). Perhaps one could say that Haskell was too lazy to acquire a semantics before it was needed?-) But call-by-need lambda-calculus, refered to in other replies, was developed in anticipation or awareness of that need, I think, and is a good place to get started without having to worry about implementation details.
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))) = Aaaarrggggh! You're right.
In essence, call-by-need is normal-order evaluation plus sharing of parameters, so you can adapt your deduction (which follows normal-order reduction, but ignores sharing) by taking care of sharing (I'll use where for that here): v = 1 : flatten (map single v) -> v = 1 : tl_v where tl_v = flatten (single 1 : map single tl_v) -- don't lose that sharing -> v = 1 : tl_v where tl_v = flatten ([1] : map single tl_v) -> v = 1 : tl_v where tl_v = 1 : flatten (map single tl_v) -- this looks familiar .. -> v = 1 : tl_v where tl_v = 1 : tl_tl_v -- there is now only one reference to this tl_tl_v = 1 : flatten (map single tl_tl_v) = v = 1 : 1 : tl_tl_v where tl_tl_v = 1:flatten (map single tl_tl_v) .. I've tried to stay close to your own derivation, but otherwise this should really correspond to Mark Tullsen's earlier posting. This might already enable you to adapt your derivation for the version with triple instead of single, but I would still suggest to have a look at the CBN papers. To complement my own earlier posting, GHood builds on Hood, which doesn't observe sharing or garbage-collection, so if one of these is important to the argument, observations have to be interpreted with more care than usual.Still, it can be quite helpful because it can give you some input about your program's behaviour Hth, Claus
Tom Moertel wrote:
Okay, then, what is the *right* way to reason about these things?
I will take the oppurtunity to advertise some recent work I have been doing together with David Sands. I think that the call-by-need lambda calculus is a very good starting point for gaining intuition about call-by-need beacuse it gives a way to reason about call-by-need computation at the term level. But the call-by-need lambda calculus was not designed for reasoning about space - there are terms which are considered equivalent which when you replace one by the other in a whole program may change the asymptotic space behaviour of the program. Therefore, we have been working on a theory of space equivalence based on an operational semantics for a small subset of Haskell. We have used the theory to reason about the to different definitions of the function any that were discussed on the list some months ago and I think it could be used in this case too. If you are interested you can find a draft paper at www.cs.chalmers.se/~gustavss/. We will submit the final version to ICFP in a few weeks so we would be very grateful for any comments. Regards, Jörgen Gustavsson.
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:-)
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
participants (8)
-
Alastair David Reid -
Claus Reinke -
David Bakin -
Jörgen Gustavsson -
Mark Tullsen -
S. Alexander Jacobson -
Tom Moertel -
Wojciech Moczydlowski, Jr