Ackermann très inefficace avec Haskell / GHC

J’essaie de calculer Ackermann(4,1) et il y a une grande différence de performance entre les différents langages / compilateurs. Voici les résultats 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 mn = ack (m-1) (ack m (n-1)); print (Int.toSsortingng (ack 4 1)); 

Raquette: racket 11.5s (avec raquette 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)) 

Haskell: inachevé , tué par le système après 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 mn = ack (m-1) (ack m (n-1)) 

La version Haskell est la seule à ne pas se terminer correctement car elle prend trop de mémoire. Il gèle ma machine et remplit l’espace d’échange avant d’être tué. Que puis-je faire pour l’améliorer sans trop figer 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 gère certains modèles de manière raisonnablement efficace (stack, appels de fin, désencapsulation, etc.) que de calculer la fonction ackermann.

EDIT 2 : Comme le soulignent plusieurs réponses, cela semble être un bug dans les versions récentes de GHC . J’essaie le même code avec AJHC et obtient de bien meilleures performances.

Merci beaucoup 🙂

NB: Le problème d’utilisation de mémoire élevée est un bogue dans le RTS GHC , où lors du débordement de stack et de l’allocation de nouvelles stacks sur le tas, il n’a pas été vérifié si la récupération de place était due. Il a déjà été corrigé dans GHC HEAD.


J’ai été en mesure d’obtenir de bien meilleures performances grâce à la conversion CPS:

 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) 

Votre fonction d’origine consum toute la mémoire disponible sur ma machine, alors que celle-ci s’exécute dans un espace constant.

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

Ocaml est encore plus rapide, cependant:

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

Edit: Lorsque 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: J’ai découvert quelque chose d’autre: exécuter votre programme d’origine avec une plus grande taille de bloc de stack ( +RTS -kc1M ) le fait fonctionner dans un espace constant. La version CPS est encore un peu plus rapide.

Edit 3: J’ai réussi à produire une version presque aussi rapide que celle d’Ocaml en déroulant manuellement la boucle principale. Cependant, il ne fonctionne que s’il est exécuté avec +RTS -kc1M (Dan Doel a déposé un bogue concernant 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 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 

Essai:

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

Edit 4 : Apparemment, la fuite d’espace est corrigée dans GHC HEAD , donc +RTS -kc1M ne sera plus nécessaire dans le futur.

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

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

Cependant, si je le comstack avec GHC 6.12.1 avec ghc --make -O2 Ack.hs , cela fonctionne parfaitement. Il calcule le résultat en 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 du GHC .

Cette version utilise des propriétés de la fonction ackermann. Ce n’est pas équivalent aux autres versions, mais c’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 mn = ackermann (m - 1) (ackermann m (n - 1)) 

Edit: Et ceci est une version avec mémo, on voit qu’il est facile de mémoriser une fonction dans haskell, le seul changement est sur 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 mn = ackermann (m - 1) (ackermann m (n - 1)) main :: IO () main = print $ memoize2 ackermann 4 2 

Ce qui suit est une version idiomatique qui tire parti de la paresse de Haskell et de l’optimisation des expressions de haut niveau constantes par 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 

Ici, nous construisons paresseusement une masortingce pour toutes les valeurs de la fonction Ackermann. Par conséquent, les appels ultérieurs aux acks ne recalculeront rien (c.-à-d. acks !! 4 !! 1 évaluation des acks !! 4 !! 1 ne doublera pas le temps d'exécution).

Bien que ce ne soit pas la solution 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 redonne un avantage à l'une des fonctionnalités les plus étranges de Haskell (la paresse).

Je ne vois pas que ce soit un bogue, ghc ne profite pas du fait qu’il sait que 4 et 1 sont les seuls arguments avec lesquels la fonction sera appelée – c’est-à-dire , il ne sortingche pas. Il ne fait pas non plus de calculs constants pour vous, donc si vous aviez écrit main = print $ ack (2+2) 1 , cela n’aurait pas calculé que 2 + 2 = 4 jusqu’à l’exécution. La ghc a des choses beaucoup plus importantes à penser. L’aide pour cette dernière difficulté est disponible si vous vous en souciez http://hackage.haskell.org/package/const-math-ghc-plugin .

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

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

L’écriture de l’algorithme dans Haskell d’une manière qui ressemble à celle que vous avez écrite en C n’est pas le même, car la sémantique de la récursivité est très différente.

Voici une version utilisant le même algorithme mathématique , mais où nous représentons symboliquement les appels à la fonction Ackermann en utilisant un type de données. De cette façon, nous pouvons contrôler plus précisément la sémantique de la récursivité.

Lorsqu’elle est compilée avec l’optimisation, cette version s’exécute en mémoire constante, mais elle est lente – environ 4,5 minutes dans un environnement similaire au vôtre. Mais je suis sûr que cela pourrait être modifié pour être beaucoup plus rapide. C’est juste pour donner l’idée.

 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 

Ce problème de performance (à l’exception du bogue RHC GHC) semble être résolu maintenant sous OS X 10.8 après la mise à jour d’Apple XCode à la version 4.6.2 . Je peux toujours le reproduire sur Linux (j’ai testé avec le backend GHC LLVM), mais plus sur OS X. Après avoir mis à jour le XCode vers 4.6.2, la nouvelle version semble avoir affecté la génération de code backend GHC pour Ackermann substantiellement (d’après ce que je me souviens de regarder pré-mise à jour des vidages d’object). J’ai été en mesure de reproduire le problème de performance sur Mac avant la mise à jour XCode – je n’ai pas les chiffres mais ils étaient sûrement très mauvais. Il semble donc que la mise à jour de XCode ait amélioré la génération de code GHC pour Ackermann.

Maintenant, les versions C et GHC sont assez proches. Code 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)); } 

Temps pour exécuter ack (4,1):

 GCC 4.8.0: 2.94s Clang 4.1: 4s 

Code Haskell:

 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)) 

Temps pour exécuter ack 4 1 (avec + RTS -kc1M):

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

Tous ont été compilés avec l’indicateur -O2 (et l’ -rtsopts pour GHC pour la solution de bogue de RTS). C’est tout à fait un scratcher en tête. La mise à jour de XCode semble avoir fait une grande différence avec l’optimisation d’Ackermann en GHC.