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

[Mikhail Glushenkov]

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

-- 
()  ascii ribbon campaign - against html e-mail
/\  www.asciiribbon.org   - against proprietary attachments