7

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

本质上，为什么 (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与 variant 相比，调用次数和使用的内存更多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

以下是关于为什么会发生这种情况的一些注释/猜测/问题：

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

1 回答 1

4

forall a . (Fractional a) => a是一个函数类型。

它有两个参数，一个 type(a :: *)和一个 type 的实例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. 如果我们调用step3 次，我们会得到三个闭包，Double里面有 3 个 s，每个闭包都指向前一个。然后，当我们编写 时vstate (step $ step $ step initState)，我们再次默认为Double，GHC 用Fractional Double实例调用这个闭包。所有的vs-es 都用 调用先前的闭包Fractional Double，但 everyvs只评估一次，因为它们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-binding，从而产生与快速版本中几乎相同的代码。

于 2018-08-13T21:53:37.953 回答