performance - que - ¿Cuánta sobrecarga tienen las llamadas de función en Haskell?

hola mundo en haskell

Question

Soy nuevo en Haskell y estoy sorprendido por el costo de una llamada a la función, que me parece completamente irrazonable, y me hace pensar que estoy haciendo algo fundamentalmente incorrecto.

Considere el siguiente código de Haskell:

module Main where
logistic x = 4.0*x*(1.0-x)

lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)

main = putStrLn $ show $ lg 0.7861 100000000

Compilando esto con el comando

 ghc -O3 -XBangPatterns -o tsths tst.hs

y ejecutándolo, me sale:

real    0m15.904s
user    0m15.853s
sys     0m0.016s

Si en lugar de llamar a la función logistic , calculo la expresión en línea:

module Main where

lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (4.0*x*(1.0-x)) (n-1)

main = putStrLn $ show $ lg 0.7861 100000000

El tiempo de ejecución se convierte en:

real    0m0.838s
user    0m0.828s
sys     0m0.004s

que es exactamente el mismo que el programa de C equivalente, que es

#include <stdio.h>

int main() {
   int i, num=100000000;
   double x=0.7861;
   for (i=0; i<num; ++i)
      x *= 4.0*(1.0-x);
   printf("%lg/n", x);
}

¿Estoy haciendo algo terriblemente mal?

Muchas gracias.

Answer 1

Agregue una firma de tipo a logistic y verá la aceleración. Permítame usar CPP para demostrar la diferencia.

bash> cat tst.hs
module Main where

#if defined(SIG)
logistic :: Double -> Double
#endif
logistic x = 4.0*x*(1.0-x)

lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)

main = putStrLn $ show $ lg 0.7861 100000000


bash> ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.4.1

Si se compila sin SIG definido (se excluye la firma de tipo):

bash> ghc -O3 -XBangPatterns -XCPP -o tsths tst.hs
[1 of 1] Compiling Main             ( tst.hs, tst.o )
Linking tsths ...


bash> time ./tsths
0.34209286442469333

real    0m13.187s
user    0m13.177s
sys 0m0.008s

Ahora compilemos con SIG definido para que se incluya la firma:

bash> rm tsths *.o *.hi


bash> ghc -O3 -XBangPatterns -XCPP -DSIG -o tsths tst.hs
[1 of 1] Compiling Main             ( tst.hs, tst.o )
Linking tsths ...
bash> time ./tsths
0.34209286442469333

real    0m0.464s
user    0m0.440s
sys 0m0.020s

No estoy seguro de por qué GHC no lo optimiza sin la firma; la restricción de monomorfismo debería restringirla a Double -> Double todos modos.

Answer 2

Es un error en GHC-7.4.1. Mirando el núcleo generado (solo el núcleo para la función lg es importante, de GHC-7.4.2, obtenemos

Main.lg3 :: GHC.Types.Double
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Main.lg3 = GHC.Float.$w$cfromRational Main.lg4 Main.lg2

Main.lg1 :: GHC.Types.Double
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Main.lg1 = GHC.Float.$w$cfromRational Main.lg2 Main.lg2

Main.$wlg :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
[GblId,
 Arity=2,
 Str=DmdType LL,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 30] 158 0}]
Main.$wlg =
  / (ww_s1Oy :: GHC.Prim.Double#) (ww1_s1OC :: GHC.Prim.Int#) ->
    case ww1_s1OC of ds_Xvs {
      __DEFAULT ->
        case Main.lg3 of _ { GHC.Types.D# x_awJ ->
        case Main.lg1 of _ { GHC.Types.D# x1_awV ->
        letrec {
          $wlg1_X1PF [Occ=LoopBreaker]
            :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
          [LclId, Arity=2, Str=DmdType LL]
          $wlg1_X1PF =
            / (ww2_X1Pv :: GHC.Prim.Double#) (ww3_X1PA :: GHC.Prim.Int#) ->
              case ww3_X1PA of ds1_Xwr {
                __DEFAULT ->
                  $wlg1_X1PF
                    (GHC.Prim.*##
                       (GHC.Prim.*## x_awJ ww2_X1Pv) (GHC.Prim.-## x1_awV ww2_X1Pv))
                    (GHC.Prim.-# ds1_Xwr 1);
                0 -> ww2_X1Pv
              }; } in
        $wlg1_X1PF
          (GHC.Prim.*##
             (GHC.Prim.*## x_awJ ww_s1Oy) (GHC.Prim.-## x1_awV ww_s1Oy))
          (GHC.Prim.-# ds_Xvs 1)
        }
        };
      0 -> ww_s1Oy
    }

Dos Double nivel superior y un bucle decente.

GHC-7.4.1 fue un poco demasiado alegre, eso produjo

Rec {
Main.$wlg [Occ=LoopBreaker]
  :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
[GblId, Arity=2, Str=DmdType LL]
Main.$wlg =
  / (ww_s1NS :: GHC.Prim.Double#) (ww1_s1NW :: GHC.Prim.Int#) ->
    case ww1_s1NW of ds_Xvb {
      __DEFAULT ->
        case GHC.Float.$wfromRat'''' (-1021) 53 Main.logistic4 Main.logistic2
        of ww2_a1Mt { __DEFAULT ->
        case GHC.Float.$wfromRat'''' (-1021) 53 Main.logistic2 Main.logistic2
        of ww3_X1Nq { __DEFAULT ->
        Main.$wlg
          (GHC.Prim.*##
             (GHC.Prim.*## ww2_a1Mt ww_s1NS) (GHC.Prim.-## ww3_X1Nq ww_s1NS))
          (GHC.Prim.-# ds_Xvb 1)
        }
        };
      0 -> ww_s1NS
    }
end Rec }

y le dio dos llamadas al trabajador fromRational en cada iteración.

Ahora, fromRational es una función bastante complicada. Todavía es bastante lento, a pesar de haber conseguido una implementación mucho más rápida en la serie 7.2, por lo que estas llamadas duelen mucho.

Con una firma de tipo, no se producen constantes Rational de nivel superior, solo constantes Double , y luego se usan, lo que por supuesto no incluye una desaceleración gratuita.

Answer 3

Según lo sugerido por Dan Burton, en realidad se trata de una función polimórfica, porque GHC infiere el tipo logistic :: Fractional a => a -> a . Si especifica el tipo explícitamente, generalmente habilita tanto la mejor comprobación como las mejores optimizaciones. Creo que es una buena práctica especificar explícitamente el tipo de función.

Si desea tener una función de tipo polimórfico pero tiene una velocidad máxima de llamada monomórfica en caso de uso específico, puede utilizar el pragma SPECIALIZE , pero creo que esto es específico de GHC.

{-# LANGUAGE BangPatterns #-}
module Main where
logistic :: Fractional a => a -> a
{-# SPECIALISE logistic :: Double -> Double #-}
logistic x = 4.0*x*(1.0-x)

lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)

main = putStrLn $ show $ lg 0.7861 100000000

También tenga en cuenta que puede especificar el pragma LANGUAGE al principio del archivo para habilitar patrones de bang y no es necesario habilitarlos en la línea de comandos.

Los tiempos en mi máquina fueron 21 segundos para el original, 0,67 seg para el tipo explícito, 0,7 seg para la especialización (que es básicamente el mismo).

Creo que la sobrecarga de llamadas especializadas es muy pequeña porque son solo un montón de instrucciones que se integran de todos modos, pero la función polimórfica resulta en llamadas. Aunque es extraño que el GHC no pueda en línea a pesar del polimorfismo.