Search code examples
haskellghcackermann

Haskell slow to compute Ackermann 4 1?

Here's an old question from 7 months ago, when stack overflowers agreed that Haskell's inefficiency in computing the Ackermann function was due to a compiler error.

Ackermann very inefficient with Haskell/GHC

7 months later, this appears to be fixed. It seems like ack runs with linear memory, but it runs pretty freakin' slow.

main = print (ack 4 1)
-- Ackermann function
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n - 1))

$ time ./ack
65533

>real   8m53.274s
>user   8m47.313s
>sys    0m4.868s


Processor  2.8 GHz Intel Core i7
Memory  8 GB 1333 MHz DDR3
Software  Mac OS X Lion 10.7.5 (11G63)

I am just asking for any insights into this. The more detailed ones will get upvoted. Keep in mind I am new to functional programming and even simple remarks about tail recursion vs regular recursion would be appreciated and upvoted.

Solution

  • I don't know how you're running it, but I suspect the complete list is:

    1. Your program with no changes and compiling with no optimizations. Initial time: 7m29.755s

    2. It appears you didn't use optimization. Be sure to use -O2 and try -fllvm when compiling. New time: 1m2.412s

    3. Use explicit type signatures and use Int (vs the default of Integer) when you can. New time: 0m15.486s

    So we received almost 8x speed-up by using optimizations (why does every other benchmark question not use optimization flags?!?!?) and an additional ~4x by using Int instead of Integer.