Почему `logBase 10 x` медленнее, чем` log x/log 10`, даже если он специализирован?

solrize в #haskell задал вопрос об одной версии этого кода, и я попробовал некоторые другие случаи и задавался вопросом, что происходит. На моей машине "быстрый" код занимает ~ 1 секунду, а "медленный" код занимает ~ 1.3-1.5 (все скомпилировано с помощью 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]

Я надеялся, что GHC сможет превратить logBase x y точно так же, как log y / log x, когда будет специализировано. Что здесь происходит, и какой будет рекомендуемый способ использования logBase?

Ответы

Ответ 1

Как всегда, посмотрите на Core.

Быстрый (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
    }
    }
    }

Медленный (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
    }
    }
    }
    }

В быстрой версии log10 вычисляется один раз и делится (статический аргумент применяется только один раз). В медленной версии он пересчитывается каждый раз.

Вы можете следовать этой линии рассуждений, чтобы создать еще лучшие версии:

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

И, используя слияние массива, вы можете удалить штраф за композиционный стиль:

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)

Сокращение стоимости на 3x

$ time ./A
6.5657059080059275e7

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

Это так же хорошо, как писать вручную. Нижеследующее не дает преимуществ над правильно написанной версией выше.

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)

Ответ 2

Другая пропущенная оптимизация: деление на константу (log 10) следует заменить умножением на обратную.