benchmarksgame benchmark alioth performance haskell ghc

performance - benchmark - Haskell: reevaluaciones innecesarias de expresiones constantes.



benchmarksgame alioth debian (2)

Voy a demostrar el problema usando el siguiente programa de ejemplo.

{-# LANGUAGE BangPatterns #-} data Point = Point !Double !Double fmod :: Double -> Double -> Double fmod a b | a < 0 = b - fmod (abs a) b | otherwise = if a < b then a else let q = a / b in b * (q - fromIntegral (floor q :: Int)) standardMap :: Double -> Point -> Point standardMap k (Point q p) = Point (fmod (q + p) (2 * pi)) (fmod (p + k * sin(q)) (2 * pi)) iterate'' gen !p = p : (iterate'' gen $ gen p) main = putStrLn . show . (/(Point a b) -> a + b) . head . drop 100000000 . iterate'' (standardMap k) $ (Point 0.15 0.25) where k = (cos (pi/3)) - (sin (pi/3))

Aquí standardMap k es la función parametrizada y k=(cos (pi/3))-(sin (pi/3)) es un parámetro. Si compilo este programa con ghc -O3 -fllvm el tiempo de ejecución en mi máquina es de aproximadamente 42s , sin embargo, si escribo k en la forma 0.5 - (sin (pi/3)) el tiempo de ejecución es 21s y si escribo k = 0.5 - 0.5 * (sqrt 3) tomará solo 12s .

La conclusión es que k se reevalúa en cada llamada de standardMap k .

¿Por qué esto no está optimizado?

PS compiler ghc 7.6.3 en archlinux

EDITAR

Para aquellos que están preocupados por las propiedades extrañas de standardMap aquí hay un ejemplo más simple e intuitivo, que presenta el mismo problema.

{-# LANGUAGE BangPatterns #-} data Point = Point !Double !Double rotate :: Double -> Point -> Point rotate k (Point q p) = Point ((cos k) * q - (sin k) * p) ((sin k) * q + (cos k) * p) iterate'' gen !p = p : (iterate'' gen $ gen p) main = putStrLn . show . (/(Point a b) -> a + b) . head . drop 100000000 . iterate'' (rotate k) $ (Point 0.15 0.25) where --k = (cos (pi/3)) - (sin (pi/3)) k = 0.5 - 0.5 * (sqrt 3)

EDITAR

Antes de hacer la pregunta, he tratado de hacer k estricto, de la misma manera que Don sugirió, pero con ghc -O3 no vi una diferencia. La solución con rigor funciona si el programa se compila con ghc -O2 . Me perdí eso porque no probé todas las combinaciones posibles de banderas con todas las versiones posibles del programa.

Entonces, ¿cuál es la diferencia entre -O2 y -O2 que afecta a estos casos?

¿Debería preferir -O2 en general?

EDITAR

Como observaron Mike Hartl y otros, si rotate k se cambia a rotate $ k o standardMap k a standardMap $ k , el rendimiento mejora, aunque no es el mejor (la solución de Don). ¿Por qué?

Como siempre, comprueba el núcleo.

Con ghc -O2, k está en línea en el cuerpo del bucle, que se despliega como una función de nivel superior:

Main.main7 :: Main.Point -> Main.Point Main.main7 = / (ds_dAa :: Main.Point) -> case ds_dAa of _ { Main.Point q_alG p_alH -> case q_alG of _ { GHC.Types.D# x_s1bt -> case p_alH of _ { GHC.Types.D# y_s1bw -> case Main.$wfmod (GHC.Prim.+## x_s1bt y_s1bw) 6.283185307179586 of ww_s1bi { __DEFAULT -> case Main.$wfmod (GHC.Prim.+## y_s1bw (GHC.Prim.*## (GHC.Prim.-## (GHC.Prim.cosDouble# 1.0471975511965976) (GHC.Prim.sinDouble# 1.0471975511965976)) (GHC.Prim.sinDouble# x_s1bt))) 6.283185307179586 of ww1_X1bZ { __DEFAULT -> Main.Point (GHC.Types.D# ww_s1bi) (GHC.Types.D# ww1_X1bZ)

Indica que las llamadas de sin y cos no se evalúan en tiempo de compilación. El resultado es que ocurrirá un poco más de matemáticas:

$ time ./A 3.1430515093368085 real 0m15.590s

Si lo haces estricto, al menos no se vuelve a calcular cada vez:

main = putStrLn . show . (/(Point a b) -> a + b) . head . drop 100000000 . iterate'' (standardMap k) $ (Point 0.15 0.25) where k :: Double !k = (cos (pi/3)) - (sin (pi/3))

Resultando en:

ipv_sEq = GHC.Prim.-## (GHC.Prim.cosDouble# 1.0471975511965976) (GHC.Prim.sinDouble# 1.0471975511965976) } in

Y un tiempo de ejecución de:

$ time ./A 6.283185307179588 real 0m7.859s

Lo que creo que es lo suficientemente bueno por ahora. También añadiría pragmas de desempaquetar al tipo de Punto.

Si desea razonar sobre el rendimiento numérico bajo diferentes arreglos de código, debe inspeccionar el Core.

Usando su ejemplo revisado. Sufre el mismo problema. k está en línea rotate . GHC piensa que es realmente barato, cuando en este punto de referencia es más caro.

Ingeniosamente, ghc-7.2.3 -O2

$ time ./A 0.1470480616244365 real 0m22.897s

Y se evalúa k cada vez que se llama rotar.

Hacer k estricto: una forma de forzarlo a no ser compartido.

$ time ./A 0.14704806100839019 real 0m2.360s

Usando pragmas UNPACK en el constructor de Point:

$ time ./A 0.14704806100839019 real 0m1.860s

No creo que sea una evaluación repetida.

Primero, cambié a la notación "do" y utilicé un "let" en la definición de "k" que pensé que debería ayudar. No, sigue siendo lento.

Luego agregué una llamada de rastreo, solo siendo evaluada una vez. Incluso comprobó que la variante rápida estaba, de hecho, produciendo un doble.

Luego imprimí ambas variaciones. Hay una pequeña diferencia en los valores iniciales.

Ajustar el valor de la variante "lenta" hace que sea la misma velocidad. No tengo idea de para qué sirve su algoritmo: ¿sería muy sensible a los valores iniciales?

import Debug.Trace (trace) ... main = do -- is -0.3660254037844386 let k0 = (0.5 - 0.5 * (sqrt 3))::Double -- was -0.3660254037844385 let k1 = (cos (pi/3)) - (trace "x" (sin (pi/3))) + 0.0000000000000001; putStrLn (show k0) putStrLn (show k1) putStrLn . show . (/(Point a b) -> a + b) . head . drop 100000000 . iterate'' (standardMap k1) $ (Point 0.15 0.25)

EDITAR: esta es la versión con literales numéricos. Está mostrando los tiempos de ejecución de 23sec vs 7sec para mí. Compilé dos versiones separadas del código para asegurarme de que no estaba haciendo algo estúpido como no compilar.

main = do -- -0.3660254037844386 -- -0.3660254037844385 let k2 = -0.3660254037844385 putStrLn . show . (/(Point a b) -> a + b) . head . drop 100000000 . iterate'' (standardMap k2) $ (Point 0.15 0.25)

EDIT2: no sé cómo obtener los códigos de operación de ghc, pero comparar los volcados hexadecimales para los dos archivos .o muestra que difieren en un solo byte, probablemente el literal. Entonces no puede ser el tiempo de ejecución.

EDIT3: Intenté activar el perfilado, y eso me desconcertó aún más. a menos que me falte algo, la única diferencia es una pequeña discrepancia en el número de llamadas a fmod (fmod.q para ser precisos).

El perfil "5" es para la terminación constante "5", igual que "6".

Fri Sep 6 12:37 2013 Time and Allocation Profiling Report (Final) constant-timings-5 +RTS -p -RTS total time = 38.34 secs (38343 ticks @ 1000 us, 1 processor) total alloc = 12,000,105,184 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc standardMap Main 71.0 0.0 iterate'' Main 21.2 93.3 fmod Main 6.3 6.7 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 50 0 0.0 0.0 100.0 100.0 main Main 101 0 0.0 0.0 0.0 0.0 CAF:main1 Main 98 0 0.0 0.0 0.0 0.0 main Main 100 1 0.0 0.0 0.0 0.0 CAF:main2 Main 97 0 0.0 0.0 1.0 0.0 main Main 102 0 1.0 0.0 1.0 0.0 main./ Main 110 1 0.0 0.0 0.0 0.0 CAF:main3 Main 96 0 0.0 0.0 99.0 100.0 main Main 103 0 0.0 0.0 99.0 100.0 iterate'' Main 104 100000001 21.2 93.3 99.0 100.0 standardMap Main 105 100000000 71.0 0.0 77.9 6.7 fmod Main 106 200000001 6.3 6.7 6.9 6.7 fmod.q Main 109 49999750 0.6 0.0 0.6 0.0 CAF:main_k Main 95 0 0.0 0.0 0.0 0.0 main Main 107 0 0.0 0.0 0.0 0.0 main.k2 Main 108 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 93 0 0.0 0.0 0.0 0.0 CAF GHC.Conc.Signal 90 0 0.0 0.0 0.0 0.0 CAF GHC.Float 89 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding 82 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 66 0 0.0 0.0 0.0 0.0 Fri Sep 6 12:38 2013 Time and Allocation Profiling Report (Final) constant-timings-6 +RTS -p -RTS total time = 22.17 secs (22167 ticks @ 1000 us, 1 processor) total alloc = 11,999,947,752 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc standardMap Main 48.4 0.0 iterate'' Main 38.2 93.3 fmod Main 10.9 6.7 main Main 1.4 0.0 fmod.q Main 1.0 0.0 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 50 0 0.0 0.0 100.0 100.0 main Main 101 0 0.0 0.0 0.0 0.0 CAF:main1 Main 98 0 0.0 0.0 0.0 0.0 main Main 100 1 0.0 0.0 0.0 0.0 CAF:main2 Main 97 0 0.0 0.0 1.4 0.0 main Main 102 0 1.4 0.0 1.4 0.0 main./ Main 110 1 0.0 0.0 0.0 0.0 CAF:main3 Main 96 0 0.0 0.0 98.6 100.0 main Main 103 0 0.0 0.0 98.6 100.0 iterate'' Main 104 100000001 38.2 93.3 98.6 100.0 standardMap Main 105 100000000 48.4 0.0 60.4 6.7 fmod Main 106 200000001 10.9 6.7 12.0 6.7 fmod.q Main 109 49989901 1.0 0.0 1.0 0.0 CAF:main_k Main 95 0 0.0 0.0 0.0 0.0 main Main 107 0 0.0 0.0 0.0 0.0 main.k2 Main 108 1 0.0 0.0 0.0 0.0 CAF GHC.IO.Handle.FD 93 0 0.0 0.0 0.0 0.0 CAF GHC.Conc.Signal 90 0 0.0 0.0 0.0 0.0 CAF GHC.Float 89 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding 82 0 0.0 0.0 0.0 0.0 CAF GHC.IO.Encoding.Iconv 66 0 0.0 0.0 0.0 0.0

EDIT4: El enlace a continuación es para los dos volcados de código de operación (gracias a @Tom Ellis). Aunque no puedo leerlos, parecen tener la misma "forma". Presumiblemente las cadenas largas de caracteres aleatorios son identificadores internos. Acabo de compilar ambos con -O2 -fforce-recomp y las diferencias de tiempo son reales. https://gist.github.com/anonymous/6462797