什麼編譯器優化技術可以把FP語言里的sum [1..n]的效率優化到C語言的水平？

01-12

影響效率的原因在於，[1..n] 這樣一個列表在FP語言里，其中每一個元素都必須實實在在地被創建出來，在被sum消費完之後，又被GC掉。
而實際上不停地對 i 自增再求和是可以完全不產生內存分配開銷的。（當然假如列表裡的元素不是簡單的Int而是更複雜的Integer或者String，或許仍然很難避免內存分配
這導致很多時候我們為了追求效率，會避免寫「消費列表」的代碼，轉而手寫一個尾遞歸版本。

請問現代編譯器是如何處理這個問題的？
這裡我做了個測試，WIN7，GHC 7.8.3，開了 -O2，然而算 maximum [1..10^9] 還是用了近20秒。（考慮到sum的話Int會溢出，所以測試用的是maximum；這個量級在C里測試僅僅用一秒左右）

上面邵成的答案很詳細了，我這裡就光講講如何讓 sum [1..1000] 在 GHC 裡面優化成功。Haskell 的 Standard Prelude 對 sum 的定義如下：

sum = foldl (+) 0

給定一個列表，展開結果是：

((( ...((0 + 1) + 2)... ) + 998) + 999) + 1000

也就是向左結合進行加法運算的結果。我們都知道 Haskell 的列表創建是惰性的，並且在這裡，因為 + 是嚴格求值，所以基本上 [1..1000] 的表，是求得下一個值就馬上消費掉了，這也是為什麼直接運行並不消耗過多空間。但列表結構畢竟還是存在的，而且不斷地創建和回收，所以最終的計算效率並不夠好。

有趣的是，曾經在 GHC 手冊裡面提到 List Fusion 的時候並沒有說支持 foldl，只是說支持 foldr。那麼我們能否用 foldr 來定義 sum 從而利用 list fusion 呢？當然可以：

sum1 :: [Int] -&> Int sum1 = foldr (+) 0

給定一個列表，展開結果是（把列表的構造器 :: 換成 + 把 [] 換成 0）：

1 + (2 + (... + (999 + (1000 + 0)) ...))

也就是向右結合進行加法運算。但運行 sum1 [0..10^9] 直接會造成棧溢出：

Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS" to increase it.

這是為什麼？我們仔細比較一下 Standard Prelude 裡面 foldl 和 foldr 的定義，不難得出結論：

foldl :: (a -&> b -&> a) -&> a -&> [b] -&> a foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs

foldr :: (a -&> b -&> b) -&> b -&> [a] -&> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)

很顯然 foldl 是尾遞歸的，而 foldr 不是。所以儘管 foldr 和 list generator 可進行 fuse 優化，但結果是得到了一個非尾遞歸的函數，調用它會造成棧溢出。那麼有沒有辦法解決尾遞歸的問題？有的，我們可以對 sum1 進行一些改造：

sum2 :: [Int] -&> Int sum2 xs = foldr (.+) id xs 0 where x .+ y = z -&> y (x + z)

這裡我們做了一個簡單的 CPS 變換，從用加法疊加數字，改變為函數的疊加。展開一下就是（把列表的構造器 :: 換成 .+ 把 [] 換成 id）：

1 .+ (2 .+ (... .+ (999 .+ (1000 .+ id)) ...))

如果只看定義，x .+ y 其實是把數字 x 和右邊函數 y 做一個運算，得到一個新函數。因為 x .+ y 的結果直接是一個函數（更準確的說法是閉包），所以整個 foldr 計算下來並不牽涉到遞歸求值，而是直接返回了一個閉包結構，這也是為什麼最終 sum2 的定義里，我們要再將這個閉包作用於 0 才能得到最後的數值 sum。

然而 GHC 是如此偉大的一個編譯器，它把 sum2 [1..n] 經由 list fusion 將 foldr 和 generator 消除掉，得到一個閉包，並繼續把這個閉包化簡為了一個尾遞歸函數（可以由 -ddump-prep 證實）。實際運行結果是，sum2 的效率和最高效的尾遞歸 sum3 是一樣的：

sum3 x y = acc 0 x where acc !s !x = if x &> y then s else acc (s + x) (x + 1)

當然，並非所有 foldl 都適合用這樣的變換成為 foldr，也並非所有 foldl 都滿足 list fusion 的條件。有興趣繼續深究的同學可以參考：

foldl as foldr to get list fusion
Haskell for all: foldl-1.0.0: Composable, streaming, and efficient left folds
takano-akio/ww-fusion · GitHub
https://www.joachim-breitner.de/blog/648-Going_to_TFP_2014

最後，請大家和我一起重複這句話：然而 GHC 是如此偉大的一個編譯器！Joachim Breitner 在最新的 GHC 7.10.1 中已經實現了上面第 4 條參考鏈接中（的論文）提到的 CallArity 優化。當 foldl 滿足條件時，可以直接進行 fusion。所以嘛，樓主，sum [1..n] 已經和 C 一樣快了哦！

已經針對題主的代碼更新了代碼樣例，看最後。

===原回答===

題主想得好。這不就是fusion乾的事嗎，deforestation/fusion/supercompiling。。愛叫啥叫啥，我統一叫fusion好了。以下粗糙地說幾點，爪機碼字，沒法扔鏈接和給代碼，見諒。

1. fusion for free

lazy語言里，sum [1..n]應該耗費O(1)內存，因為[1..n]不是規約到normal form才扔給sum的，只要sum是尾遞歸的寫法，那就是一邊加，一邊展開[1..n]，然後前邊用不到的元素會被gc回收。

2. fusion for all

還有種做法可以在不添加編譯器擴展的情況下，給所有語言（包括strict語言）加fusion。把所有的immutable數據結構分成delayed/manifest兩種，然後像是map/fold/concat之類的組合子，全部都只生成delayed表示的容器，然後一個複雜的表達式，就是一個delayed容器進行各種變換的pipeline，最後調用eval，把delayed轉成manifest容器，就可以獲取容器裡面的值了。一個典型例子是Haskell里的repa庫，針對數組（不是list，是array！）用這個技巧做fusion，同時還能夠輕易進行並行求值。

3. fusion by rewriting

上面兩種技巧的缺點在於，仍然沒有手寫for loop快（畢竟靠gc），或者增加程序員負擔（我只想操作一種容器）。那麼，終極的做法，就是在編譯器里做code transformation，檢測到程序員寫的可以進行fusion表達式，然後轉寫成沒有中間形式的版本。

這裡就有很多不同的fusion方案了，各有適用範圍。ghc里目前對list實現的fusion方案叫short cut fusion，參見SPJ的A short cut to deforestation一文。這之前有Philip Wadler的一些deforestation相關的文章，之後還有Generalized Stream Fusion等方案。。文章很多，可以自己看看。

另外值得一提的是ghc有個pragma，叫RULES，可以讓程序員在代碼里自己指定rewrite rules。所以假設你發明了一個新的數據結構和這上面的fusion演算法，不需要給編譯器打補丁，也可以以庫的方式實現。

fusion演算法也是fp語言編譯技術的一個重要領域，之前很多研究都是在non-strict語言上做的，這兩年也有人在嘗試做strict語言上的fusion，參見Positive Supercompilation for call-by-value一文。。non-strict語言的fusion演算法不能照搬到strict語言上，因為一些non-strict下成立的termination property不一定就在call by value下成立（@姚培森可以展開講這個。。）

總而言之就是，請放心大膽地使用immutable data structure，然後信任ghc（

===代碼樣例===

{-# OPTIONS_GHC -Wall -O2 -threaded -with-rtsopts="-N" #-}


import Data.Array.Repa as R

import Data.Functor.Identity

import Data.Vector as V

import Data.Vector.Unboxed as U

import System.TimeIt
n :: Int

n = 1000000000
naive_max :: Int

naive_max = Prelude.maximum [0..n-1]
vector_max :: Int

vector_max = V.maximum $ V.generate n id
vector_unboxed_max :: Int

vector_unboxed_max = U.maximum $ U.generate n id
repa_max :: Int

repa_max = R.foldAllS max 0 $ R.fromFunction (R.ix1 n) ((_ :. x) -&> x)
repa_parallel_max :: Int

repa_parallel_max = runIdentity $ R.foldAllP max 0 $ R.fromFunction (R.ix1 n) ((_ :. x) -&> x)

main :: IO () main = (timeIt $ putStrLn "======" &>&> putStr "naive_max: " &>&> print naive_max) &>&> (timeIt $ putStrLn "======" &>&> putStr "vector_max: " &>&> print vector_max) &>&> (timeIt $ putStrLn "======" &>&> putStr "vector_unboxed_max: " &>&> print vector_unboxed_max) &>&> (timeIt $ putStrLn "======" &>&> putStr "repa_max: " &>&> print repa_max) &>&> (timeIt $ putStrLn "======" &>&> putStr "repa_parallel_max: " &>&> print repa_parallel_max)

所以，站在普通Haskell程序員的角度，想要Haskell as fast as C的話，扔開Prelude即可。

另外召喚同樣閑得蛋疼的Haskeller幫我加個accelerate-cuda的測例（雖然我猜會慢不少）。。

在 Mathematica 里 Sum[i,{i,1,n}] 可以優化成 (1+n)*n/2, 然後就比 C 語言速度快了...

我來通俗一點回答。如果這份代碼你如此寫成C#的話，應該就是O(1)內存空間的：

Enumerable.Range(1, n).Sum()

下面我可以把他們寫出來（但是就不保持格式上的一致了）

IEnumerable& Range(int start, int end) { for (var i = start; i &<= end; I++) yield return I; } int Sum(IEnumerable& numbers) { var sum = 0; foreach (var i in numbers) sum += I; return sum; }

所以只要編譯成這樣就可以了。

這是一個簡單的reduction

如果trip count確定直接編譯時得到結果

否則循環的向量化可以做到