Why does this Haskell program allocate so much memory?

Question

Take a look at the following Haskell program:

-- (^) allocs memory so we define it using the native (**) pow :: Int -> Int -> Int pow xy = floor $ fromIntegral x ** fromIntegral y -- tail recursive, div and mod are native, I believe, so, no alloc isPalindrome :: Int -> Bool isPalindrome x = go (pow 10 (floor $ logBase 10 $ fromIntegral x)) x where go mx = x <= 0 || div xm == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) -- go is tail recursive too... no obvious allocation here wanderer :: Int -> Int wanderer n = go 0 (pow 10 n - 1) (pow 10 n - 1) where go pxy | p > 0 && div px >= pow 10 n = p go pxy | p > 0 && y < div px || y < x = go p (x-1) (pow 10 n - 1) go pxy | isPalindrome (x*y) = go (x*y) x (y-1) go pxy = go px (y-1) main = print . wanderer $ 8 

Profiling it, we get:

 Fri May 8 03:36 2015 Time and Allocation Profiling Report (Final) aff +RTS -p -RTS total time = 7.34 secs (7344 ticks @ 1000 us, 1 processor) total alloc = 6,487,919,472 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc isPalindrome Main 41.9 18.5 isPalindrome.go Main 22.6 1.4 wanderer.go Main 20.0 67.8 pow Main 15.5 12.3 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 47 0 0.0 0.0 100.0 100.0 main Main 95 0 0.0 0.0 0.0 0.0 CAF:main1 Main 92 0 0.0 0.0 0.0 0.0 main Main 94 1 0.0 0.0 0.0 0.0 CAF:main2 Main 91 0 0.0 0.0 100.0 100.0 main Main 96 0 0.0 0.0 100.0 100.0 wanderer Main 98 1 0.0 0.0 100.0 100.0 pow Main 101 1 0.0 0.0 0.0 0.0 wanderer.go Main 99 49995002 20.0 67.8 100.0 100.0 isPalindrome Main 102 49985002 41.9 18.5 80.0 32.2 pow Main 104 49985002 15.5 12.3 15.5 12.3 isPalindrome.go Main 103 52207117 22.6 1.4 22.6 1.4 pow Main 100 1 0.0 0.0 0.0 0.0 pow Main 97 2 0.0 0.0 0.0 0.0 CAF GHC.Conc.Signal 85 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding 78 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 76 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 69 0 0.0 0.0 0.0 0.0 CAF GHC.Event.Thread 55 0 0.0 0.0 0.0 0.0 

As far as I know, all my functions are tail recursive, and these foreplay functions are asm operations. However, this simple program allocates 7 GB of memory. Where does all the selection happen?

Answer 1

The distribution comes from go in isPalindrome :

 go mx = x <= 0 || div xm == mod x 10 && go (div m 100) (div (x - m * mod x 10) 10) 

On the right side we have a || . Short Circuit Semantics || implemented through lazy assessment. The GHC sees that the argument m not used if x <= 0 evaluates to True , so it does not decompress m , which allows it to remain non-displayable. Of course, in this case we better disable m as well, so let it do it.

 {-# LANGUAGE BangPatterns #-} go !mx = ... 

Now with ghc -O2 and +RTS -s :

  52,016 bytes allocated in the heap 3,408 bytes copied during GC 44,312 bytes maximum residency (1 sample(s)) 17,128 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) 

Answer 2

GHC was sometimes called "distribution assessment." More importantly, is memory retained. Just by watching the code, I don't see any obvious space leaks.

Have you looked at the runtime statistics ? You do not even need profiling libraries for this. The copied GC bytes and maximum residency are of great interest here ... both of which, I think, will be relatively very small.

Besides first-order problems, most of these distributions are likely to be closures. Are you compiling ghc -O to run the string analyzer? Even so, I’m not sure if the string analyzer can eliminate the closure distribution for the argument m in the first go function or the arguments x and y in the second go assume that beat patterns will significantly reduce your distributions here.

The practical consequences of tail recursion in Haskell are very different than strict language; therefore, if you are familiar with tail calls in strict language, your intuition is probably disabled.