Why is GHC so much worse than JHC when computing the Ackermann function?
nominolo at googlemail.com
Sat Apr 20 23:03:46 CEST 2013
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?
> Excerpts from Mikhail Glushenkov's message of Sat Apr 20 01:55:10 -0700 2013:
>> Hi all,
>> This came up on StackOverflow . 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)
>>  http://stackoverflow.com/questions/16115815/ackermann-very-inefficient-with-haskell-ghc/16116074#16116074
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users