代码之家  ›  专栏  ›  技术社区  ›  kye

Haskell中秩2多态性的令人费解的性能/输出行为

  •  7
  • kye  · 技术社区  · 6 年前

    下面的代码(带位置注释的内联代码)给出了一个我正在经历的令人费解的行为的最小示例。

    本质上,为什么(2)会导致糟糕的空间/时间性能,而(1)不会?

    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"
    

    a、 注释(1)和(3),编译时不带 -O2 ,代码只输出“hello”三次,正如我所期望的那样。

    b、 注释(2)和(3),编译时不带 ,代码输出“hello”八次。它似乎每一步输出一个额外的“hello”。

    c、 注释(1)和(4),编译时不带 -氧气

    d、 注释(2)和(4),编译时不带 ,代码运行得非常慢,性能报告(包括在下面)显示了对 vstate 使用的内存比变种要多得多 c 我也不明白为什么会这样。

    e、 注释(2)和(4),编译 -氧气 ,代码的行为与variant相同 . 所以很明显,ghc能够优化任何在变异中发生的病理行为 d .

    这是variant的分析报告 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 
    

    这是variant的分析报告 -氧气 ):

        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
    

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

    • 我知道Haskell中的多态性是缓慢的,如 this StackOverflow question . 这可能是问题的一部分,因为当 是单形态的 vstate :: Float . 但我不明白为什么缺少let绑定(如位置(2))会导致如此糟糕的时间/空间性能。
    • 这是较大代码基中性能缺陷的最小版本,我们通过使用 realToFrac (承诺是 here 以防有人好奇)。我知道用 修复了最小示例中的行为,但我在较大的代码库中进行了尝试,但没有修复性能问题。(我们需要在较大的代码基中使用rank-2多态性的原因是 ad autodiff的库。)是否有比使用 ,例如可以应用的内联专门化?
    1 回复  |  直到 6 年前
        1
  •  4
  •   András Kovács    6 年前

    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 给a。(小数a)=>a f .

    所以,每个人 创建一个新的函数闭包,它捕获 vs::双精度 . 如果我们打电话 三次,我们得到三个闭包和三个 在里面,每个闭包都引用上一个闭包。然后,当我们写 vstate (step $ step $ step initState) ,我们再次默认为 双倍 Fractional Double 实例。所有的 -es调用前面的闭包 ,但是 只计算一次,因为它们通常很懒 不重新计算的值。

    但是,如果我们能够 NoMonomorphismRestriction , 一般化为 forall a. Fractional a => a

    现在,慢点 :

    step :: State -> State
    step (State f) = State ((trace "hello" f) `seq` f)
    

    指数 在步骤数中调用的次数,因为 step f 电话 两次,如果没有优化,则不会共享计算,因为这两个调用都发生在lambda下。在 (trace "hello" f) `seq` f ,第一个呼叫 f型 默认为 分数倍 ,而第二个调用只是通过隐式 像以前一样。

    如果我们打开优化,GHC会发现 调用不依赖于函数参数,并浮起 trace "hello" f 到let绑定,生成的代码与快速版本中的代码几乎相同。

    推荐文章