Haskell Heap Issues with Parameter Passing Style

Question

Here's a simple program that blows my heap to Kingdom Come:

intersect n k z s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))
p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

What the program does is calculate the intersection of two infinite series, stopping when it reaches 23 elements. But that's not important to me.

What's interesting is that as far as I can tell, there shouldn't be much here that is sitting on the heap. The function intersect is recursives with all recursions written as tail calls. State is accumulated in the arguments, and there is not much of it. 5 integers and a small list of tuples.

If I were a betting person, I would bet that somehow thunks are being built up in the arguments as I do the recursion, particularly on arguments that aren't evaluated on a given recursion. But that's just a wild hunch.

What's the true problem here? And how does one fix it?

Answer 1

If you have a problem with the heap, run the heap profiler, like so:

$ ghc -O2 --make A.hs -prof -auto-all -rtsopts -fforce-recomp
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A.exe ...

Which when run:

$ ./A.exe +RTS -M1G -hy

Produces an A.hp output file:

$ hp2ps -c A.hp

Like so:

So your heap is full of Integer, which indicates some problem in the accumulating parameters of your functions -- where all the Integers are.

Modifying the function so that it is strict in the lazy Integer arguments (based on the fact you never inspect their value), like so:

{-# LANGUAGE BangPatterns #-}

intersect n k !z !s rs c
  | c == 23   = rs
  | x == y    = intersect (n+1) (k+1) (z+1) (z+s) (f : rs) (c+1)
  | x < y     = intersect (n+1) k (z+1) s rs c
  | otherwise = intersect n (k+1) z s rs c
    where x = (2*n*n) + 4 * n
          y = (k * k + k )
          f = (z, (x `div` 2), (z+s))

p = intersect 1 1 1 0 [] 0

main = do
  putStr (show p)

And your program now runs in constant space with the list of arguments you're producing (though doesn't terminate for c == 23 in any reasonable time).