kye*_*kye 7 polymorphism performance haskell rank-n-types
下面的代码(带有位置的内联注释)给出了我遇到的令人费解的行为的最小例子.
基本上,为什么(2)导致可怕的空间/时间性能,而(1)不是？
下面的代码在ghc版本8.4.3上编译并运行如下:
ghc -prof -fprof-auto -rtsopts test.hs; ./test +RTS -p
{-# LANGUAGE Rank2Types #-}
import Debug.Trace
-- Not sure how to get rid of the record
data State = State {
-- (0) If vstate :: Float, the extra "hello"s go away
vstate :: forall a . (Fractional a) => a
}
step :: State -> State
step s =
-- (1) one "hello" per step
-- let vs = trace "hello" (vstate s) in
-- s { vstate = vs `seq` vstate s }
-- (2) increasing "hello"s per step
s { vstate = (trace "hello" (vstate s)) `seq` vstate s }
main :: IO ()
main = do
let initState = State { vstate = 0 }
-- (3) step 3 times
-- let res = step $ step $ step initState
-- print $ vstate res
-- (4) step 20 times to profile time/space performance
let res = iterate step initState
print $ vstate $ last $ take 20 res
print "done"
一个.用(1)和(3)注释,编译没有-O2,代码只输出"hello"三次,正如我所期望的那样.
湾 用(2)和(3)注释,编译没有-O2,代码输出"hello"八次.它似乎每步输出一个额外的"你好".我不明白为什么会这样.
C.随着(1)和(4)的注释,编译没有-O2,代码运行速度非常快.
d.随着(2)和(4)的注释,编译没有-O2,代码运行非常缓慢,性能报告(包括在下面)显示,vstate与变体相比,它可以进行更多的调用并使用更多的内存c.我也不明白为什么会这样.
即 使用(2)和(4)注释,编译时 -O2,代码的行为与变体相同c.很明显,ghc能够优化变体中发生的任何病理行为d.
以下是变体c(快速)的分析报告:
Mon Aug 13 15:48 2018 Time and Allocation Profiling Report (Final)
partial +RTS -p -RTS
total time = 0.00 secs (0 ticks @ 1000 us, 1 processor)
total alloc = 107,560 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
CAF GHC.IO.Handle.FD <entire-module> 0.0 32.3
CAF GHC.IO.Encoding <entire-module> 0.0 3.1
main Main partial.hs:(24,1)-(35,16) 0.0 13.4
main.res Main partial.hs:32:9-36 0.0 1.6
step Main partial.hs:(15,1)-(18,36) 0.0 1.1
step.vs Main partial.hs:17:9-37 0.0 46.1
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 114 0 0.0 0.6 0.0 100.0
CAF Main <entire-module> 227 0 0.0 0.1 0.0 52.2
main Main partial.hs:(24,1)-(35,16) 228 1 0.0 2.7 0.0 52.1
vstate Main partial.hs:11:5-10 230 20 0.0 0.0 0.0 0.0
main.initState Main partial.hs:25:9-40 239 0 0.0 0.0 0.0 0.0
main.res Main partial.hs:32:9-36 234 0 0.0 0.0 0.0 0.0
step Main partial.hs:(15,1)-(18,36) 235 0 0.0 0.0 0.0 0.0
main.initState Main partial.hs:25:9-40 233 1 0.0 0.0 0.0 0.0
main.res Main partial.hs:32:9-36 231 1 0.0 1.6 0.0 49.4
step Main partial.hs:(15,1)-(18,36) 232 19 0.0 1.1 0.0 47.8
step.vs Main partial.hs:17:9-37 236 19 0.0 46.1 0.0 46.7
vstate Main partial.hs:11:5-10 237 190 0.0 0.0 0.0 0.6
main.initState Main partial.hs:25:9-40 238 0 0.0 0.6 0.0 0.6
CAF Debug.Trace <entire-module> 217 0 0.0 0.2 0.0 0.2
CAF GHC.Conc.Signal <entire-module> 206 0 0.0 0.6 0.0 0.6
CAF GHC.IO.Encoding <entire-module> 189 0 0.0 3.1 0.0 3.1
CAF GHC.IO.Encoding.Iconv <entire-module> 187 0 0.0 0.2 0.0 0.2
CAF GHC.IO.Handle.FD <entire-module> 178 0 0.0 32.3 0.0 32.3
CAF GHC.IO.Handle.Text <entire-module> 176 0 0.0 0.1 0.0 0.1
main Main partial.hs:(24,1)-(35,16) 229 0 0.0 10.7 0.0 10.7
以下是变体的分析报告d(慢;没有-O2):
Mon Aug 13 15:25 2018 Time and Allocation Profiling Report (Final)
partial +RTS -p -RTS
total time = 1.48 secs (1480 ticks @ 1000 us, 1 processor)
total alloc = 1,384,174,472 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
step Main partial.hs:(15,1)-(21,60) 95.7 98.8
main.initState Main partial.hs:25:9-40 3.0 1.2
vstate Main partial.hs:11:5-10 1.4 0.0
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 114 0 0.0 0.0 100.0 100.0
CAF Main <entire-module> 227 0 0.0 0.0 100.0 100.0
main Main partial.hs:(24,1)-(35,16) 228 1 0.0 0.0 100.0 100.0
vstate Main partial.hs:11:5-10 230 1048575 1.4 0.0 100.0 100.0
main.initState Main partial.hs:25:9-40 236 0 3.0 1.2 3.0 1.2
main.res Main partial.hs:32:9-36 234 0 0.0 0.0 95.7 98.8
step Main partial.hs:(15,1)-(21,60) 235 0 95.7 98.8 95.7 98.8
main.initState Main partial.hs:25:9-40 233 1 0.0 0.0 0.0 0.0
main.res Main partial.hs:32:9-36 231 1 0.0 0.0 0.0 0.0
step Main partial.hs:(15,1)-(21,60) 232 19 0.0 0.0 0.0 0.0
CAF Debug.Trace <entire-module> 217 0 0.0 0.0 0.0 0.0
CAF GHC.Conc.Signal <entire-module> 206 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding <entire-module> 189 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv <entire-module> 187 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD <entire-module> 178 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.Text <entire-module> 176 0 0.0 0.0 0.0 0.0
main Main partial.hs:(24,1)-(35,16) 229 0 0.0 0.0 0.0 0.0
以下是关于为什么会发生这种情况的一些注意/猜测/问题:
vstate被单形化时会消失vstate :: Float.但我不明白为什么缺少let-binding,如在位置(2),会导致如此糟糕的时间/空间性能.realToFrac(提交在这里以防万一有人好奇).我知道编译-O2修复了最小示例中的行为,但是我在更大的代码库中尝试了它并且它不能解决性能问题.(我们在更大的代码库中需要rank-2多态性的原因是将ad库用于autodiff.)是否存在比使用更原则的修复realToFrac,例如可以应用的内联特化？forall a . (Fractional a) => a是一个函数类型。
它有两个参数，一个类型(a :: *)和一个类型为 的实例Fractional a。每当你看到 时=>，它在操作上都是一个函数，并编译为 GHC 核心表示中的函数，有时也保留为机器代码中的函数。->和之间的主要区别=>在于，后者的参数不能由程序员显式给出，并且它们总是由实例解析隐式填充。
我们step先来看看快速：
step :: State -> State
step (State f) =
let vs = trace "hello" f
in State (vs `seq` f)
这里，vs有一个未确定的Fractional类型，默认为Double。如果您打开-Wtype-defaults警告，GHC 会向您指出这一点。因为，它只是一个数值，由返回的闭包vs :: Double捕获。是的，是一个函数，因为它有一个函数类型，并且它被 GHC 脱糖为一个实际的 lambda 表达式。该 lambda 抽象了两个参数，捕获为自由变量，并将这两个参数传递给.vs `seq` fforall a . (Fractional a) => avsf
因此，每个都会step创建一个新的函数闭包来捕获vs :: Double. 如果我们调用step三次，我们会得到三个闭包，Double其中包含三个 s，每个闭包都引用前一个闭包。然后，当我们编写 时vstate (step $ step $ step initState)，我们再次默认为Double，并且 GHC 使用实例调用此闭包Fractional Double。所有vs-es 都使用 调用先前的闭包Fractional Double，但每个vs仅计算一次，因为它们是Double不会重新计算的常规惰性值。
然而，如果我们启用NoMonomorphismRestriction,vs则被泛化为forall a. Fractional a => a，因此它也成为一个函数，并且它的调用不再被记忆。因此，在这种情况下，快速版本的行为与慢速版本相同。
现在，慢step：
step :: State -> State
step (State f) = State ((trace "hello" f) `seq` f)
这在步骤数中具有指数step f数量的调用，因为调用f两次，并且在没有优化的情况下，不会共享计算，因为这两次调用都发生在 lambda 下。在 中(trace "hello" f) `seq` f，第一次调用f默认为Fractional Double，第二次调用只是像以前一样传递隐式Fractional a实例。
如果我们打开优化，GHC 会观察到第一次f调用不依赖于函数参数，并浮出trace "hello" f到 let 绑定，从而产生与快速版本中几乎相同的代码。