為什麼這幾種fib函數的性能差異如此之大？

01-13

在Let vs. Where 這篇文章里看到，下面幾種fib函數實現的性能差異巨大。
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)
上面的解釋是， fib2中，會對每個x重新定義一次fib"，從而破壞memorization。但是看的不是很理解。
親自測試，如果ghc --make fib.hs，測試fib 30，則第一種實現比其他三種快幾十倍，ghc -O2 fib.hs，前兩種實現速度相同，比三四種實現快幾十倍。

關於這個問題的一些討論：
[Haskell-cafe] Eta-expansion destroys memoization?

原問題裡面給的 2010 年 Haskell Cafe 郵件組的討論已經解釋清楚了。這個程序里各函數實際執行的效率不同，和寫法，和優化相關。原 fib1 即便沒有優化執行效率也高，是因為 GHC 對 section 語法的實現沒有嚴格按照 Haskell Report 來做（其中定義 (e op) = x -&> e op x）。嚴格來做的話 fib1 和 fib2 應該完全一樣。

另外，改變 fib2 效率的優化叫做 full laziness，用 ghc -O2 -fno-full-laziness 編譯，fib2 就還是效率很差。這種優化簡單講就是把函數體當中的 free expression 盡量提到外層去而不改變語義：

let f x = e in ... (f u) ... (f v) ... ====&> let y = e1 in let f x = e2 in ... (f u) ... (f v) ...

其中在 e2 裡面會用到 y。這裡 e1 的計算和 x 是無關的，所以在 f u 和 f v 的計算中可以共享同一個 e1 的值。值得注意的是，full laziness 優化同時改變了時間和空間效率，因為 e1 的值必須在計算 f u 和 f v 之間一直留駐內存。這是以空間換時間的典型例子，因該視具體情況選擇性使用。

更新：

我又仔細看了一下 eta expansion 在這裡面的作用，把 fib1 改成

fib1 = (!!) (map fib" [0..]) where fib" = ...

試過之後，效率和原 fib1 一樣（我之前做的試驗有誤）。編譯時如果不做任何優化，那麼 fib1 本身並非是一個函數，依據 WHNF (weak head normal form) 的要求對它先進行求值（以下用 let 表示求值環境）：

fib1 = (!!) (map fib" [0..]) where fib" = ... = let fib" = ... l = map fib" [0..] in (!!) l

這時候需要將 (!!) 的定義代入（來自 Haskell Report）：

(!!) :: [a] -&> Int -&> a xs !! n | n &< 0 = error "Prelude.!!: negative index" [] !! _ = error "Prelude.!!: index too large" (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)

簡單寫就是：

(!!) xs n = if n &< 0 then ... else case xs of {[] -&> ...; ...}

將 (!!) 的定義代入 fib1 可以得到它的 WHNF：

fib1 = let fib" = ... l = map fib" [0..] in -&> if n &< 0 then ... else case l of {[] -&> ...; ...}

我們可以比較一下 fib2（因為已經是 WHNF 了，所以以下化簡純粹是為了有個對照）：

fib2 = x -&> (!!) (map fib" [0..]) x where fib" = ... = x -&> let fib" = ... l = map fib" [0..] in (!!) l x = x -&> let fib" = ... l = map fib" [0..] in if x &< 0 then ... else case l of {[] -&> ...; ...}

這時候可以看出兩者的差別就在於 fib" 和 l 的定義是在 x -&> .. 閉包內，還是在外。而 full laziness 優化所做的就是將 fib2 轉換成 fib1 的形式。

Haskell並不是緩存所有函數的結果。

惰性求值的「緩存」只是對按名調用的改進。

Desuger之後

(map fib" [0..] !!) -&> (!!) (map fib" [0..])

map fib" [0..] !! x -&> x -&> (!!) (map fib" [0..]) x

第一個，map fib" [0..]這個Expression是Const Applactive Form，會被Lift到Top Level，後面的多次調用共享這個列表。從而實現了「緩存」

第二個的Expression在Lambda Expression裡面，每次Lambda調用產生新的實例。開-O2優化之後可能也可以「提取」出來，所以和第一個差不多快

用trace試一下，fib1每個fib n都只算了1次，考慮到!!是 $O(n)$ 的，所以應該是 $O(n^2)$ 。，而fib2則不然（有重複計算）。

第三、四個版本和下面的是等價的，為 $O(2^n)$ ，map fib" [0..]幾乎不起作用。

fib :: Int -&> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

對了，談性能的時候不考慮編譯選項嗎？

1和2的寫法，在不開編譯優化的時候有不一樣，但是開了 -O後是一樣的。

（還是看TRACE）

$ ghc fib.hs [1 of 1] Compiling Main ( fib.hs, fib.o ) Linking fib ... $ ./fib 1 4 4 3 2 1 0 5 $ ./fib 2 4 4 3 2 1 0 1 2 1 0 5 $ ghc -O fib.hs [1 of 1] Compiling Main ( fib.hs, fib.o ) Linking fib ... $ ./fib 1 4 0 2 1 4 3 5 $ ./fib 2 4 0 2 1 4 3 5

可以看到在開啟O優化後，2和1在執行上已經一樣了，說明這兩個寫法「根本」上是等效的，只是差別比較深，需要優化。

但是我更感興趣的是求值順序也不同了，這個倒是很意外。

另外3和4的寫法在O下也有改變，好像把0和1兩個常數部分給記住了。