我尝试计算Ackermann(4,1)并有不同的语言/编译器之间的性能有很大的区别。 下面是我的酷睿i7 3820QM结果，16G的Ubuntu 12.10 64位 ，
C：1.6秒 ， gcc -O3 （用gcc 4.7.2）
int ack(int m, int n) {
if (m == 0) return n+1;
if (n == 0) return ack(m-1, 1);
return ack(m-1, ack(m, n-1));
}
int main() {
printf("%d\n", ack(4,1));
return 0;
}
OCaml的：3.6s， ocamlopt （与OCaml的3.12.1）
let rec ack = function
| 0,n -> n+1
| m,0 -> ack (m-1, 1)
| m,n -> ack (m-1, ack (m, n-1))
in print_int (ack (4, 1))
标准ML：5.1s mlton -codegen c -cc-opt -O3 （与mlton 20100608）
fun ack 0 n = n+1
| ack m 0 = ack (m-1) 1
| ack m n = ack (m-1) (ack m (n-1));
print (Int.toString (ack 4 1));
球拍：11.5s racket （球拍v5.3.3）
(require racket/unsafe/ops)
(define + unsafe-fx+)
(define - unsafe-fx-)
(define (ack m n)
(cond
[(zero? m) (+ n 1)]
[(zero? n) (ack (- m 1) 1)]
[else (ack (- m 1) (ack m (- n 1)))]))
(time (ack 4 1))
哈斯克尔：未完成 ，后由22S杀死系统ghc -O2 （与GHC 7.4.2）
哈斯克尔：1.8秒 ajhc （与ajhc 0.8.0.4）
main = print $ ack 4 1
where ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Haskell的版本是失败，因为它需要太多的内存才能正常终止的唯一一个。 它冻结我的机器，填补被杀之前的交换空间。 我能做些什么来改善它没有严重fuglifying的代码？
编辑 ：我很欣赏一些渐近聪明的解决方案，但他们不正是我要求的。 这是详细了解看到编译器是否处理以相当有效的方式某些模式（堆，尾调用，取消装箱等）相比计算阿克曼函数。
编辑2：由于若干答复指出，这似乎是在最近版本的GHC的一个bug 。 我尝试用相同的代码AJHC并获得更好的性能。
非常感谢你 ：）
Answer 1:
注：内存占用率过高的问题是在GHC RTS中的错误 ，其中在堆栈溢出和新的堆栈分配在堆上它不检查垃圾收集是否到期。 它已经被固定在GHC HEAD。
我能够通过CPS转换来获得更好的性能ack ：
module Main where
data P = P !Int !Int
main :: IO ()
main = print $ ack (P 4 1) id
where
ack :: P -> (Int -> Int) -> Int
ack (P 0 n) k = k (n + 1)
ack (P m 0) k = ack (P (m-1) 1) k
ack (P m n) k = ack (P m (n-1)) (\a -> ack (P (m-1) a) k)
您的原始功能会消耗我的机器上的所有可用内存，而这一块在不断的空间中运行。
$ time ./Test
65533
./Test 52,47s user 0,50s system 96% cpu 54,797 total
ocaml的仍然较快，但是：
$ time ./test
65533./test 7,97s user 0,05s system 94% cpu 8,475 total
编辑：在编译时JHC ，你原来的程序是一样快OCaml的版本：
$ time ./hs.out
65533
./hs.out 5,31s user 0,03s system 96% cpu 5,515 total
编辑2：别的东西，我已经发现：具有较大的堆栈块大小（运行你的原程序+RTS -kc1M ）使得它在不断的空间中运行。 该CPS版本仍然是快一点，但。
编辑3：我设法生产运行几乎一样快OCaml的一个手动展开主循环的一个版本。 然而，当运行它仅适用+RTS -kc1M （丹Doel 已经提交了错误有关此问题的）：
{-# LANGUAGE CPP #-}
module Main where
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int
ack0 :: Int -> Int
ack0 n =(n+1)
#define C(a) a
#define CONCAT(a,b) C(a)C(b)
#define AckType(M) CONCAT(ack,M) :: Int -> Int
AckType(1)
AckType(2)
AckType(3)
AckType(4)
#define AckDecl(M,M1) \
CONCAT(ack,M) n = case n of { 0 -> CONCAT(ack,M1) 1 \
; 1 -> CONCAT(ack,M1) (CONCAT(ack,M1) 1) \
; _ -> CONCAT(ack,M1) (CONCAT(ack,M) (n-1)) }
AckDecl(1,0)
AckDecl(2,1)
AckDecl(3,2)
AckDecl(4,3)
ack :: P -> (Int -> Int) -> Int
ack (P m n) k = case m of
0 -> k (ack0 n)
1 -> k (ack1 n)
2 -> k (ack2 n)
3 -> k (ack3 n)
4 -> k (ack4 n)
_ -> case n of
0 -> ack (P (m-1) 1) k
1 -> ack (P (m-1) 1) (\a -> ack (P (m-1) a) k)
_ -> ack (P m (n-1)) (\a -> ack (P (m-1) a) k)
main :: IO ()
main = print $ ack (P 4 1) id
测试：
$ time ./Test +RTS -kc1M
65533
./Test +RTS -kc1M 6,30s user 0,04s system 97% cpu 6,516 total
编辑4：显然，空间泄漏被固定在GHC HEAD ，所以+RTS -kc1M不会在未来是必要的。
Answer 2:
它似乎有某种错误的参与。 什么GHC版本您使用的？
随着GHC 7，我得到了相同的行为，你怎么做。 该程序消耗所有可用的内存，而不会产生任何输出。
但是，如果我用GHC 6.12.1编译它只是ghc --make -O2 Ack.hs ，它完美的作品。 它计算在10.8s我的电脑上的结果，而普通的C版本需要7.8s。
我建议你报告GHC网站这个bug 。
Answer 3:
这个版本使用阿克曼函数的一些性质。 这不等同于其他版本，但它的速度快：
ackermann :: Int -> Int -> Int
ackermann 0 n = n + 1
ackermann m 0 = ackermann (m - 1) 1
ackermann 1 n = n + 2
ackermann 2 n = 2 * n + 3
ackermann 3 n = 2 ^ (n + 3) - 3
ackermann m n = ackermann (m - 1) (ackermann m (n - 1))
编辑：这是记忆化版本，我们可以看到，它很容易在Haskell到memoize的功能，唯一的变化是在调用点：
import Data.Function.Memoize
ackermann :: Integer -> Integer -> Integer
ackermann 0 n = n + 1
ackermann m 0 = ackermann (m - 1) 1
ackermann 1 n = n + 2
ackermann 2 n = 2 * n + 3
ackermann 3 n = 2 ^ (n + 3) - 3
ackermann m n = ackermann (m - 1) (ackermann m (n - 1))
main :: IO ()
main = print $ memoize2 ackermann 4 2
Answer 4:
下面是一个地道的版本，采用Haskell的lazyness和恒定的顶级表现的GHC的优化利用。
acks :: [[Int]]
acks = [ [ case (m, n) of
(0, _) -> n + 1
(_, 0) -> acks !! (m - 1) !! 1
(_, _) -> acks !! (m - 1) !! (acks !! m !! (n - 1))
| n <- [0..] ]
| m <- [0..] ]
main :: IO ()
main = print $ acks !! 4 !! 1
在这里，我们懒洋洋地构建矩阵阿克曼函数的所有值。 其结果是，随后将呼叫acks将不会重新计算任何东西（即评估acks !! 4 !! 1再次将无法运行时间的两倍）。
虽然这不是最快的解决方案，它看起来很像天真的实现，它是在内存使用方面非常有效，而且重铸的Haskell的怪异特征（lazyness）作为实力之一。
Answer 5:
我看不出这是一个错误可言， ghc只是没有采取的，它知道4和1是唯一参数的函数将永远不会有所谓的事实优势-那就是，说穿，它不作弊。 它也不会为你做数学常数，因此，如果你写了main = print $ ack (2+2) 1 ，就不会计算，2 + 2 = 4，直到运行时。 该ghc有更重要的事情要考虑。 如果你照顾它帮助后者难度可用http://hackage.haskell.org/package/const-math-ghc-plugin 。
因此ghc如果你做一些数学比如，这至少是一个hundered倍的速度与4和1作为参数，你的C程序的帮助。 但随着4 2试试吧：
main = print $ ack 4 2 where
ack :: Int -> Integer -> Integer
ack 0 n = n + 1
ack 1 n = n + 2
ack 2 n = 2 * n + 3
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1) )
这将得到正确的答案，所有〜20000个的数字，在十分之一秒下，而海湾合作委员会，与你的算法，将永远给错误的答案。
Answer 6:
在类似于你用C写的方式的方式写在Haskell的算法是不相同的算法，因为递归的语义有很大的不同。
下面是使用相同的数学算法的一个版本，但在这里我们代表呼吁阿克曼函数符号使用的数据类型。 这样一来，我们就可以更精确地控制递归的语义。
当与优化编译，这个版本在不断的内存中运行，但它是缓慢的 - 在与你相似的环境下约4.5分钟。 但我敢肯定它可以修改要快得多。 这仅仅是给的想法。
data Ack = Ack !Int
ack :: Int -> Int -> Int
ack m n = length . ackR $ Ack m : replicate n (Ack 0)
where
ackR n@(Ack 0 : _) = n
ackR n = ackR $ ack' n
ack' [] = []
ack' (Ack 0 : n) = Ack 0 : ack' n
ack' [Ack m] = [Ack (m-1), Ack 0]
ack' (Ack m : n) = Ack (m-1) : ack' (Ack m : decr n)
decr (Ack 0 : n) = n
decr n = decr $ ack' n
Answer 7:
This performance issue (except for GHC RTS bug obviously) seems to be fixed now on OS X 10.8 after Apple XCode update to 4.6.2. I can still reproduce it on Linux (I have been testing with GHC LLVM backend though), but not any more on OS X. After I updated the XCode to 4.6.2, the new version seems to have affected the GHC backend code generation for Ackermann substantially (from what I remember from looking at object dumps pre-update). I was able to reproduce the performance issue on Mac before XCode update - I don't have the numbers but they were surely quite bad. So, it seems that XCode update improved the GHC code generation for Ackermann.
Now, both C and GHC versions are quite close. C code:
int ack(int m,int n){
if(m==0) return n+1;
if(n==0) return ack(m-1,1);
return ack(m-1, ack(m,n-1));
}
Time to execute ack(4,1):
GCC 4.8.0: 2.94s
Clang 4.1: 4s
Haskell code:
ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Time to execute ack 4 1 (with +RTS -kc1M):
GHC 7.6.1 Native: 3.191s
GHC 7.6.1 LLVM: 3.8s
All were compiled with -O2 flag (and -rtsopts flag for GHC for RTS bug workaround). It is quite a head scratcher though. Updating XCode seems to have made a big difference with optimization of Ackermann in GHC.
文章来源: Ackermann very inefficient with Haskell/GHC
