Haskell有哪些提高效率的技巧？

01-15

在學習Haskell，Monad,STRef等特性和很多內置函數用得不太溜，做很多事情都是從頭自己寫起來，可能執行效率會很慢。有什麼能提高程序執行效率的技巧嗎？或者在優化程序的時候有什麼思路嗎？另外，看到網上很多寫Haskell的動不動就用到Monad+do塊，然後就處於一種過程式編程的風格里。我知道這仍然是純函數，只是不知道Haskell是不是提倡這種寫法？

問題問得太混亂。我只回答前半個問題（提高程序執行效率/優化程序的思路）吧。。

1. 使用合適的數據結構

比如盡量多用Vector代替List（除非需要大量cons/uncons操作）；Writer monad中用DList代替List；盡量用unordered-containers代替containers，用ByteString/Text代替String，等等；

2. 不要過早使用IORef/STRef

能用StateT的場合盡量避免直接用IORef/STRef，實際上性能一般都是前者更佳。。（

3. 使用合適的並行/並發抽象

比如需要共享狀態時，基本的primitive有IORef、MVar、TVar，其overhead是逐漸遞增的，而能力也是逐漸遞增的（IORef支持單變數CAS操作，MVar有blocking的get/put，隱含了condition variable，而TVar背後的STM支持多變數讀寫的事務），選擇能夠滿足需要的最弱的一個；Haskell線程和array/dataflow parallel編程相關的，這個要講也太多了，強烈推薦Simon Marlow的《Parallel and Concurrent Programming in Haskell》

4. 適時使用Streaming I/O

這個請自行查閱《九評Lazy I/O》，哦不對，pipes/conduit文檔。。

5. 動靜結合調試性能問題

靜：學會讀ghc編譯輸出Core代碼（尤其是經過simplifier之後的），看哪些地方inline了，哪些地方specialize了，哪些地方應用了strict/unbox優化，等等。。

動：使用RTS的profile功能；使用threadscope工具查看eventlog；使用criterion進行benchmark，比較性能，用weigh來檢測各種內存分配行為；對於生產環境的伺服器，用ekg監視內存佔用，等等

6. 適量使用strict求值

說到性能，是不是惰性求值就是性能的天敵呢？非也。。這個展開來說就長了，總之，需要引入strict求值的工具我們還是有的，seq/deepseq，bang pattern，以及ghc 8引入的Strict語言擴展。應適量使用strict求值，並且通過benchmark來衡量效果，而不是無腦默認全部lazy/strict。

7. LLVM後端有奇效

尤其是一些並行度高的數值計算代碼，LLVM後端比默認的ASM後端生成代碼效率有明顯提升（編譯時間也是）。RTS支持的primop里，有一組SIMD primop就是只在LLVM後端才支持的（想看RTS到底支持哪些primop，自行查看ghc-prim的haddock文檔）。

8. 理解一些語言特性的編譯器實現

比如一條最重要的常識：Haskell中，多態是有性能代價的（很多人誤以為type class編譯完了以後就自動specialize掉了，實際上不總是如此）；另外還有喜聞樂見的Generics/Template Haskell之爭，要性能不要優雅？那就手寫Template Haskell（

長期在reddit上圍觀別人撕逼，互懟後……我總結出有幾個基礎的性能提升要訣是應該了解的，不然很容易被打臉 ( ????? )

01 不要用尾遞歸，要麼尾遞歸和嚴格求值一塊用。這條可以擴展成多用foldr，少用foldl。

大部分從其他函數式語言轉過來人尤其容易中招。尾遞歸後性能不升反降，為什麼？構建太多thunk

一看foldr，直覺要遍歷整個表，其實不是的，惰性求值保證結果一出來就立即返回，有時候就讀個表頭

02 表操作 ++ 注意其右結合屬性。參考手冊list fusion一節，了解「good producers」和「good consumer」

嚴格求值幾乎是每個新手對「調優」的條件反射，嚴格求值之所以可以加快速度是因為減少了構造thunk，但是thunk很多時候並不是主要矛盾

其實大量的時間是用在解構和構造新數據結構上，這個開銷往往比thunk還大，所以應該先關注數據結構，尤其是那些作為組合子界面的中間數據結構，看能不能「融合」（fusion）掉

你不用組合子風格，fusion也不一定有大用，但用了組合子風格，必須考慮fusion

03 儘可能使用int類型

我這裡並不是要吐槽integer類型，我要吐槽的是int#，word32…… 大部分情況下真沒必要，用int就行

04 命令式風格大部分情況下不能解決性能問題

這又回到題主的問題了，monad 這樣的風格是解決性能問題的通用方法么？答案是：不是，儘管它們給人一種c的感覺

reddit上有一個關於某個haskell程序性能的討論，貼主用上了int#，st monad和嚴格求值，這個程序又長又丑，你猜最後怎麼著？另外一個人用一行組合子風格的程序達到了相同的性能，後者僅僅使用了int和fusion

（貼主還硬拗說這次是題目沒選對，肯定能找到非這樣寫不行程序，只能呵呵了，可見他根本沒仔細考慮問題出在哪裡）

知乎上也有一個類似案例，最後發現性能的關鍵點同樣是用一個位操作——這已經到了「指令篩選」那個pass，我們在大多數時候是無法干預這個pass的，只能寄望於更好的後端

最後，如果都把代碼寫成c或者ML還要Haskell幹嘛呢，我認為大部分情況下應該堅持使用組合子風格，堅持惰性求值

樓上 TJ（畢竟匿名了，我也不好直接 @..）已經說的很好了，我再補充幾點：

怎麼寫執行效率高？

在可讀性差不多的情況下，盡量選擇依賴較少/語義較弱的寫法，因為這樣做（據說）更易為編譯器所優化，而且通常也更為簡單易懂一些。

比如如果某件事情用 Applicative 就能精確描述的話，那就可以不用 Monad （例如用 parser combinator 來處理 context-free grammar）。再比如能用 List.{foldr,unfold} 甚至是 fixpoint functor 的時候那就別手寫遞歸，前者語義比較弱，GHC 裡面有對應的 rewrite rules 來進行 stream fusion，樓上所提到的 streaming IO 庫也是充滿 rewrite rules。手寫遞歸就沒有這個好處。當然具體的情況還是要具體分析，效率分析工具很重要。

過程式的寫法好不好？

好呀！「哈斯凱爾是最好的過程式語言（當然是個玩笑——Why is Haskell (sometimes) referred to as "Best Imperative Language"?）」，我們怎麼能不支持過程式的寫法..

如果要描述一個過程式的演算法，那麼用過程式的寫法來實現，通常可讀性是較高的。並不是說不能用過程式的方式寫，而是要見人說人話，適應不同的情況。某種寫法寫起來舒服，大家也看的明白，那就是最好的。

常用的 Monad 在各種庫里支持也是相當好的，比如 ekmett 的 Lens 庫里就針對常用的 Monad 提供了方便的操作方式。

有基本書，值得看一下

Haskell Design Patterns
Haskell Data Analysis Cookbook

這兩本書，網上找一下吧，草民，看了一些，還是有些用的，第一本，亞馬遜的電子書有買（土豪們可以考慮）

還有一本書叫

Haskell Financial Data Modeling and Predictive Analytics

Haskell 商業應用的一個例子（算是吧）

還有一本，名字翻譯過來大概是交 Haskell的高性能編程啥的，出版日期是今年10月份（現在的日期是7月4日）

關於 Monad 與 do 記法，我只能說，官方文檔可以解釋，還有上面第一本書

llvm 後端優化有神奇的效果，（贊同樓上的觀點），但是很多時候，安裝llvm，尤其在一些CI 平台上，安裝 llvm ，（還是不如讓我吃屎）

（最後，對方不願意講話，直接拋出一本：

GHC Users Guide Documentation 、

給你

看到網上很多寫Haskell的動不動就用到Monad+do塊，然後就處於一種過程式編程的風格里。我知道這仍然是純函數，只是不知道Haskell是不是提倡這種寫法？

提倡的，至少不反對，呵呵~

別的問題答不上來，呼喚 @閱千人而惜知己@邵成