Why is GHC so much worse than JHC when computing the Ackermann function?

[Edward Z. Yang]

I don't seem to get the leak on latest GHC head.  Running the program
in GC debug mode in 7.6.2 is quite telling; the program is allocating
*a lot* of megablocks.  We probably fixed it though?

Edward

Excerpts from Mikhail Glushenkov's message of Sat Apr 20 01:55:10 -0700 2013:
> Hi all,
> 
> This came up on StackOverflow [1]. When compiled with GHC (7.4.2 &
> 7.6.2), this simple program:
> 
> main = print $ ack 4 1
>   where 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))
> 
> consumes all available memory on my machine and slows down to a crawl.
> However, when compiled with JHC it runs in constant space and is about
> as fast as the straightforward Ocaml version (see the SO question for
> benchmark numbers).
> 
> I was able to fix the space leak by using CPS-conversion, but the
> CPS-converted version is still about 10 times slower than the naive
> version compiled with JHC.
> 
> I looked both at the Core and Cmm, but couldn't find anything
> obviously wrong with the generated code - 'ack' is compiled to a
> simple loop of type 'Int# -> Int# -> Int#'. What's more frustrating is
> that running the program with +RTS -hc makes the space leak
> mysteriously vanish.
> 
> Can someone please explain where the space leak comes from and if it's
> possible to further improve the runtime of this program with GHC?
> Apparently it's somehow connected to the stack management strategy,
> since running the program with a larger stack chunk size (+RTS -kc1M)
> makes the space leak go away. Interestingly, choosing smaller stack
> chunk sizes (256K, 512K) causes it to die with an OOM exception:
> 
> $ time ./Test +RTS -kc256K
> Test: out of memory (requested 2097152 bytes)
> 
> 
> [1] http://stackoverflow.com/questions/16115815/ackermann-very-inefficient-with-haskell-ghc/16116074#16116074
>