[GHC] #7850: Strangely high memory usage on optimized Ackermann function

[GHC]

#7850: Strangely high memory usage on optimized Ackermann function
---------------------------------+------------------------------------------
    Reporter:  dolio             |       Owner:                         
        Type:  bug               |      Status:  new                    
    Priority:  normal            |   Milestone:                         
   Component:  Compiler          |     Version:  7.6.2                  
    Keywords:                    |          Os:  Unknown/Multiple       
Architecture:  Unknown/Multiple  |     Failure:  Runtime performance bug
  Difficulty:  Unknown           |    Testcase:                         
   Blockedby:                    |    Blocking:                         
     Related:                    |  
---------------------------------+------------------------------------------

Comment(by dolio):

 Here's the simplest test case I can think of to demonstrate the behavior:

 {{{
 -- main = print $ stk 4051 1000000
 main = print $ stk 4052 1000000

 stk :: Int -> Int -> Int
 stk _     0 = 0
 stk depth n = loop depth `seq` stk depth (n-1)

 loop :: Int -> Int
 loop 0 = 0
 loop n = loop (n-1) `seq` 0
 }}}

 With -O0, ~0% memory usage. With -O2, memory usage grows about linearly
 with time. If the alternate main is used, -O2 also uses ~0% memory.

 The boundary can be found using +RTS -K32K, which will stack overflow
 after one chunk is used. Choices of depth that do not overflow under such
 a setting will run in little memory, and choices that do will use large
 amounts of memory. The boundary number will probably be higher when
 running with 4-byte ints, for instance.

 Some +RTS -s stats look like:

    4052 -O2: 32259 MB total memory in use (504 MB lost due to
 fragmentation)
    4052 -O0:     1 MB total memory in use (0 MB lost due to fragmentation)
    4051 -O2:     1 MB total memory in use (0 MB lost due to fragmentation)

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7850#comment:22>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler