Dlaczego "logBase 10 x" wolniej niż "log x/log 10", nawet gdy jest wyspecjalizowany?

Question

solrize w # haskell zadał pytanie dotyczące jednej wersji tego kodu i próbowałem innych przypadków i zastanawiałem się, co się dzieje. Na moim komputerze "szybki" kod zajmuje ~ 1 sekundę, a "wolny" kod ~ 1.3-1.5 (wszystko jest skompilowane z 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] 

I'd've nadzieję, że GHC byłby w stanie włączyć logBase x y się dokładnie tak samo jak log y/log x, gdy wyspecjalizowane. Co się tutaj dzieje i jaki byłby zalecany sposób używania logBase?

Answer 1

Jak zwykle spójrz na Rdzeń.

Szybki (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 
    } 
    } 
    } 

Powolny (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 
    } 
    } 
    } 
    } 

W szybkiej wersji log10 jest obliczana raz dzielone (statyczny argumentem jest stosowany tylko raz). W powolnej wersji jest przeliczana za każdym razem.

Możesz śledzić tę linię rozumowania, aby produkować coraz lepsze wersje:

-- 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] 

i korzystając fuzję tablicy, można usunąć karę stylu kompozytorskiego:

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) 

cięcia kosztów przez 3x

$ time ./A 
6.5657059080059275e7 

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

Co jest tak dobre, jak pisanie ręczne. Poniższe nie oferuje żadnych korzyści w stosunku do poprawnie napisanej wersji powyżej.

Answer 2

Kolejna pominięta optymalizacja: dzielenie przez stałą (log 10) należy zastąpić pomnożeniem przez odwrotność.