Ackermann与Haskell / GHC非常低效
我试着计算Ackermann(4,1) ，不同语言/编译器之间的性能差别很大。 以下是我的Core i7 3820QM，16G，Ubuntu 12.10 64bit ，
C：1.6s ， 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 mn = 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 mn) (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）
Haskell：1.8s ajhc （with 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 mn = ack (m-1) (ack m (n-1))
Haskell版本是唯一一个无法正常终止，因为它占用太多的内存。 它冻结我的机器，并填补交换空间才被杀死。 我可以做些什么来改善它，而不会严重污染代码？
编辑 ：我欣赏一些渐近更聪明的解决scheme，但他们不完全是我所要求的。 这更多的是看看编译器是否以合理有效的方式处理某些模式（堆栈，尾部调用，拆箱等），而不是计算ackermann函数。
编辑2 ：正如几个答复所指出的，这似乎是GHC最近版本中的一个错误 。 我使用AJHC尝试相同的代码，并获得更好的性能。
非常感谢你 ：）
注意：高内存使用率问题是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 mn) k = ack (P m (n-1)) (\a -> ack (P (m-1) a) k)
您的原始function消耗我的机器上的所有可用内存，而这个内存在恒定的空间中运行。
$ 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 （Dan 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 mn) 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
testing：
$ time ./Test +RTS -kc1M 65533 ./Test +RTS -kc1M 6,30s user 0,04s system 97% cpu 6,516 total
编辑4 ：显然， GHC HEAD中的空间泄漏是固定的 ，所以+RTS -kc1M将来不需要。
似乎有涉及的一些错误。 你正在使用什么GHC版本？
与GHC 7，我得到了与你一样的行为。 该程序消耗所有可用内存而不产生任何输出。
但是，如果我使用ghc --make -O2 Ack.hs编译GHC 6.12.1，它可以很好地工作。 它计算在我的电脑10.8s的结果，而普通的C版本需要7.8s 。
我build议你在GHC网站上报告这个错误 。
这个版本使用了ackermann函数的一些属性。 这不等同于其他版本，但速度很快：
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 mn = ackermann (m - 1) (ackermann m (n - 1))
编辑：这是一个memoization的版本，我们看到很容易记住haskell函数，唯一的变化是在调用网站：
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 mn = ackermann (m - 1) (ackermann m (n - 1)) main :: IO () main = print $ memoize2 ackermann 4 2
以下是一个惯用的版本，它利用了Haskell的懒惰和GHC对常量顶级expression式的优化。
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
在这里，我们正在为阿克曼函数的所有值构造一个matrix。 结果，随后的acks调用将不会重新计算任何东西（即再次评估acks !! 4 !! 1 不会使运行时间加倍）。
虽然这不是最快的解决scheme，但它看起来很像天真的实现，它在内存使用方面非常高效，并且以Haskell的怪异特性之一（懒惰）作为强项。
我没有看到这是一个错误， ghc没有利用它知道4和1是函数唯一被调用的唯一参数 – 也就是说， ，它不会作弊。 它也不会为你做常数运算，所以如果你写了main = print $ ack (2+2) 1 ，直到运行时才会计算出2 + 2 = 4。 ghc有更重要的事情需要考虑。 帮助后者的困难是可用的，如果你关心它http://hackage.haskell.org/package/const-math-ghc-plugin 。
所以如果你做一个小math， ghc是有帮助的，例如，这至less比你的C程序快4倍和1倍。 但是用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 mn = ack (m-1) (ack m (n-1) )
这将在十分之一秒内给出正确的答案，所有〜20,000位数字，而海湾合作委员会，与您的algorithm，将永远拿出错误的答案。
在Haskell中以与C中编写方式相似的方式编写algorithm与algorithm不同，因为recursion的语义是相当不同的。
这是一个使用相同mathalgorithm的版本，但是我们使用数据types象征性地表示对Ackermann函数的调用。 这样，我们可以更精确地控制recursion的语义。
当使用优化进行编译时，这个版本运行在不断的内存中，但是速度很慢 – 在类似于你的环境下大约4.5分钟。 但我相信它可以修改得更快。 这只是为了给出这个想法。
data Ack = Ack !Int ack :: Int -> Int -> Int ack mn = 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
这个性能问题（显然除了GHC RTS bug）似乎在Apple XCode更新到4.6.2之后，现在在OS X 10.8上得到了修复。 我仍然可以在Linux上复制它（我已经使用GHC LLVM后端进行了testing），但在OS X上没有更多。在将XCode更新到4.6.2之后，新版本似乎影响了GHC后端代码生成阿克曼实质上（从我看到的对象转储记得更新前）。 在XCode更新之前，我能够在Mac上重现性能问题 – 我没有这些数字，但是确实相当糟糕。 所以，XCode更新似乎改进了Ackermann的GHC代码生成。
现在，C和GHC版本都非常接近。 C代码：
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)); }
执行确认的时间（4,1）：
GCC 4.8.0: 2.94s Clang 4.1: 4s
哈斯克尔代码：
ack :: Int -> Int -> Int ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack mn = ack (m-1) (ack m (n-1))
执行确认的时间4 1（带+ RTS -kc1M）：
GHC 7.6.1 Native: 3.191s GHC 7.6.1 LLVM: 3.8s
所有编译与-O2标志（和-rtsopts旗为GHC RTS错误解决方法）。 尽pipe如此，这还是一个令人头疼的问题。 更新XCode似乎与GHC中的Ackermann的优化有很大的不同。
