Why is there a space leak here?
David Bakin
davidbak@cablespeed.com
Mon, 28 May 2001 13:25:22 -0700
This is a multi-part message in MIME format.
------=_NextPart_000_0063_01C0E779.A61E3330
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
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=20
=3D take m v
where
v =3D 1 : flatten (map triple v)
triple x =3D [x,x,x]
-- This has no space leak, e.g., when reducing (length (foo2 1000000))
foo2 m=20
=3D take m v
where
v =3D 1 : flatten (map single v)
single x =3D [x]
-- flatten a list-of-lists
flatten :: [[a]] -> [a]
flatten [] =3D []
flatten ([]:xxs) =3D flatten xxs
flatten ((x':xs'):xxs) =3D x' : flatten' xs' xxs
flatten' [] xxs =3D flatten xxs
flatten' (x':xs') xxs =3D x': flatten' xs' xxs
------=_NextPart_000_0063_01C0E779.A61E3330
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 5.50.4522.1800" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT size=3D2>Why is there a space leak in foo1 but not in =
foo2? =20
(I.e., in Hugs Nov '99) foo1 eats cells (and eventually runs out) where =
foo2=20
doesn't. That is, if I do (length (foo1 1000000)) I =
eventually run=20
out of cells but (length (foo2 1000000)) runs fine (every GC returns =
basically=20
the same amount of space). Something must be wrong in flatten but =
it=20
follows the pattern of many functions in the prelude (which I'm trying =
to learn=20
from).</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>I have been puzzling over this for nearly a full day =
(getting=20
this reduced version from my own code which wasn't working). In =
general,=20
how can I either a) analyze code looking for a space leak or b) =
experiment=20
(e.g., using Hugs) to find a space leak? Thanks! --=20
Dave</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>-- This has a space leak, e.g., =
when=20
reducing (length (foo1 1000000))<BR>foo1 m <BR> =3D take m=20
v<BR> where<BR> v =3D 1 =
: flatten=20
(map triple v)<BR> triple x =3D =
[x,x,x]</FONT></DIV>
<DIV><FONT face=3D"Courier New"></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>-- This has no space leak, =
e.g., when=20
reducing (length (foo2 1000000))<BR>foo2 m <BR> =3D take m=20
v<BR> where<BR> v =3D 1 =
: flatten=20
(map single v)<BR> single x =3D =
[x]</FONT></DIV>
<DIV><FONT face=3D"Courier New" size=3D2></FONT> </DIV>
<DIV><FONT face=3D"Courier New" size=3D2>-- flatten a =
list-of-lists<BR>flatten ::=20
[[a]] -> [a]<BR>flatten=20
[]  =
; =3D=20
[]<BR>flatten ([]:xxs) =3D flatten=20
xxs<BR>flatten ((x':xs'):xxs) =3D x' : flatten' xs' xxs<BR>flatten' []=20
xxs =3D flatten =
xxs<BR>flatten' (x':xs')=20
xxs =3D x': flatten' xs' xxs</FONT></DIV>
<DIV> </DIV>
<DIV><FONT size=3D2></FONT> </DIV></BODY></HTML>
------=_NextPart_000_0063_01C0E779.A61E3330--