Why does eta extension degrade fiber performance?
I read this article , which says that the eta extension will degrade performance fib
, as the code below fib1
will be much faster than other implementations. He explains that in slower versions the parameter fib'
will be overridden for every x argument. But I do not understand. Can anyone provide 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 have checked the code above.
Compiled with ghc --make fib.hs
, fib1
much faster than others. Compiling with ghc -O2 fib.hs
, fib1
and fib2
has the same performance as fib3
and is fib4
much slower.
It looks like it is -O2
fib2
optimizing with the flag , so I checked with ghc --make fib.hs -ddump-simpl
to see what is going on, and the generated code for the two functions is 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 reading the generated code, ghc -make -ddump-simpl fib.hs
I write two new functions to test it. Now compiled with ghc --make fib.hs
, fib5
it is still much faster than fib6
I think these two functions will make the analysis easier.
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
source to share
After looking at the linked article, it seems like the difference between
fibs = let fibs' = ... in (\ x -> map fibs [0..] !! x)
poems
fibs = \ x -> let fibs' = ... in map fibs [0..] !! x
As you can see, the first version fibs'
has a global constant that never changes and you just index it. In the second version fibs
, it is a function that builds a "new" one, another fibs'
for each value x
. And what's the difference in performance.
source to share