為什麼這段 Haskell 代碼比 C 慢那麼多？

我在 StackOverflow 的提問：performance - Haskell: Why does Int performs worse than Word64, and why my program is far slower than C?

這段代碼是計算給定整數區間最長的冰雹序列，比如 3 -&> 10 -&> 5 -&> 16 -&> 8 -&> 4 -&> 2 -&> 1，即奇數乘三加一，偶數除以二，最終總能得到 1。

C 代碼：

#include &

int main(int argc, char **argv) {
int max_a0 = 1000000;
int longest = 0, max_len = 0;
int a0, len;
unsigned long a;

for (a0 = 1; a0 &<= max_a0; a0++) { a = a0; len = 0; while (a != 1) { len++; a = ((a%2==0)? a : 3*a+1)/2; } if (len &> max_len) {
max_len = len;
longest = a0;
}
}
printf("(%d, %d)
", max_len, longest);
return 0;
}


Haskell 代碼：

collatzNext :: Int -&> Int
collatzNext a
| even a = a `div` 2
| otherwise = (3 * a + 1) `div` 2

collatzLen :: Int -&> Int
collatzLen n = collatzIter n 0
where
collatzIter 1 len = len
collatzIter n len = collatzIter (collatzNext n) (len + 1)

main :: IO ()
main =
print $ maximum $ [collatzLen x | x &<- [1..1000000]]

前者在我的電腦上運行時間為 0.2s，後者為 2s，如果我將類型簽名從 Int 改成 Word，速度能提升一倍。我同時測試了 GHC 7.8/7.10。

問題是：

一、為什麼 Word 反而比 Int 快？

二、為什麼 Haskell 版本這麼慢？我這裡全是尾遞歸，我也嘗試過 BangPatterns 強制使用 strict eval，但是基本沒有提升，可能 O2 開關的 strict analysis 起作用了。這種純數值運算，Haskell 應該不比 C 差啊？

---

Stack Overflow 是個神奇的網站，大神調教出了一個比 C 更快的 Haskell 版本，還很優雅，連尾遞歸都（幾乎）沒用！

本回答轉自 Stack Overflow，原作者 András Kovács，回答的英文原始地址請戳這裡。

這段代碼的性能取決於好幾個因素。搞定其中的每一個，這段代碼的性能能達到 C 版本的水平。這些因素分別是：

一、使用正確的整數類型

題目中給出的 C 代碼並非最佳：它在所有架構上均使用 32 位整數（主流 C 實現中，只有 long 在 64 位機器上為八個位元組），而 Haskell 的 Int 在 64 位機器上是 64 位整數。比較要想準確，我們就應該在兩段代碼里使用相同的整數類型。此外，如非必要，我們都應當在 Haskell 代碼里使用原生的整數類型，即在 64 位機器上使用 64 位數字，而不是 Int32 或者 Word32 之流，因為 GHC 對非原生整數類型的操作往往是通過調用外部 C 函數來實現的，這很慢。

二、collatzNext 中的除法操作

對 Int 來說，div 比 quot 慢很多，這是因為 div 對負數有特殊處理。用 Word 之所以會讓程序變快，是因為對 Word 來說，div 和 quot 是一樣的。但這還是比 C 要慢一些。除以二可以通過右移一位來實現。因為種種原因，即使 LLVM 也沒有實現這一特定優化，所以我們最好手工實現它，將 quot n 2 換成 shiftR n 1。

三、奇偶檢查

最快的檢查奇偶的方式莫過於看最後一二進位位的值了。LLVM 可以對 even 函數做此優化，而 GHC 默認的後段則不可以。因此，如果我們要使用默認的後端，我們可以把 even n 換成 n .. 1 == 0，這對性能有著不錯的提示。

然而，我發現 GHC 7.10 有一個小性能 bug：它沒有為 Word 類型內聯 even 函數，這對性能影響很大（一次額外的函數調用，Word 是 box 類型因而分配在堆上，even 函數位於代碼最「活躍」的路徑上）。因此，我們應該使用 rem n 2 == 0 或者 n .. 1 == 0 而不是 even 函數。不過 GHC 對 Int 類型還是會內聯 even 的。

四、合併掉 collatzLen 中的列表

題主補充：我是在實驗一篇博客文章的時候提這個問題的，博客鏈接在我的 SO 問題中給出。作者的第一個 Haskell 版本的 collatzLen 是這麼實現的：

collatzLen a0 = length $ takeWhile (/= 1) $ iterate collatzNext a0


但這段代碼在使用 LLVM 後端的情況下，耗時為 C 的十倍，這是因為這段代碼會產生中間列表，內存分配很耗時間。這段代碼本質上等價於我在本問題下給出的 collatzLen 實現，這個中間列表是可以優化掉的。

這是一個很重要的因素。那篇博文在列表合併的問題上有些過期了。GHC 7.8 合併不掉 collatzLen 的中間列表，但 7.10 可以。也就是說，使用 GHC 7.10 和 LLVM 後端，我們可以優雅地得到 C 一般的性能。

collatzNext a = (if even a then a else 3*a+1) `quot` 2
collatzLen a0 = length $ takeWhile (/= 1) $ iterate collatzNext a0
maxColLen n = maximum $ map collatzLen [1..n]

main = do
[n] &<- getArgs print $ maxColLen (read n :: Int)

GHC 7.10.1，O2 優化，LLVM 後端，n = 10000000，上述代碼執行時間為 2.8 秒，而等價的 C 代碼用了 2.4 秒。如果不用 LLVM 後端，那麼運行時長將為 12.4 秒。這完全是因為缺少對 even 函數的優化。使用 a .. 1 == 0 可以解決這個問題。

五、合併掉計算最大長度時產生的中間列表

即使 GHC 7.10 也做不到（但理論上似乎可行），所以我們要求助手寫循環了（額，所有讀者都應該知道尾遞歸等價於循環吧）。

collatzNext a = (if a .. 1 == 0 then a else 3*a+1) `shiftR` 1
collatzLen = length . takeWhile (/= 1) . iterate collatzNext

maxCol :: Int -&> Int
maxCol = go 1 1 where
go ml i n | i &> n = ml
go ml i n = go (max ml (collatzLen i)) (i + 1) n

main = do
[n] &<- getArgs print $ maxCol (read n :: Int)

GHC 7.10.1，O2 優化，LLVM 後端，n = 10000000，上述代碼執行時間為 2.1 秒，C 的為 2.4 秒。要想在沒有 LLVM 和 GHC 7.10 的情況下得到類似的性能，我們只需要手工加上這些優化就好了：

collatzLen :: Int -&> Int
collatzLen = go 0 where
go l 1 = l
go l n | n .. 1 == 0 = go (l + 1) (shiftR n 1)
| otherwise = go (l + 1) (shiftR (3 * n + 1) 1)

maxCol :: Int -&> Int
maxCol = go 1 1 where
go ml i n | i &> n = ml
go ml i n = go (max ml (collatzLen i)) (i + 1) n

main = do
[n] &<- getArgs print $ maxCol (read n :: Int)

GHC 7.8.4，O2 優化，n = 10000000，上述代碼運行時間為 2.6 秒。

大家覺得贊的，看在我翻譯的份上送我個贊吧，然後記得去 SO 給原作者點贊。

---

結論更新:

原來的版本速度主要慢在 div 除法和 even函數上面.

直接在原來的版本上把相應操作換成quot 和 與 位運算後, 再開啟優化選項(-O3), 速度提升到了0.3s, 也是接近C的速度. 可見關鍵在於這兩個操作, 與使用unboxed類型, strict無關, 開啟優化後這些工作ghc會幫我們完成. (不過使用unboxed類型依然會快一點!而且不用開啟優化選項就很快)

相關部分代碼

collatzNext :: Int -&> Int
collatzNext a = r `quot` 2 -- 0.30 with -O3
--collatzNext a = r `div` 2 -- 1.39s with -O3
where
r = if a .. 1 == 0 then a else 3 * a + 1 -- 使用and運算代替even函數

collatzLen :: Int -&> Int
collatzLen n = collatzIter n 0
where
collatzIter 1 len = len
collatzIter n len = collatzIter (collatzNext n) (len + 1)


------------

補充:

非常影響性能的點:

判斷奇偶數(even)時, 使用 位運算 代替求余, 速度會從使用unboxed類型後的1.27s直接提升到0.29s.

乘法運算 替換成 一次位移一次加法,性能提升不明顯. 不過 @Tang Boyun的結論 ghc優化底層不夠好的結論是對的.

----------

補充: 我沒有使用llvm後端

----------

我在使用unboxed類型以及用位運算實現(even)之後, 速度由原來的 2s多提高到了0.29s左右, 基本等價於C的速度.

以下是代碼:

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

import GHC.Types
import GHC.Prim

collatzNext :: Int# -&> Int#
collatzNext a =
case andI# a 1# of
0# -&> quotInt# a 2#
--_ -&> (3# *# a +# 1#) `quotInt#` 2#
_ -&> ((uncheckedIShiftL# a 1#) +# a +# 1#) `quotInt#` 2#

collatzLen :: Int# -&> Int#
collatzLen n = collatzIter n 0#
where
collatzIter 1# len = len
collatzIter n len = collatzIter (collatzNext n) (len +# 1#)

main :: IO ()
main = do
print (I# (find_max_len 1# 0#))

find_max_len :: Int# -&> Int# -&> Int#
find_max_len 1000000# max_len = max_len
find_max_len n max_len =
case cn &># max_len of
0# -&> find_max_len nn max_len
_ -&> find_max_len nn cn
where
nn = n +# 1#
cn = collatzLen n


---

幾個可以優化的點:

1. 除法不要用div ，用quot

2. 編譯選項里加-fllvm，用llvm後端編譯。不用llvm後端的話，那就自己把乘法展開，*3變成一次移位，一次加法。c編譯器會做這個優化，ghc默認後端不會，ghc優化集中在core及以上level，底層優化不行。

實際使用時候，沒必要做以上的這種優化，因為性能瓶頸不會在這種地方。

---

1. 作者的原始版本，在我這台MBP(i7, macOS 10.12.2)上運行的情況：C/clang (clang-800.0.42.1) 1.875s 上下, GHC 7.8.3 (bootstrap by 7.6.2) 10.284s 上下

2. András Kovács 最後的版本頭上要加上import，不然編譯報錯

import Data.Bits

import System.Environment (getArgs)

3. GHC 8.0.1 -fllvm 下優化後的版本是 2.37~2.40 之間

4. C 的版本也用位操作替換取模和除，也可提升一丁點兒，1.668~1.695s。

*均為 -O2

這麼看來 GHC 性能是可以搞得很不錯的，就是陷阱略多。另外不知道András Kovács那個比原始C版本還快是怎麼跑出來的。

---

題外話，關於Haskell代碼的優化

必備的：

調優：

熟用RTS，這個相當於Haskell的perf?可以查看熱點函數、內存使用情況等；

用-ddump-xx查看相關信息；

其他語言無關的工具

發現問題是第一步

可控的：

副作用：

ST Monad可以模擬副作用（寫出來比較難看）

數據類型：

Unboxed Type，代碼寫出來會比較難看（同ST Monad）

Data.Word

另外Data.xx還有很多很多黑魔法。。。

數據結構：

比如要注意到List的某些操作是O(n)，必要時換Vector，以及各種」Functional Array「

數值計算：

比如C語言的除法，編譯器除了優化成位運算，也會根據操作數類型做具體優化。 用`quot`和Word32/Word64就和C語言中差不多了。。

求值策略：

某些函數用Strict版本

可控-不可控之間

Deforestation，Fusion，Strictness Analysis等High level的優化，以及Runtime中一些Low level的設計，基本上只能」相信編譯器「。當然在熟悉其原理後，可以嘗試寫利於優化的代碼。。

-----

某種程度上說，效率越接近C，代碼就可能越「遠離Haskell「。。用比較自然的語法來寫高效的程序，還是Ocaml更靠譜（逃。。），況且Ocaml各種庫的黑魔法也不少。

---

推薦閱讀：