[Haskell-beginners] Space leak debugging

[Daniel Fischer]

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