optimization - suma - ¿Por qué `logBase 10 x` es más lento que` log x/log 10`, incluso cuando está especializado?

propiedades del logaritmo y exponencial

Question

solrize en #haskell hizo una pregunta sobre una versión de este código y probé otros casos y me preguntaba qué estaba pasando. En mi máquina, el código "rápido" toma ~ 1 segundo y el código "lento" toma ~ 1.3-1.5 (todo está compilado con ghc -O2 ).

import Data.List

log10 :: Double -> Double
--log10 x = log x / log 10 -- fast
--log10 = logBase 10 -- slow
--log10 = barLogBase 10 -- fast
--log10 = bazLogBase 10 -- fast
log10 = fooLogBase 10 -- see below

class Foo a where
    fooLogBase :: a -> a -> a

instance Foo Double where
    --fooLogBase x y = log y / log x -- slow
    fooLogBase x = let lx = log x in /y -> log y / lx -- fast


barLogBase :: Double -> Double -> Double
barLogBase x y = log y / log x

bazLogBase :: Double -> Double -> Double
bazLogBase x = let lx = log x in /y -> log y / lx


main :: IO ()
main = print . foldl'' (+) 0 . map log10 $ [1..1e7]

Esperaba que GHC pudiera convertir logBase xy en exactamente lo mismo que log y / log x , cuando logBase xy especializado. ¿Qué está pasando aquí y cuál sería la forma recomendada de usar logBase ?

Answer 1

Como siempre, mira el Núcleo.

Rápido (1.563s) -

-- note: top level constant, referred to by specialized fooLogBase

Main.main_lx :: GHC.Types.Double
Main.main_lx =
     case GHC.Prim.logDouble# 10.0 of { r ->
     GHC.Types.D# r
  }

Main.main7 :: GHC.Types.Double -> GHC.Types.Double
Main.main7 =
  / (y :: GHC.Types.Double) ->
    case y of _ { GHC.Types.D# y# ->
    case GHC.Prim.logDouble# y# of { r0 ->
    case Main.main_lx of { GHC.Types.D# r ->
    case GHC.Prim./## r0 r of { r1 ->
    GHC.Types.D# r1
    }
    }
    }

Lento (2.013s)

-- simpler, but recomputes log10 each time
Main.main7 =
  / (y_ahD :: GHC.Types.Double) ->
    case y_ahD of _ { GHC.Types.D# x_aCD ->
    case GHC.Prim.logDouble# x_aCD of wild1_aCF { __DEFAULT ->
    case GHC.Prim.logDouble# 10.0 of wild2_XD9 { __DEFAULT ->
    case GHC.Prim./## wild1_aCF wild2_XD9 of wild3_aCz { __DEFAULT ->
    GHC.Types.D# wild3_aCz
    }
    }
    }
    }

En la versión rápida, log10 se calcula una vez y se comparte (el argumento estático se aplica solo una vez). En la versión lenta se vuelve a calcular cada vez.

Puedes seguir esta línea de razonamiento para producir versiones aún mejores:

-- 1.30s
lx :: Double
lx = log 10

log10 :: Double -> Double
log10 y = log y / lx

main :: IO ()
main = print . foldl'' (+) 0 . map log10 $ [1..1e7]

Y, mediante la fusión de matrices, puede eliminar la penalización del estilo de composición:

import qualified Data.Vector.Unboxed as V

lx :: Double
lx = log 10

log10 :: Double -> Double
log10 y = log y / lx

main :: IO ()
main = print . V.sum . V.map log10 $ V.enumFromN 1 (10^7)

Reduciendo el costo en 3x

$ time ./A
6.5657059080059275e7

real    0m0.672s
user    0m0.000s
sys     0m0.000s

Que es tan bueno como escribirlo a mano. Lo siguiente no ofrece ningún beneficio sobre la versión escrita correctamente arriba.

lx :: Double
lx = D# (GHC.Prim.logDouble# 10.0##)

log10 :: Double -> Double
log10 (D# y) = D# (case logDouble# y of r -> r /## d#)
    where
        D# d# = lx

main :: IO ()
main = print . V.sum . V.map log10 $ V.enumFromN 1 (10^7)

Answer 2

Otra optimización perdida: la división por una constante (log 10) debe reemplazarse con la multiplicación por el recíproco.