为什么eta扩展会降低fib的性能？

Question

我读到这篇文章说eta扩展会降低性能fib,就像下面的代码一样,它fib1会比其他实现快得多.它解释了在较慢的版本中,fib'将为每个参数x重新定义.但我真的不明白.谁能提供更详细的解释？

import System.Environment
import Control.Monad

main = do
    (mode:num:_) <- liftM (map read) getArgs
    case mode of
      1 -> print $ fib1 num
      2 -> print $ fib2 num
      3 -> print $ fib3 num
      4 -> print $ fib4 num

fib1 :: Int->Integer
fib1 = (map fib' [0..] !!)
  where fib' 0 = 1
        fib' 1 = 1
        fib' n = fib1 (n-1) + fib1 (n-2)
fib2 :: Int->Integer
fib2 x = map fib' [0..] !! x
  where fib' 0 = 1
        fib' 1 = 1
        fib' n = fib2 (n-1) + fib2 (n-2)
fib3 :: Int->Integer
fib3 = (map fib' [0..] !!)
  where fib' 0 = 1
        fib' 1 = 1
        fib' n = fib' (n-1) + fib' (n-2)
fib4 :: Int->Integer
fib4 x = map fib' [0..] !! x
  where fib' 0 = 1
        fib' 1 = 1
        fib' n = fib' (n-1) + fib' (n-2)

我测试了上面的代码.

编译ghc --make fib.hs,fib1比其他人快得多.与编译ghc -O2 fib.hs,fib1并fib2有相同的性能,而fib3与fib4慢得多.

似乎带有-O2标志,fib2进一步优化,所以我测试了ghc --make fib.hs -ddump-simpl看看发生了什么,并且生成的代码在下面是两个函数

Rec {
fib1 [Occ=LoopBreaker] :: Int -> Integer
[GblId, Str=DmdType]
fib1 =
  !!
    @ Integer
    (map
       @ Int
       @ Integer
       (\ (ds_d10B :: Int) ->
          case ds_d10B of wild_X6 { GHC.Types.I# ds1_d10C ->
          case ds1_d10C of _ [Occ=Dead] {
            __DEFAULT ->
              + @ Integer
                GHC.Num.$fNumInteger
                (fib1 (- @ Int GHC.Num.$fNumInt wild_X6 (GHC.Types.I# 1)))
                (fib1 (- @ Int GHC.Num.$fNumInt wild_X6 (GHC.Types.I# 2)));
            0 -> __integer 1;
            1 -> __integer 1
          }
          })
       (enumFrom @ Int GHC.Enum.$fEnumInt (GHC.Types.I# 0)))
end Rec }

Rec {
fib2 [Occ=LoopBreaker] :: Int -> Integer
[GblId, Arity=1, Str=DmdType]
fib2 =
  \ (x_ay6 :: Int) ->
    !!
      @ Integer
      (map
         @ Int
         @ Integer
         (\ (ds_d10x :: Int) ->
            case ds_d10x of wild_X8 { GHC.Types.I# ds1_d10y ->
            case ds1_d10y of _ [Occ=Dead] {
              __DEFAULT ->
                + @ Integer
                  GHC.Num.$fNumInteger
                  (fib2 (- @ Int GHC.Num.$fNumInt wild_X8 (GHC.Types.I# 1)))
                  (fib2 (- @ Int GHC.Num.$fNumInt wild_X8 (GHC.Types.I# 2)));
              0 -> __integer 1;
              1 -> __integer 1
            }
            })
         (enumFrom @ Int GHC.Enum.$fEnumInt (GHC.Types.I# 0)))
      x_ay6
end Rec }

在读完ghc -make -ddump-simpl fib.hs生成的代码后,我编写了两个新函数来测试它.现在编译ghc --make fib.hs,fib5仍然快得多fib6,我认为这两个函数会使分析更容易.

fib5 :: Int->Integer
fib5 = (!!) 
        (map (\n->
                case n of 
                  0 -> 1
                  1 -> 1
                  _ -> fib5 (n-1) + fib5 (n-2))
             [0..])
fib6 :: Int->Integer
fib6 = \x->
        (!!) (map (\n->
                case n of 
                  0 -> 1
                  1 -> 1
                  _ -> fib6 (n-1) + fib6 (n-2))
              [0..]) 
             x

Answer 1

看看链接的文章,似乎是它们之间的区别

fibs = let fibs' = ... in (\ x -> map fibs [0..] !! x)

经文

fibs = \ x -> let fibs' = ... in map fibs [0..] !! x

正如您所看到的,在第一个版本中fibs'是一个永远不会改变的全局常量,而您只是将其编入索引.在第二个版本中,fibs是一个构造"new"的函数,fibs'对于每个值都是不同的x.这就是性能差异.