Tại sao `logBase 10 x` chậm hơn` log x/log 10`, ngay cả khi chuyên biệt?

Question

solrize trong #haskell đã hỏi một câu hỏi về một phiên bản của mã này và tôi đã thử một số trường hợp khác và đã tự hỏi điều gì đang diễn ra. Trên máy của tôi, mã "nhanh" mất ~ 1 giây và mã "chậm" mất ~ 1.3-1.5 (mọi thứ được biên dịch với 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 hy vọng rằng GHC sẽ có thể biến logBase x y vào chính xác những điều tương tự như log y/log x, khi chuyên. Điều gì đang xảy ra ở đây và cách nào được khuyến nghị sử dụng logBase?

Answer 1

Như mọi khi, hãy nhìn vào Lõi.

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

chậm (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 
    } 
    } 
    } 
    } 

Trong phiên bản nhanh, log10 được tính một lần và chia sẻ (tham số tĩnh được áp dụng một lần duy nhất). Trong phiên bản chậm, nó được tính toán lại mỗi lần.

Bạn có thể làm theo dòng này của lập luận để tạo ra phiên bản tốt hơn:

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

Và, sử dụng mảng fusion, bạn có thể loại bỏ các hình phạt của phong cách sáng tác:

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) 

cắt chi phí by 3x

$ time ./A 
6.5657059080059275e7 

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

Điều nào cũng tốt bằng cách viết bằng tay. Bên dưới không cung cấp lợi ích nào so với phiên bản được viết chính xác ở trên.

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

Một tối ưu hóa bị bỏ lỡ khác: chia cho hằng số (log 10) phải được thay thế bằng cách nhân với nghịch đảo.