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.