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

[Thomas Schilling]

Sounds similar to the bug we had in 6.12.1.  It was a simple
accounting bug, i.e., the GC was not invoked, because it didn't know
that the memory was allocated.

On 20 April 2013 22:03, Edward Z. Yang <ezyang at mit.edu> wrote:
> 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
>>
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users