Haskell 中 rank-2 多态性的令人费解的 performance/output 行为

Question

下面的代码（注释与位置内联）给出了我遇到的令人费解的行为的最小示例。

从本质上讲，为什么 (2) 会导致糟糕的 space/time 性能，而 (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" 三次，如我所料。

b。将 (2) 和 (3) 注释掉，编译时不带 -O2，代码输出 "hello" 八次。它似乎每一步输出一个额外的 "hello" 。 我不明白为什么会这样。

c。加上 (1) 和 (4) 的注释，编译时没有 -O2，代码运行非常快。

d。在 (2) 和 (4) 中注释，在没有 -O2 的情况下编译，代码运行非常慢，性能报告（包含在下面）显示对 vstate 进行了更多调用并且比变体 c 使用更多的内存。 我也不明白为什么会这样。

e。在 (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

这里有一些 notes/guesses/questions 为什么会这样：

性能下降与 "hello" 计数增加有什么关系？病理版本似乎每增加一步就多输出一个 "hello"。为什么？
我知道 Haskell 中的多态性很慢，详见 this Whosebug question。这可能是问题的一部分，因为当 vstate 单态化为 vstate :: Float 时，病态行为消失了。但我不明白为什么缺少 let-binding，如位置 (2)，会导致如此糟糕的 time/space 性能。
这是较大代码库中性能错误的最小版本，我们使用 realToFrac 通过 "monomorphizing" 浮点型数字修复了它（提交是 here 以防万一很好奇）。我知道用 -O2 编译修复了最小示例中的行为，但我在较大的代码库中尝试过它并没有修复性能问题。（我们在较大的代码库中需要 rank-2 多态性的原因是使用 ad 库进行 autodiff。）是否有比使用 realToFrac 更有原则的修复方法，例如可以应用的内联特化？

Answer 1

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，它只是一个数值，由返回的闭包捕获。是的，vs `seq` f 是一个函数，因为它有一个函数类型 forall a . (Fractional a) => a，并且它被 GHC 脱糖为一个实际的 lambda 表达式。这个 lambda 抽象了两个参数，捕获 vs 作为自由变量，并将两个参数传递给 f.

因此，每个 step 创建一个捕获 vs :: Double 的新函数闭包。如果我们调用 step 三次，我们会得到三个闭包，其中包含三个 Double，每个闭包都引用前一个闭包。然后，当我们写 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)

这在步数中有 exponential 次调用，因为 step f 调用 f 两次，没有优化就没有计算共享，因为这两个调用都发生在 lambda 下。在 (trace "hello" f) `seq` f 中，对 f 的第一次调用默认为 Fractional Double，第二次调用只是像以前一样传递隐式 Fractional a 实例。

如果我们打开优化，GHC 观察到第一个 f 调用不依赖于函数参数，然后将 trace "hello" f 浮动到 let 绑定，结果几乎相同代码与快速版本一样。

Haskell 中 rank-2 多态性的令人费解的 performance/output 行为

Puzzling performance/output behavior with rank-2 polymorphism in Haskell

performance

haskell

polymorphism

rank-n-types