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:
-
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.
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) |