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
的推荐方式是什么?
发布于 2012-07-02 19:49:05
像往常一样,看看核心。
快速(1.563秒)-
-- 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.013秒)
-- 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
}
}
}
}
在fast版本中,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)
将成本降低到1/3
$ 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)
发布于 2012-07-03 07:09:49
另一个错过的优化:除以一个常量(Log10)应该替换为乘以倒数。
https://stackoverflow.com/questions/11290929
复制相似问题