Haskell的斐波那契序列的性能取決於方法

Question

我嘗試了不同的方法，以斐波那契序列的給定索引處得到一個號碼，他們基本上可以分爲兩大類：

• 建立一個列表和查詢的索引
• 使用變量（可能是單獨的或tupled未經列表）

我挑選兩個的一個示例：

fibs1 :: Int -> Integer 
fibs1 n = fibs1' !! n 
    where fibs1' = 0 : scanl (+) 1 fibs1' 

fib2 :: Int -> Integer 
fib2 n = fib2' 1 1 n where 
    fib2' _ b 2 = b 
    fib2' a b n = fib2' b (a + b) (n - 1) 

fibs1：

real 0m2.356s 
user 0m2.310s 
sys  0m0.030s 

fibs2：

real 0m0.671s 
user 0m0.667s 
sys  0m0.000s 

兩者都使用64位GHC 7.6.1和-O2 -fllvm編譯。他們的核心轉儲在長度上非常相似，但是他們在不太熟悉解釋的部分有所不同。

我並不感到驚訝，fibs1失敗n = 350000（Stack space overflow）。但是，我對使用這麼多內存的事實感到不舒服。

我想清楚一些事情：

1. 爲什麼GC未照顧到列表的開頭的整個計算，即使大部分很快就會變得沒用？
2. 爲什麼GHC不會將列表版本優化爲變量版本，因爲其中只有兩個元素是同時需要的？

編輯：對不起，我混合速度結果，固定。雖然我的三個疑問中的兩個仍然有效）。

Answer 1

爲什麼在整個計算過程中GC沒有照顧到列表的開始，儘管它大部分很快變得無用了？

fibs1使用了大量的內存，是緩慢的，因爲scanl是懶惰的，它不評估列表元素，所以

fibs1' = 0 : scanl (+) 1 fibs1' 

產生

0 : scanl (+) 1 (0 : more) 
0 : 1 : let f2 = 1+0 in scanl (+) f2 (1 : more') 
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in scanl (+) f3 (f2 : more'') 
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in f3 : let f4 = f3+f2 in scanl (+) f4 (f3 : more''') 

等，所以你寧願迅速獲得巨大的嵌套thunk。當評估該thunk時，它會被推入堆棧，並且在250000到350000之間的某個點，對於默認堆棧而言，它變得太大。

而且由於每個列表元素在未評估時都保留對前一個元素的引用，因此列表的開頭不能被垃圾收集。

如果使用的是嚴格的掃描，

fibs1 :: Int -> Integer 
fibs1 n = fibs1' !! n 
    where 
    fibs1' = 0 : scanl' (+) 1 fibs1' 
    scanl' f a (x:xs) = let x' = f a x in x' `seq` (a : scanl' f x' xs) 
    scanl' _ a [] = [a] 

時產生的k個列表單元格，它的價值已經被評估，所以不參考以前，因此列表可以被垃圾收集（假設沒有其他人持有對它的引用），因爲它是遍歷的。

在該實現中，列表版本與fib2一樣快（儘管如此，它仍然需要分配列表單元，所以它分配更多一點點，因此速度可能稍慢一點，但差別很小，因爲斐波納契數字變得如此之大以至於列表結構開銷變得微不足道）。

scanl的想法是，它的結果是逐步消耗的，以便消耗強制元素並防止大的thunk的建立。

爲什麼GHC不會將列表版本優化爲變量版本，因爲其中只有兩個元素是同時需要的？

它的優化器無法通過算法看出來確定。 scanl對編譯器是不透明的，它不知道scanl是做什麼的。

如果我們採取scanl（重命名，或從前奏隱藏scanl，我選擇重命名）的確切的源代碼，

scans     :: (b -> a -> b) -> b -> [a] -> [b] 
scans f q ls   = q : (case ls of 
           [] -> [] 
           x:xs -> scans f (f q x) xs) 

和編譯模塊出​​口它（與-O2），然後查看生成的接口文件與

ghc --show-iface Scan.hi 

我們得到（例如，編譯器版本之間的細微差別）

Magic: Wanted 33214052, 
     got 33214052 
Version: Wanted [7, 0, 6, 1], 
     got [7, 0, 6, 1] 
Way: Wanted [], 
    got [] 
interface main:Scan 7061 
    interface hash: ef57dac14815e2f1f897b42a007c0c81 
    ABI hash: 8cfc8dab79de6a51fcad666f1869574f 
    export-list hash: 57d6805e5f0b5f76f0dd8dfb228df988 
    orphan hash: 693e9af84d3dfcc71e640e005bdc5e2e 
    flag hash: 1e8135cb44ef6dd330f1f56943d1f463 
    used TH splices: False 
    where 
exports: 
    Scan.scans 
module dependencies: 
package dependencies: base* ghc-prim integer-gmp 
orphans: base:GHC.Base base:GHC.Float base:GHC.Real 
family instance modules: 
import -/ base:Prelude 1cb4b618cf45281dc97748b1831bf0cd 
d79ca4e223c0de0a770a3b88a5e67687 
    scans :: forall b a. (b -> a -> b) -> b -> [a] -> [b] 
    {- Arity: 3, HasNoCafRefs, Strictness: LLL -} 
vectorised variables: 
vectorised tycons: 
vectorised reused tycons: 
scalar variables: 
scalar tycons: 
trusted: safe-inferred 
require own pkg trusted: False 

並且看到接口文件沒有公開函數的展開，只顯示了它的類型，元數，嚴格性以及它沒有引用CAF。

當編譯一個導入模塊的文件時，編譯器所要做的就是接口文件公開的信息。

在這裏，沒有暴露的信息可以讓編譯器做任何事情，只是發出一個調用函數。

如果展開展開，編譯器有機會內聯展開並分析知道類型和組合函數的代碼，以生成更多不會構建thunk的積極代碼。

但是，scanl的語義是最大限度的懶惰，輸出的每個元素都是在檢查輸入列表之前發出的。這造成的後果是，如果列表中包含的任何未定義值GHC不能做出另外嚴格，因爲這將改變這一結果：

scanl (+) 1 [undefined] = 1 : scanl (+) (1 + undefined) [] = 1 : (1 + undefined) : [] 

而

scanl' (+) 1 [undefined] = let x' = 1 + undefined in x' `seq` 1 : scanl' (+) x' [] 
         = *** Exception: Prelude.undefined 

人們可以做出變型

scanl'' f b (x:xs) = b `seq` b : scanl'' f (f b x) xs 

這將產生1 : *** Exception: Prelude.undefined爲上述輸入，但任何嚴格將確實會改變結果，如果列表包含未定義的值，所以即使編譯器知道展開，它不能使評估嚴格 - 除非它能證明列表中沒有未定義的值，這對我們來說顯而易見，而不是編譯器[我認爲它不會是容易教一個編譯器認識到並能夠證明缺少未定義的值]。