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?
> 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?
"Steinitz, Dominic J" wrote:
> I'd love it if someone could write a tutorial paper on space
> leaks.
I agree that would be very useful.
> 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.
In my "traces" I did the garbage collections as soon as possible, basically
removing unused let bindings.
The ordering of evaluations is a bit more tricky ... I would
recommend becoming familiar with the various call-by-need calculi.
For me, it was more intuitive than trying to understand what's going
on at some lower level (such as the STG Machine) and then relate that
lower level to my program. With call-by-need calculi you can
understand what's going on at the source level. Here's a starting
point:
The Call-by-Need Lambda Calculus,
POPL 95, Ariola, Felleisen, Maraist, Odersky, & Wadler
@article{maraist-odersky-wadler:need-JFP98,
author = "John Maraist and Martin Odersky and Philip Wadler",
title = "The Call-by-Need Lambda Calculus",
journal = "Journal of Functional Programming",
volume = 8,
number = 3,
month = may,
year = 1998,
publisher = "Cambridge University Press",
}
- Mark
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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 ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
Mark Tullsen <[EMAIL PROTECTED]> 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 checkout hugs98 cvs -d checkout fptools/hslibs cd hugs98/src/unix ./convert_hslibs ../../.. # path points to base of fptools tree ./configure --prefix=$HOME cd .. make install where is whatever you normally use to get the CVS repository. Something like this :ext:@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:[EMAIL PROTECTED]:/cvs with the password "cvs". ___ 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?
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 ___ 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?
"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?
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 <[EMAIL PROTECTED]> 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 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
>
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 100))
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 100))
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 :
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?
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?
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
A pecular algebraic data structure
I've been working with one pecular algebraic data structure, named Register, which is described in currently upgraded http://www.numeric-quest.com/haskell/QuantumComputer.html. or in gzipped version of the same document http://www.numeric-quest.com/haskell/QuantumComputer.html.gz. Section 13 of that document outlines the background for the topic of this message. But the section is just way too long to quote it in here. But to summarize it: data Register is pecular because it is indexable but not observable in a standard way, and because two different representations can describe the same state. In theory there should be well defined transformation from one representation to another. This seems to me as a good subject for some research work. Granted that there are many experts on functional data structures out there (I do not want to pressure any of you gurus, so I am not naming anyone :-)), could you please look at the write-up and help me with the following questions? + Is the Register data structure strangely unique, or does it fit somewhere into a hierarchy of known functional data structures? I would be happy to learn that the latter is the case, since I could then start looking at it at a more formal, well known and tested way. + Is a non-uniqness of representation amenable to formal treatment, such as deforestation? Jan ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Advantages of Paper
Alastair David Reid wrote: > > > I find it therefore of concern that many crucial Haskell documents, > > including the standard and, for example, the various Glasgow Haskell > > manuals, are only available online. > > My printed copy of the Haskell 98 report is numbered: > > YaleU/DCS/RR-1106 [snip] Er, are you sure? According to ftp://ftp.cs.yale.edu/pub/TR/LISTING TR1106 is "The Haskell 1.3 Language Version" and comes from 1996. (Earlier versions of the Haskell Report also appear with separate numbers in this listing). http://citeseer.nj.nec.com doesn't appear to know of any later print versions. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Advantages of Paper
Judging from my logs, some libraries, such as University of Chicago library, do their own indexing of WWW. Jan ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Advantages of Paper
We're not really in a position to mail out bound copies of the Haskell report. We generally distribute our tech reports in electronic form and haven't even been asked for paper copies in years. I've got a few bound Haskell reports that I give to visitors but we don't plan to print any more. It would be nice if the report was published in book form someday! The original problem here is that there's no comprehensive archive of Haskell related research papers. At one point we were maintaining a set of useful papers at haskell.org by hand (Olaf did all the hard work ...) but it's not really feasable to do any of the haskell.org maintainence by hand anymore. I've been slowly putting together software to automate haskell.org - forms for adding new applications, libraries, documents, and anything else that you could want. However, I'm not done and really need help to get things finished. In general, haskell.org is open to anyone that wants to work on these things and I would highly encourage anyone with time available to pitch in! I think haskell.org is the right place to give documents a permant home and will be glad to assist anyone that wants to work on this with me. John ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Advantages of Paper
> I find it therefore of concern that many crucial Haskell documents, > including the standard and, for example, the various Glasgow Haskell > manuals, are only available online. My printed copy of the Haskell 98 report is numbered: YaleU/DCS/RR-1106 Copies can no doubt be obtained from the Yale Haskell Group though I'm afraid I don't know who you should write to or how much money to send. It would be a good idea if haskell.org described how to get a copy but I don't know who maintains those pages. As it is, you have to infer the existence of a Yale tech report for the language from the fact that the language report cites a tech report for the library :-) [I'm less concerned about GHC documentation because it comes with the compiler and it seems unlikely that you'd want one and not the other.] -- Alastair Reid[EMAIL PROTECTED]http://www.cs.utah.edu/~reid/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Why is there a space leak here?
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 <[EMAIL PROTECTED]> 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 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
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 100)
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 100)
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[EMAIL PROTECTED]http://www.cs.utah.edu/~reid/
David's version:
-- 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-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:
---
Advantages of Paper
I don't want to seem incredibly Luddite, but there are some things the World Wide Web is not good at, and one of them is permanence. Try for example finding out about Glasgow Haskell from http://www.dcs.gla.ac.uk, which was I think the standard URL a few years ago. In 2050 we may not even have a World Wide Web (remember Gopher?), or if we do URLs as we have them may be as outdated as those e-mail addresses I remember which included lots of percent signs telling the network to send your message to Birmingham via Beachy Head. I find it therefore of concern that many crucial Haskell documents, including the standard and, for example, the various Glasgow Haskell manuals, are only available online. I therefore suggest that they at least be printed out in the form of technical reports, and made available in this form to libraries, which are well-used to storing information long-term. Otherwise the curious in 2050 will be able to locate manuals for FORTRAN II and Simula (as I can do in 5 minutes in the local library), but getting Haskell documentation will be about as easy as reading 5-track paper tape. I don't think it matters if Haskell itself is obsolete in the year 2050, as it probably will be. But it will be a pity if most of the papers written using it are hard to figure out because the documentation itself is missing. ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
