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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
