Re: Why is GHC so much worse than JHC when computing the Ackermann function?
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-...
Hi, Am Samstag, den 20.04.2013, 13:03 -0700 schrieb 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?
it’s confirmed that it is fixed in HEAD. But it’d be really interesting to know what the bug was and how it was fixed. Could someone who has a setup for running bisect at his fingertips find out? Greetings, Joachim -- Joachim "nomeata" Breitner Debian Developer nomeata@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nomeata@joachim-breitner.de | http://people.debian.org/~nomeata
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
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-...
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
participants (3)
-
Edward Z. Yang -
Joachim Breitner -
Thomas Schilling