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

20 Apr 2013

      #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

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

tags

participants (2)