Strangely high memory usage on optimized Ackermann function
The following post on stack overflow demonstrates some strange behavior in, at least, recent GHC versions (7.4.2 on):
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:
When compiled without optimizations, the program uses almost no memory, but of course takes a while.
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.
-ddump-simpl reveals that the loop is completely unboxed, operating only on Int#. -ddump-prep also shows no lets where allocation would presumably happen.
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.
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.