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.

Bombshell

Do the timings change when you annotate ack :: Int -> Int -> Int – Courier

I thought the annotations were just for the programmer, and it would infer type regardless? – Bombshell

Sure, but it makes a difference whether the function is just for Int or for any number. – Courier

@BretFontecchio If you don't specify a type signature, it defaults to variable length Integers, which are much slower than fixed size Int. – Bane

It did in fact speed it up by the way. "real 3m38.111s" – Bombshell

It should go at least 20 times faster .... – Courier

@LambdaFairy Worse, it probably infers ack :: Num a => a -> a -> a – Courier

@Courier Yeah, you're right. I just remembered the monomorphism restriction doesn't apply to function declarations P: – Bane

If you don't mind me asking, where's 20 come from? It seems to take 1/3 as long. – Bombshell

I would be interested in hearing about the running time complexity of the Hindley Milner implementation in Haskell. I read somewhere it is DEXP-hard, but I'm sure what would plug in where. What is n? The number of variables, the number of types, and so on... – Bombshell

@BretFontecchio On my meager Intel Core i3, above program runs in 9.003s when compiled by Frege, which is basically a Haskell dialect for the JVM. I did think that GHC could do better, but since Thomas M DuBuisson reported 15.5s with ghc -O2 I assume that the JIT has a good opportunity to shine in this case. – Courier

I must still be doing something wrong. I'm getting ~4 min with -O2 and there are no warnings in -Wall – Bombshell

@BretFontecchio Are you using GHC 7.6.3? Does your code include the type signatures? 4m is what I'd expect with Integer and -O2. – Hultin

hmm I'm not at my computer right now but it is extremely recent. I downloaded Haskell platform about 4 days ago. I am almost positive I have "Int" although I can't double check until 930 when I get out of lecture. Oh and -fllvm knocked 30 seconds off. – Bombshell

OK I snuck over to my laptop and checked. I have the type annotation ack :: Int -> Int -> Int – Bombshell

Is this bug really fixed in the latest Haskell platform? I have GHC 7.6.3 here (OS X 10.9, 2.5GHz i5) and ack (with Ints and -fllvm) uses a large amount of memory (gigs) and takes 40 seconds to run. Increasing the stack chunk size (compile with "-O2 -fllvm -rtsopts" and run "time ./Ackermann +RTS -kc1M"), as suggested in the old Stack Overflow post, results in a total time of 4.8 seconds. Could someone with GHC 7.8 try this? – Amidst

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.

Hultin

That's still almost a factor of 10 worse than ajhc, so I still think it's a performance bug. – Warranty

Compiler version might be relevant for this question – Coextensive

I'm using version 7.6.3 – Bombshell

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.

Bane

But if there's any function that requires Big Integers, it's Ackermann, isn't it? – Tarriance

Conveniently, Integer is not needed for this value of Ackermann. Also, the first (very frustrating) issue is actually lack of optimization and not types. – Hultin

I understand it's frustrating when many people make the same mistake, but it goes to show that it's an easy mistake to make, does it not? I do appreciate the patience though. – Bombshell

@BretFontecchio You have a point, I admit. I am confused about why the mistake is easy to make. No one runs gcc without -O3 and expects top-notch performance. Perhaps people have a (bad) mental connection between higher level languages and bytecode-centered languages that lean on JIT for optimizations? – Hultin

I normally code java in an ide with an ant build.xml that don't really update too often. can't speak for everyone but this seems common. – Bombshell