Аккерманн очень неэффективен с 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 (с окамлом 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,5 с 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: незавершенный, убитый системой после 22s ghc -O2 (с ghc 7.4.2)

Haskell: 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 является единственной, которая не может завершиться должным образом, потому что она занимает слишком много памяти. Он замерзает мою машину и заполняет пространство подкачки перед тем, как его убили. Что я могу сделать, чтобы улучшить его без серьезного исправления кода?

EDIT. Я ценю некоторые из асимптотически умных решений, но они не совсем то, о чем я прошу. Это больше похоже на то, обрабатывает ли компилятор определенные шаблоны достаточно эффективным способом (стек, хвостовые вызовы, распаковка и т.д.), Чем вычисление функции ackermann.

EDIT 2. Как было отмечено несколькими ответами, это выглядит как ошибка в последних версиях GHC. Я пробую тот же код с AJHC и получаю гораздо лучшую производительность.

Большое спасибо:)

Ответы

Ответ 1

NB: Проблема с высокой памятью является ошибкой в RHG GHC, где при переполнении и распределении стека новых стеков на куче не было проверено, требуется ли сбор мусора. Он уже зафиксирован в 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 (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 не будет в будущем.

Ответ 2

Кажется, что есть какая-то ошибка. Какую версию GHC вы используете?

С GHC 7 я получаю то же поведение, что и вы. Программа потребляет всю доступную память, не производя никакого выхода.

Однако, если я скомпилирую его с GHC 6.12.1 только с ghc --make -O2 Ack.hs, он отлично работает. Он вычисляет результат в 10.8s на моем компьютере, а версия с открытым кодом - 7.8s.

Я предлагаю вам сообщить об этой ошибке на веб-сайте GHC.

Ответ 3

В этой версии используются некоторые свойства функции 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))

Edit: И это версия с memoization, мы видим, что легко memoize функции в 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 m n = ackermann (m - 1) (ackermann m (n - 1))

main :: IO ()
main = print $ memoize2 ackermann 4 2

Ответ 4

Ниже приведена идиоматическая версия, в которой используется лазильность 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

Здесь мы лениво строим матрицу для всех значений функции Аккермана. В результате последующие вызовы acks не будут компрометировать что-либо (т.е. Оценка acks !! 4 !! 1 снова не удвоит время выполнения).

Хотя это не самое быстрое решение, он очень похож на наивную реализацию, он очень эффективен с точки зрения использования памяти, и он перерабатывает одну из мощных функций Haskell (ленивость) в качестве силы.

Ответ 5

Я не вижу, что это ошибка вообще, 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, с вашим алгоритмом, навсегда вернется, чтобы дать неправильный ответ.

Ответ 6

Написание алгоритма в 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 [email protected](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

Ответ 7

Эта проблема производительности (за исключением ошибки GHC RTS, очевидно), по-видимому, теперь исправлена в OS X 10.8 после обновления Apple XCode до 4.6.2. Я все еще могу воспроизвести его в Linux (я тестировал с помощью GHC LLVM backend, хотя), но не больше в OS X. После того, как я обновил XCode до 4.6.2, новая версия, похоже, повлияла на генерацию кода GHC для Аккерманн существенно (из того, что я помню, глядя на предварительное обновление дампов объекта). Я смог воспроизвести проблему производительности на Mac до обновления XCode - у меня нет номеров, но они были совершенно плохи. Таким образом, похоже, что обновление XCode улучшило генерацию кода GHC для Ackermann.

Теперь версии 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

Код Haskell:

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 для GHC для обхода ошибки RTS). Впрочем, это довольно голова. Обновление XCode, похоже, сильно повлияло на оптимизацию Ackermann в GHC.