#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