50

我尝试计算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 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))

Haskell：未完成，22 秒后被系统杀死ghc -O2 （使用 ghc 7.4.2）

Haskell： ajhc 1.8 秒（使用 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 版本是唯一无法正确终止的版本，因为它占用了太多内存。它会冻结我的机器并在被杀死之前填充交换空间。在不严重修改代码的情况下，我能做些什么来改进它？

编辑：我很欣赏一些渐近更智能的解决方案，但它们并不是我所要求的。这更多是关于查看编译器是否以相当有效的方式（堆栈、尾调用、拆箱等）处理某些模式，而不是计算 ackermann 函数。

编辑 2：正如一些回复所指出的，这似乎是GHC 最新版本中的一个错误。我用AJHC尝试相同的代码并获得更好的性能。

非常感谢你 ：）

4

7 回答 7

37

注意：高内存使用问题是 GHC RTS 中的一个错误，在堆栈溢出和在堆上分配新堆栈时，没有检查垃圾收集是否到期。它已经在 GHC HEAD 中修复。

我能够通过 CPS-converting 获得更好的性能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（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 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将来不再需要。

于 2013-04-20T03:00:28.107 回答
13

似乎涉及某种错误。您使用的是什么 GHC 版本？

使用 GHC 7，我得到与您相同的行为。该程序消耗所有可用内存而不产生任何输出。

但是，如果我只用 GHC 6.12.1 编译它ghc --make -O2 Ack.hs，它就可以完美运行。它在我的计算机上以10.8s计算结果，而纯 C 版本需要7.8s。

我建议您在 GHC 网站上报告此错误。

于 2013-04-20T16:36:10.450 回答
7

这个版本使用了 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 m n = ackermann (m - 1) (ackermann m (n - 1))

编辑：这是一个带有 memoization 的版本，我们看到在 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
于 2013-04-20T10:01:11.357 回答
5

下面是一个惯用的版本，它利用了 Haskell 的惰性和 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

在这里，我们懒惰地为Ackermann 函数的所有值构建一个矩阵。因此，后续调用acks不会重新计算任何东西（即acks !! 4 !! 1再次评估不会使运行时间加倍）。

虽然这不是最快的解决方案，但它看起来很像幼稚的实现，它在内存使用方面非常有效，并且将 Haskell 的一个怪异特性（懒惰）重新塑造为一种优势。

于 2013-04-20T03:10:43.823 回答
4

我根本不认为这是一个错误，ghc只是没有利用它知道 4 和 1 是函数将被调用的唯一参数这一事实——也就是说，坦率地说，它不会作弊。它也不会为你做恒定的数学运算，所以如果你写了main = print $ ack (2+2) 1，它不会计算出 2+2 = 4 直到运行时。有ghc更重要的事情要考虑。如果你关心它，可以为后一种困难提供帮助http://hackage.haskell.org/package/const-math-ghc-plugin。

如果你ghc做一些数学运算会有所帮助，例如，这至少比你的 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 m n = ack (m-1) (ack m (n-1) )

这将在不到十分之一秒的时间内给出所有约 20,000 位数字的正确答案，而 gcc 和您的算法将永远给出错误答案。

于 2013-04-20T21:04:01.967 回答
4

用 Haskell 编写算法的方式看起来与用 C 编写的方式相似，这不是同一种算法，因为递归的语义完全不同。

这是一个使用相同数学算法的版本，但我们使用数据类型象征性地表示对 Ackermann 函数的调用。这样，我们可以更精确地控制递归的语义。

使用优化编译时，此版本在恒定内存中运行，但速度很慢 - 在类似于您的环境中大约需要 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
于 2013-04-23T18:09:41.127 回答
3

这个性能问题（显然除了 GHC RTS 错误）似乎在 AppleXCode更新到4.6.2. 我仍然可以在 Linux 上重现它（虽然我一直在使用 GHC LLVM 后端进行测试），但在 OS X 上就不行了。在我将 XCode 更新到 4.6.2 后，新版本似乎影响了 GHC 后端代码生成Ackermann 实质上（根据我在更新前查看对象转储的记忆）。在 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));

}

执行 ack(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 m n = ack (m-1) (ack m (n-1))

执行 ack 4 1 的时间（使用 +RTS -kc1M）：

GHC 7.6.1 Native: 3.191s
GHC 7.6.1 LLVM: 3.8s

所有都是用标志编译的-O2（以及-rtsopts用于 RTS 错误解决方法的 GHC 标志）。不过，这真是令人头疼。更新 XCode 似乎对 GHC 中的 Ackermann 优化产生了很大的影响。

于 2013-04-27T03:05:32.410 回答