Почему расширение eta ухудшает производительность fib?

Question

Я читал this article, в котором говорится, что eta expansion ухудшит производительность 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 - это функция, которая строит «новый», другой fibs' для каждого значения x. И это разница в производительности.