performance - pagina - Ackermann muy ineficiente con Haskell/GHC
haskell pagina oficial (7)
Intento calcular Ackermann(4,1) y hay una gran diferencia en el rendimiento entre diferentes lenguajes / compiladores. Debajo están los resultados en mi Core i7 3820QM, 16G, Ubuntu 12.10 64bit ,
C: 1.6s , gcc -O3 (con 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 (con 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))
Estándar ML: 5.1s mlton -codegen c -cc-opt -O3 (con 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));
Raqueta: 11.5s racket (con raqueta 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: inacabado , muerto por sistema después de 22 s ghc -O2 (con ghc 7.4.2)
Haskell: 1.8 ajhc (con 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 versión de Haskell es la única que no finaliza correctamente porque requiere demasiada memoria. Congela mi máquina y llena el espacio de intercambio antes de ser asesinado. ¿Qué puedo hacer para mejorarlo sin exagerar el código?
EDITAR : Aprecio algunas de las soluciones asintóticamente más inteligentes, pero no son exactamente lo que estoy pidiendo. Se trata más bien de ver si el compilador maneja ciertos patrones de una manera razonablemente eficiente (pila, llamadas de cola, unboxing, etc.) que la computación de la función ackermann.
EDIT 2 : Como se señala en varias respuestas, esto parece ser un error en las versiones recientes de GHC . Intento el mismo código con AJHC y obtengo un rendimiento mucho mejor.
Muchas gracias :)
Escribir el algoritmo en Haskell de una manera similar a la forma en que lo escribió en C no es el mismo algoritmo, porque la semántica de la recursión es bastante diferente.
Aquí hay una versión que usa el mismo algoritmo matemático , pero donde representamos llamadas a la función de Ackermann simbólicamente usando un tipo de datos. De esta forma, podemos controlar la semántica de la recursión de manera más precisa.
Cuando se compila con optimización, esta versión se ejecuta en memoria constante, pero es lenta, unos 4,5 minutos en un entorno similar al suyo. Pero estoy seguro de que podría modificarse para ser mucho más rápido. Esto es solo para dar la idea.
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
Esta versión usa algunas propiedades de la función ackermann. No es equivalente a las otras versiones, pero es rápido:
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))
Editar: Y esta es una versión con memoria, vemos que es fácil memorizar una función en haskell, el único cambio está en el sitio de llamadas:
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
Este problema de rendimiento (a excepción del error GHC RTS obviamente) parece estar solucionado ahora en OS X 10.8 después de que Apple XCode actualice a 4.6.2 . Todavía puedo reproducirlo en Linux (he estado probando con el backend de GHC LLVM), pero ya no en OS X. Después de actualizar el XCode a 4.6.2, la nueva versión parece haber afectado la generación de código backend de GHC para Ackermann sustancialmente (por lo que recuerdo al mirar depósitos de objetos previos a la actualización). Pude reproducir el problema de rendimiento en Mac antes de la actualización de XCode. No tengo los números, pero seguramente fueron bastante malos. Por lo tanto, parece que la actualización de XCode mejoró la generación de código GHC para Ackermann.
Ahora, las versiones C y GHC están bastante cerca. Código 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));
}
Hora de ejecutar ack (4,1):
GCC 4.8.0: 2.94s
Clang 4.1: 4s
Código 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))
Hora de ejecutar ack 4 1 (con + RTS -kc1M):
GHC 7.6.1 Native: 3.191s
GHC 7.6.1 LLVM: 3.8s
Todos fueron compilados con -O2 bandera (y -rtsopts bandera para GHC para solución de error RTS). Aunque es bastante un rascador de cabeza. La actualización de XCode parece haber marcado una gran diferencia con la optimización de Ackermann en GHC.
La siguiente es una versión idiomática que aprovecha la lazyness de Haskell y la optimización de GHC de las expresiones constantes de alto nivel.
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
Aquí, estamos construyendo perezosamente una matriz para todos los valores de la función de Ackermann. Como resultado, las llamadas subsiguientes a acks no volverán a calcular nada (es decir, evaluar acks !! 4 !! 1 nuevo no duplicará el tiempo de ejecución).
Aunque esta no es la solución más rápida, se parece mucho a la implementación ingenua, es muy eficiente en términos de uso de la memoria, y reescribe una de las características más extrañas de Haskell (pereza) como una fortaleza.
No veo que esto sea un error en absoluto, ghc simplemente no está aprovechando el hecho de que sabe que 4 y 1 son los únicos argumentos con los que se llamará a la función, es decir, para decirlo sin rodeos , no hace trampa. Tampoco hace matemática constante para usted, así que si hubiera escrito main = print $ ack (2+2) 1 , no habría calculado que 2 + 2 = 4 hasta el tiempo de ejecución. El ghc tiene cosas mucho más importantes en que pensar. La ayuda para la última dificultad está disponible si te interesa http://hackage.haskell.org/package/const-math-ghc-plugin .
Así que se ayuda a ghc si se hace un poco de matemática, por ejemplo, esto es por lo menos un tiempo cazado tan rápido como su programa C con 4 y 1 como argumentos. Pero pruébalo con 4 y 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) )
Esto dará la respuesta correcta , todos ~ 20,000 dígitos, en menos de una décima de segundo, mientras que el gcc, con su algoritmo, demorará una eternidad para dar la respuesta incorrecta.
Parece que hay algún tipo de error involucrado. ¿Qué versión de GHC estás usando?
Con GHC 7, tengo el mismo comportamiento que tú. El programa consume toda la memoria disponible sin producir ningún resultado.
Sin embargo, si lo compilo con GHC 6.12.1 solo con ghc --make -O2 Ack.hs , funciona perfectamente. Calcula el resultado en 10.8s en mi computadora, mientras que la versión C simple toma 7.8s .
Le sugiero que informe este error en el sitio web de GHC .
NB: El problema de uso de memoria alta es un error en el GHC RTS , donde al desbordamiento de la pila y la asignación de nuevas pilas en el montón no se verificaba si la recolección de basura se debe. Ya se ha corregido en GHC HEAD.
Pude obtener un rendimiento mucho mejor con el ack conversión de 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 m n) k = ack (P m (n-1)) (/a -> ack (P (m-1) a) k)
Su función original consume toda la memoria disponible en mi máquina, mientras que esta se ejecuta en un espacio constante.
$ time ./Test
65533
./Test 52,47s user 0,50s system 96% cpu 54,797 total
Ocaml es aún más rápido, sin embargo:
$ time ./test
65533./test 7,97s user 0,05s system 94% cpu 8,475 total
Editar: cuando se compila con JHC , su programa original es tan rápido como la versión de Ocaml:
$ time ./hs.out
65533
./hs.out 5,31s user 0,03s system 96% cpu 5,515 total
Edición 2: Algo más que descubrí: ejecutar tu programa original con un tamaño de pila más grande ( +RTS -kc1M ) lo hace funcionar en un espacio constante. La versión de CPS es aún un poco más rápida.
Edición 3: Logré producir una versión que se ejecuta casi tan rápido como el Ocaml desenrollando manualmente el lazo principal. Sin embargo, solo funciona cuando se ejecuta con +RTS -kc1M (Dan Doel ha presentado un error sobre este comportamiento):
{-# 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
Pruebas:
$ time ./Test +RTS -kc1M
65533
./Test +RTS -kc1M 6,30s user 0,04s system 97% cpu 6,516 total
Editar 4 : Aparentemente, la fuga de espacio se soluciona en GHC HEAD , por lo que +RTS -kc1M no será necesario en el futuro.