Haskell如何编写地道高效的循环？Advent of Code习题性能问题求解

堆内存占用过高的原因 #

你写的尾递归逻辑看似和C循环对等，但GHC默认采用惰性求值策略，所有递归参数在没有显式标注严格性的情况下，不会立刻计算值，只会在迭代过程中累计数千万个未求值的thunk（临时计算对象），全部堆在内存里，最终导致数GB的占用，同时大量GC操作也会拖慢CPU执行效率，和C直接在栈上更新原生整数的行为完全不同。

高效地道的Haskell写法 #

首先第一步要在cabal配置中添加GHC编译参数 -O2，开启全程序优化，没有优化的GHC生成代码性能会比C低1~2个数量级。

方案1：带严格性标注的尾递归 #

开启BangPatterns语言扩展，给所有递归累加器添加严格性标记，强制每次迭代立刻计算参数值，避免thunk堆积。开O2优化后GHC会自动将这些Int拆为未装箱的原生机器整数，全程无堆分配，性能和C版本基本一致。
示例代码：

-- 文件头部开启BangPatterns扩展
{-# LANGUAGE BangPatterns #-}

run :: IO ()
run = do
    print "Starting:"
    print (iteration''' 0 1 3 0 50000000)

iteration''' :: Int -> Int -> Int -> Int -> Int -> (Int, Int, Int, Int)
-- 所有参数前加!表示严格求值
iteration''' !cp !cv !ss !zv 0 = (cp, cv, ss, zv)
iteration''' !cp !cv !ss !zv !count = iteration''' ncp ncv ss nzv (count - 1)
    where
        ncp = ((cp + ss) `mod` cv) + 1
        nzv = if ncp == 1 then cv else zv
        ncv = cv + 1

方案2：ST Monad可变状态写法 #

如果更习惯C式的命令式写法，可以用ST Monad操作可变变量，逻辑和你的C参考代码完全一一对应，开O2后性能同样接近C：

import Control.Monad.ST
import Data.STRef
import Control.Monad (when, forM_)

run :: IO ()
run = print $ runST $ do
    let stepSize = 3
    zv <- newSTRef 0
    position <- newSTRef 0
    forM_ [1..50000000] $ \i -> do
        p <- readSTRef position
        let newP = (p + stepSize) `mod` i
        writeSTRef position (newP + 1)
        when (newP == 0) $ writeSTRef zv i
    readSTRef zv

注意不要使用Integer类型做累加器，你的代码里用的Int是机器字长整数，已经符合要求，Integer是任意精度整数，会带来额外的性能开销。

内容的提问来源于stack exchange，提问作者Tanse