Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Space leak debugging (Philip Scott)
2. Re: Space leak debugging (Daniel Fischer)
3. Re: Space leak debugging (Brandon S. Allbery KF8NH)
4. Re: Space leak debugging (Philip Scott)
5. Re: Space leak debugging (Philip Scott)
----------------------------------------------------------------------
Message: 1
Date: Thu, 03 Jun 2010 21:18:12 +0100
From: Philip Scott <[email protected]>
Subject: [Haskell-beginners] Space leak debugging
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hello again, it's me, your favourite haskell beginner :)
This one really has me puzzled. I've got a little example here - the
program itself is a bit silly but it illustrates my problem nicely.
He's a little program:
import qualified Data.ByteString as B
chunkFiller i bs = do
if (B.null bs ) then return 1
else chunkFiller (i+1) bs
main = do
let bs = (B.singleton 10)
j <- chunkFiller 0 bs
return 1
It runs forever, which is fine, but it doesn't run in constant space. In
fact, it gobbles up all the memory until it can't get any more and dies.
I can't for the life of me work out what is going on, surely there is
some enormous thunk being built up somewhere, but for all the
Debug.Trace(), $!, seq's, and profilign outputs in the world I can't
figure out where. What is *really* interesting is that if you replace
the 'if' line with
if (B.null bs || i== -1) then return 1
(i never equals -1) then it runs in constant space! That just boggles my
mind.
As usual, any thoughts greatly appreciated.
All the best,
Philip
------------------------------
Message: 2
Date: Thu, 3 Jun 2010 23:51:40 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Space leak debugging
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Thursday 03 June 2010 22:18:12, Philip Scott wrote:
> Hello again, it's me, your favourite haskell beginner :)
>
> This one really has me puzzled. I've got a little example here - the
> program itself is a bit silly but it illustrates my problem nicely.
>
> He's a little program:
>
> import qualified Data.ByteString as B
>
> chunkFiller i bs = do
> if (B.null bs ) then return 1
> else chunkFiller (i+1) bs
>
> main = do
> let bs = (B.singleton 10)
> j <- chunkFiller 0 bs
> return 1
>
> It runs forever, which is fine, but it doesn't run in constant space. In
> fact, it gobbles up all the memory until it can't get any more and dies.
> I can't for the life of me work out what is going on, surely there is
> some enormous thunk being built up somewhere,
Yep.
chunkFiller 0 bs
~> chunkFiller (0+1) bs
~> chunkFiller ((0+1)+1) bs
~> chunkFiller (((0+1)+1)+1) bs
~> ...
Since the loop doesn't do much, the thunk grows really fast:
$ ./philLeak +RTS -s -M400M
./philLeak +RTS -s -M400M
Heap exhausted;
Current maximum heap size is 419430400 bytes (400 MB);
use `+RTS -M<size>' to increase it.
414,708,668 bytes allocated in the heap
1,173,761,740 bytes copied during GC
414,303,860 bytes maximum residency (11 sample(s))
5,643,660 bytes maximum slop
418 MB total memory in use (3 MB lost due to fragmentation)
Generation 0: 781 collections, 0 parallel, 2.06s, 2.16s elapsed
Generation 1: 11 collections, 0 parallel, 7.64s, 13.11s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.26s ( 0.26s elapsed)
GC time 9.70s ( 15.27s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 9.95s ( 15.54s elapsed)
%GC time 97.4% (98.3% elapsed)
Alloc rate 1,619,867,147 bytes per MUT second
Productivity 2.6% of total user, 1.6% of total elapsed
> but for all the
> Debug.Trace(), $!, seq's, and profilign outputs in the world I can't
> figure out where.
a) BangPatterns, put a bang on the i,
chunkFiller !i bs = ...
b) else i `seq` chunkFiller (i+1) bs
c) else (chunkFiller $! i+1) bs
all of those cure the space leak.
> What is *really* interesting is that if you replace
> the 'if' line with
>
> if (B.null bs || i== -1) then return 1
>
> (i never equals -1) then it runs in constant space! That just boggles my
> mind.
bs isn't null, so it must check whether i == (-1). For that, it must
evaluate i, hence it doesn't build a thunk.
>
> As usual, any thoughts greatly appreciated.
>
> All the best,
>
> Philip
------------------------------
Message: 3
Date: Fri, 4 Jun 2010 01:25:16 -0400
From: "Brandon S. Allbery KF8NH" <[email protected]>
Subject: Re: [Haskell-beginners] Space leak debugging
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Jun 3, 2010, at 16:18 , Philip Scott wrote:
> that if you replace the 'if' line with
>
> if (B.null bs || i== -1) then return 1
>
> (i never equals -1) then it runs in constant space! That just
> boggles my mind.
That's your clue: since adding i there makes it run in constant
space, you must be forcing its evaluation when it otherwise was just
building thunks. So you need to make i strict with seq or case.
--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [email protected]
system administrator [openafs,heimdal,too many hats] [email protected]
electrical and computer engineering, carnegie mellon university KF8NH
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url :
http://www.haskell.org/pipermail/beginners/attachments/20100604/118366b7/PGP-0001.bin
------------------------------
Message: 4
Date: Fri, 04 Jun 2010 09:12:56 +0100
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Space leak debugging
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi Daniel,
>
>> It runs forever, which is fine, but it doesn't run in constant space. In
>> fact, it gobbles up all the memory until it can't get any more and dies.
>> I can't for the life of me work out what is going on, surely there is
>> some enormous thunk being built up somewhere,
>>
> Yep.
>
> chunkFiller 0 bs
> ~> chunkFiller (0+1) bs
> ~> chunkFiller ((0+1)+1) bs
> ~> chunkFiller (((0+1)+1)+1) bs
> ~> ...
>
You are entirely right, thank you! I was totally fixated on the
bytestring, I never even considered it might be something to do with my
inncoent looking accumulator :)
You guys are awesome.
- Phil
------------------------------
Message: 5
Date: Fri, 04 Jun 2010 09:13:37 +0100
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Space leak debugging
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
On 03/06/2010 22:58, Markus Läll wrote:
> I'm going to guess, that the testing i for equality forces it to be
> evaluated to a integer on every iteration, so it wont grow a recursive
> i + 1 + 1 + ... thunk.
>
>
Spot on! Thank you ever so much.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 24, Issue 4
****************************************
