Why would eta expansion degrade the performance of fib?

Question

I read this article which says that the eta expansion would degrade performance of fib, like code below, the fib1 would be much faster than other implementations. It explains that in the slower versions, the fib' would be redefined for every argument x. But I don't really get it. Could anyone give a more detailed explanation?

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)

I tested the code above.

Compiled with ghc --make fib.hs, fib1 is much faster than the others. Compile with ghc -O2 fib.hs, fib1 and fib2 are of the same performance, while fib3 and fib4 are much slower.

It seems that with -O2 flag, fib2 is further optimized, so I tested with ghc --make fib.hs -ddump-simpl to see what is going on, and the generated code for the two functions are below

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 }

after read the code that ghc -make -ddump-simpl fib.hs generated, I write two new function to test it. Now compiled with ghc --make fib.hs, fib5 is still much faster than fib6, I think these two functions would make it easier to analyze.

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

Looking at the linked article, it seems that it's the difference between

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

verses

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

As you can see, in the first version fibs' is a global constant that never changes, and you're just indexing into that. In the second version, fibs is a function that constructs a "new", different fibs' for every value of x. And that's the performance difference.