Strangely high memory usage on optimized Ackermann function

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.

Trac metadata

Trac field	Value
Version	7.6.2
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system	Linux
Architecture	x86_64 (amd64)