Ackermann très inefficace avec Haskell/GHC

Question

J'essaie l'informatique Ackermann(4,1) et il y a une grande différence de performance entre les différents langages/compilateurs. Voici les résultats obtenus sur mon Core i7 3820QM, 16G, Ubuntu 12.10 64bit ,

C : 1.6s , gcc -O3 (avec 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 (avec 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))

Standard ML : 5.1s mlton -codegen c -cc-opt -O3 (avec 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));

Raquette : 11.5s racket (avec 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 : inachevé tué par le système après 22s ghc -O2 (avec ghc 7.4.2)

Haskell : 1.8s ajhc (avec 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))

La version Haskell est la seule qui ne se termine pas correctement parce qu'elle prend trop de mémoire. Elle gèle ma machine et remplit l'espace de swap avant de se faire tuer. Que puis-je faire pour l'améliorer sans fuglifier lourdement le code ?

EDIT : J'apprécie certaines des solutions asymptotiquement plus intelligentes, mais elles ne sont pas exactement ce que je demande. Il s'agit plus de voir si le compilateur traite certains motifs de manière raisonnablement efficace (pile, appels de queue, unboxing, etc.) que de calculer la fonction d'ackermann.

EDIT 2 : Comme l'ont souligné plusieurs réponses, il semble que ce soit un bogue dans les versions récentes de GHC . J'essaie le même code avec AJHC et obtenir de bien meilleures performances.

Merci beaucoup :)

Answer 1

NB : Le problème de l'utilisation élevée de la mémoire est un bogue dans le RTS de GHC Dans le cas d'un débordement de pile et de l'allocation de nouvelles piles sur le tas, il n'était pas vérifié si la collecte des déchets était prévue. Ce problème a déjà été corrigé dans GHC HEAD.

---

J'ai pu obtenir de bien meilleures performances en convertissant les 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)

Votre fonction originale consomme toute la mémoire disponible sur ma machine, alors que celle-ci fonctionne en espace constant.

$ time ./Test
65533
./Test  52,47s user 0,50s system 96% cpu 54,797 total

Cependant, Ocaml est toujours plus rapide :

$ time ./test
65533./test  7,97s user 0,05s system 94% cpu 8,475 total

Edit : Lorsqu'il est compilé avec JHC votre programme original est à peu près aussi rapide que la version Ocaml :

$ time ./hs.out 
65533
./hs.out  5,31s user 0,03s system 96% cpu 5,515 total

Edit 2 : Autre chose que j'ai découvert : l'exécution de votre programme original avec une taille plus grande des morceaux de pile ( +RTS -kc1M ) le fait fonctionner dans un espace constant. La version CPS est tout de même un peu plus rapide.

Edit 3 : J'ai réussi à produire une version qui tourne presque aussi vite que la version Ocaml en déroulant manuellement la boucle principale. Cependant, elle ne fonctionne que lorsqu'elle est exécutée avec +RTS -kc1M (Dan Doel a déposé un bug sur ce comportement) :

{-# 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

Test :

$ time ./Test +RTS -kc1M
65533
./Test +RTS -kc1M  6,30s user 0,04s system 97% cpu 6,516 total

Edit 4 : Apparemment, la fuite spatiale est fixé dans GHC HEAD donc +RTS -kc1M ne sera pas nécessaire à l'avenir.

Answer 2

Il semble qu'il y ait une sorte de bug. Quelle version de GHC utilisez-vous ?

Avec GHC 7, j'obtiens le même comportement que vous. Le programme consomme toute la mémoire disponible sans produire aucune sortie.

Cependant, si je le compile avec GHC 6.12.1 juste avec ghc --make -O2 Ack.hs il fonctionne parfaitement. Il calcule le résultat dans 10.8s sur mon ordinateur, alors que la version C simple prend 7.8s .

Je vous suggère de signaler ce bogue sur le site web de GHC .

Answer 3

Cette version utilise certaines propriétés de la fonction d'ackermann. Elle n'est pas équivalente aux autres versions, mais elle est rapide :

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 : Et voici une version avec mémorisation, on voit qu'il est facile de mémoriser une fonction en haskell, le seul changement est dans le site d'appel :

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

Ce qui suit est une version idiomatique qui tire avantage de la paresse de Haskell et de l'optimisation par GHC des expressions constantes de haut niveau.

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

Ici, nous construisons paresseusement une matrice pour tous les valeurs de la fonction d'Ackermann. Par conséquent, les appels ultérieurs à acks ne recalculera rien (c'est-à-dire qu'en évaluant acks !! 4 !! 1 encore une fois pas double de la durée de fonctionnement).

Bien que cette solution ne soit pas la plus rapide, elle ressemble beaucoup à l'implémentation naïve, elle est très efficace en termes d'utilisation de la mémoire, et elle présente l'une des caractéristiques les plus étranges de Haskell (la paresse) comme une force.

Answer 5

Je ne vois pas du tout en quoi il s'agit d'un bug, ghc ne tire pas avantage du fait qu'elle sait que 4 et 1 sont les seuls arguments avec lesquels la fonction sera appelée - c'est-à-dire, pour être franc, qu'elle ne triche pas. Il ne fait pas non plus de calculs constants pour vous, donc si vous aviez écrit main = print $ ack (2+2) 1 il n'aurait pas calculé que 2+2 = 4 jusqu'au moment de l'exécution. Le site ghc a des choses bien plus importantes à penser. Une aide pour cette dernière difficulté est disponible si vous vous en occupez http://hackage.haskell.org/package/const-math-ghc-plugin .

Alors ghc est aidé si vous faites un peu de calcul, par exemple, c'est au moins cent fois plus rapide que votre programme C avec 4 et 1 comme arguments. Mais essayez-le avec 4 et 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) )

Cela donnera à l droite réponse, tous les ~20 000 chiffres, en moins d'un dixième de seconde, alors que le gcc, avec votre algorithme, prendra une éternité pour donner la mauvaise réponse.