Haskell slow to compute Ackermann 4 1?

Question

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.

Answer 1

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.

Answer 2

Add a type signature to ack:

ack :: Int -> Int -> Int

This should solve two problems with your code:

Overly general types

Without the signature, the compiler derives the following type:

ack :: (Eq a, Eq b, Num a, Num b) => a -> b -> b

ack ends up generalized to all number types, instead of just integers. This additional layer of indirection makes the code slow.

Giving ack a concrete type (like Int) removes this indirection.

Type defaulting

In addition, I'm guessing your main action is written like this:

main = print (ack 4 1)

Your ack works on any number type, but you don't specify exactly which one. This means GHC chooses one automatically, in a process called type defaulting.

In this case, it chooses Integer, a variable length type. Because Integer can handle numbers of arbitrary size, it is much slower than the machine sized Int.

Conclusion

To summarize:

• Always write type signatures for top-level definitions.
• Always compile with -Wall.