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

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] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH