5

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.

Community
  • 1
  • 1
Bret Fontecchio
  • 629
  • 7
  • 16
  • 1
    Do the timings change when you annotate `ack :: Int -> Int -> Int` – Ingo Dec 11 '13 at 22:04
  • I thought the annotations were just for the programmer, and it would infer type regardless? – Bret Fontecchio Dec 11 '13 at 22:12
  • Sure, but it makes a difference whether the function is just for Int or for any number. – Ingo Dec 11 '13 at 22:13
  • 2
    @BretFontecchio If you don't specify a type signature, it defaults to variable length `Integer`s, which are much slower than fixed size `Int`. – Lambda Fairy Dec 11 '13 at 22:14
  • It did in fact speed it up by the way. "real 3m38.111s" – Bret Fontecchio Dec 11 '13 at 22:20
  • It should go at least 20 times faster .... – Ingo Dec 11 '13 at 22:21
  • 1
    @LambdaFairy Worse, it probably infers `ack :: Num a => a -> a -> a` – Ingo Dec 11 '13 at 22:25
  • @Ingo Yeah, you're right. I just remembered the monomorphism restriction doesn't apply to function declarations P: – Lambda Fairy Dec 11 '13 at 22:26
  • If you don't mind me asking, where's 20 come from? It seems to take 1/3 as long. – Bret Fontecchio Dec 11 '13 at 23:58
  • 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... – Bret Fontecchio Dec 11 '13 at 23:59
  • @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. – Ingo Dec 12 '13 at 00:11
  • I must still be doing something wrong. I'm getting ~4 min with -O2 and there are no warnings in -Wall – Bret Fontecchio Dec 12 '13 at 00:17
  • @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`. – Thomas M. DuBuisson Dec 12 '13 at 01:08
  • 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. – Bret Fontecchio Dec 12 '13 at 01:26
  • OK I snuck over to my laptop and checked. I have the type annotation ack :: Int -> Int -> Int – Bret Fontecchio Dec 12 '13 at 01:46
  • 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? – imladris Dec 12 '13 at 16:16

2 Answers2

10

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.

Thomas M. DuBuisson
  • 64,245
  • 7
  • 109
  • 166
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.
Lambda Fairy
  • 13,814
  • 7
  • 42
  • 68
  • But if there's any function that requires Big `Integers`, it's Ackermann, isn't it? – leftaroundabout Dec 11 '13 at 23:17
  • Conveniently, Integer is not needed for this value of Ackermann. Also, the first (very frustrating) issue is actually lack of optimization and not types. – Thomas M. DuBuisson Dec 11 '13 at 23:23
  • 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. – Bret Fontecchio Dec 12 '13 at 00:03
  • @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? – Thomas M. DuBuisson Dec 12 '13 at 01:06
  • 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. – Bret Fontecchio Dec 12 '13 at 01:18