Haskell计算Ackermann 4 1的速度很慢？

Question

这是7个月前的一个老问题,当时堆栈溢出器同意Haskell计算Ackermann函数的低效率是由于编译器错误造成的.

Ackermann与Haskell/GHC的效率非常低

7个月后,这似乎是固定的.似乎ack使用线性内存运行,但它运行速度非常慢.

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)

我只是要求对此有任何见解.更详细的将得到投票.请记住,我是函数式编程的新手,甚至关于尾递归与常规递归的简单评论也会受到赞赏和赞成.

Answer 1

我不知道你是怎么运行的,但我怀疑完整列表是:

1. 您的程序没有任何更改,编译时没有优化.初始时间:7m29.755s

2. 看来你没有使用优化.务必在编译时使用-O2并尝试-fllvm.新时间:1m2.412s

3. 使用显式类型签名并Int尽可能使用(默认值为Integer).新时间:0m15.486s

因此,我们通过使用优化获得了近8倍的加速(为什么每个其他基准测试问题都没有使用优化标志？!？!？)而使用Int而不是使用额外的~4倍Integer.