Haskell 執行速度怎樣？

函數式的思考方式我終於知道自己沒習慣了，我指的遞歸。
寫 Fabonacci 數累加的時候我發現 CoffeeScript 的執行速度都快很多，
計算 Fabonacci 30 的時候速度明顯。後來還死機，在 ghci 中執行的。
那麼 ghci 的速度究竟怎樣？編譯的呢？

ghci是一個解釋器，而且並沒有進行速度方面的優化，速度當然不快。對於遞歸計算fibonacci而言，你如果使用ghc來編譯，提供合適的類型提示（fibonacci :: Int -&> Int就足夠了）並且加上-O（優化）選項的話，那麼速度將會達到C的50%。這速度自然完爆任何解釋型語言，除了luajit和v8能勉強追上之外..

那麼為什麼ghc還是會比C慢一半呢？這就牽扯到現代CPU自身附帶的優化了。遞歸計算fibonacci的時候，將會進行多次函數調用和返回。函數調用很簡單，ghc和gcc生成的代碼沒什麼區別。不過在函數返回這一點上，gcc會使用指令集里現有的返回指令（比如x86上就是ret），這樣CPU的分支預測就可以準確預測返回地址，從而導致流水線不會出現停滯的情況。相反，ghc的調用協定就不同，它並不適用C的棧，所以在返回的時候並不使用原生的返回指令，而是使用一個indirect jump指令來完成（比如x86上就是jmp *(RXX)），這樣就使得CPU無法準確預測返回地址，從而導致流水線經常會出現停滯的情況。流水線停滯會導致什麼？會導致IPC（instruction per cycle，每CPU周期能運行的指令數量）下降，從而降低代碼的運行速度。Reddit上面的這篇帖子里，Simon Marlow也談到了他的SandyBridge i7在運行gcc和ghc生成的fibonacci代碼時，IPC相差了3倍。

（當然並不是說函數返回時的分支預測的問題ghc就無法解決了——編譯的時候也是可以提供一些代碼來幫助CPU進行分支預測的，不過也許是因為ghc的開發者們覺得這個並不是那麼重要）
^ 過了一年多的編輯：一個例子詳見 Branch predication test ，runDirectThreading可以看作是ghc當前使用的方法，而runWithPredictor可以看作是一種提供了額外的預測代碼的方法。Ivy Bridge/Haswell上，gcc-4.8 -O2編譯，兩者速度差別很大。

那麼ghc為什麼要這麼做呢？這是因為，haskell是一種lazy functional的語言，其運行時環境和C相差太大，所以不使用C的棧而轉而使用自己的一套調用協定將會更加合適——詳見Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine以及後續的Making a fast curry: push/enter vs. eval/apply for higher-order languages這兩篇paper。

對比 GCC C 的速度 http://shootout.alioth.debian.org/u32/benchmark.php?test=alllang=ghclang2=gcc
節省的人力更重要 http://www.haskell.org/haskellwiki/Why_Haskell_matters#The_speed_of_Haskel
08 年的狀況 http://neilmitchell.blogspot.com/2008/05/haskell-and-performance.html
豆瓣上相類的帖

http://www.douban.com/group/topic/23690425/
http://www.douban.com/group/topic/24027444/

事實上，函數式編程的程序寫法會在極大程度上影響效率。
如果做基本運算都死機的話（無論多麼複雜），首先要考慮代碼是否有問題.

fib = 0:1:zipWith (+) fib (tail fib)
main = do
putStrLn $ show $ last $ take 100000 fib

time ./fib 結果: real 0m0.952s
user 0m0.927s
sys 0m0.025s

在處理fibonacci這種結構的時候，如果用遞歸要注意遞歸方式。其公式直接轉換成代碼是樹形迭代，其展開的消耗以指數級方式增長而歸約的過程也會長很多(詳見SICP第一章論述)。在函數式中使用遞歸，盡量把操作轉化成尾遞歸。
不良代碼示例:

fib 0 = 0
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))
main = do
putStrLn $ show $ fib 100000

(此代碼佔用我100％ CPU＋300M內存，在我用網頁拼音輸入法敲完這篇答案，喝了兩杯水以後仍未能輸出結果。事實上這種方式求第35個數用了5秒，而求第38個數用了20秒。所以求第100000已經是不可能完成的任務。從時間增長上也能看出這種演算法的時間消耗不是線性的)
BTW: 我曾用Project Euler的第12題作為測試，用java，python，.net，haskell, c求解，都能在1.6秒之內得到結果。 ( http://projecteuler.net/problem=12 )
所以我的結論是如果是基本運算，在演算法相同的情況下，以C語言為標尺，各種語言都不會有太大差距。現代語言更多應該考慮的是語言（及其周邊類庫框架）的高級特性、平台機制，這才是是複雜應用場景下的選擇標準。

Haskell慢的就跟一坨屎一樣，上面說的能達到50%是GHC開最大優化才能達到C Debug版本的50%