[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                   |      Component:  Compiler      
 Version:  7.6.2                    |       Keywords:                
      Os:  Linux                    |   Architecture:  x86_64 (amd64)
 Failure:  Runtime performance bug  |      Blockedby:                
Blocking:                           |        Related:                
------------------------------------+---------------------------------------
 Greetings.

 The following post on stack overflow demonstrates some strange behavior
 in, at least, recent GHC versions (7.4.2 on):

 [http://stackoverflow.com/questions/16115815/ackermann-very-inefficient-
 with-haskell-ghc]

 The program in question is simple:

 {{{
 main = print $ ack 4 1

 ack :: Int -> Int -> Int
 ack 0 !n = n+1
 ack m  0 = ack (m-1) 1
 ack m  n = ack (m-1) $ ack m (n-1)
 }}}

 Here are the properties I've been able to deduce so far:

 1) When compiled without optimizations, the program uses almost no memory,
 but of course takes a while.

 2) When compiled with optimizations (-O and above), the program eats
 memory at a staggering rate. It easily freezes my machine in a matter of
 seconds.

 3) -ddump-simpl reveals that the loop is completely unboxed, operating
 only on Int#. -ddump-prep also shows no lets where allocation would
 presumably happen.

 4) Setting a maximum heap size typically seems to have no effect. When I
 set it to the minimum heap size with -M4096, even the optimized program
 seems to run in constant space most of the time. However, using something
 like -M1000000 seems to result in the outrageous memory usage, and the RTS
 never catches that far more than 1 megabyte of memory is being used. I had
 to convince myself that the flag actually does something with another test
 program.

 5) The standard bounded stack also does nothing.

 So, we seem to have a program that is allocating vast amounts of
 (ostensibly) non-heap, non-stack memory; but only when optimized.

 I believe I once set the maximum heap to 40960B, and killed the program
 before it killed my machine. On exiting, I got a heap overflow error. So,
 my initial stab would be that the completely unboxed loop somehow ''is''
 allocating in the heap, but somehow not in a way that ever allows the
 garbage collector or heap overflow check to run (similar to how a non-
 allocating loop can block any thread preemption). That's a wild guess,
 though.

 I'm unable to easily investigate the behavior on older GHC versions,
 unfortunately. So I'm unsure how far back this behavior goes. If I've
 missed something obvious, I apologize, but this seems like very odd
 behavior to me.

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