Haskell简单递归求最大值运行极慢 如何优化超越Python

我正在使用一个简单的递归max算法开展Haskell性能分析实验，初始实现代码如下：

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

将其与功能等价的Python命令式实现做性能对比，发现Python版本的运行速度快10倍，Python实现代码如下：

with open("input.txt") as fl:
    data = [int(d) for d in fl.read().splitlines()]
max_ = 0
for d in data:
    if max_ < d:
        max_ = d
print(max_)

待排查的核心问题与测试背景：

• 这一性能差距是否是Haskell场景下使用尾递归的固有局限导致？
• 还有哪些其他方案可以提升该Haskell代码的运行速度？
• 本次测试使用的输入文件包含1M个无符号无界整数，数字平均长度为32位。

为便于排查问题，附上初始完整的Haskell代码文件如下：

import Max
import System.IO  
import Control.Monad
import System.Environment
import Prelude

readInt :: String -> Integer
readInt = read

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

main = do
    args <- getArgs
    contents <- readFile "input.txt"
    let numbers_as_strings = words $ contents
    let numbers = map readInt numbers_as_strings
    let max_number = max_tag 0 numbers
    print max_number

优化进展更新 #

采用@Willem Van Onsem建议的重构方案后性能提升明显，运行耗时从28秒缩短至12秒，重构后的代码如下：

max_bar :: Integer -> [Integer] -> Integer
max_bar head [] = head
max_bar head (x:xs) =
  let {b = head < x} in
    let {m = case b of {True -> x; False -> head}} in
      max_bar m xs

现寻求进一步的优化方案，目标是让该Haskell实现的运行速度超过Python。

问题解答 #

首先明确：性能差距和尾递归的固有局限完全无关。
你最初的max_tag实现根本不是尾递归：递归调用max_tag x xs之后，还要执行比较、条件分支逻辑，递归调用不是函数的最后一个动作，运行时会在内存中构建长度为100万的未求值调用链，这才是初始版本耗时28秒的核心原因。尾递归在GHC中会被优化为等价的命令式循环，不会产生栈堆积开销，性能完全可以和原生循环对齐。

你改完的max_bar已经是正确的尾递归形式，仍未跑赢Python，是因为还有几个明显的性能瓶颈没有处理，按优化收益从高到低排序：

• 替换低效的输入解析逻辑：当前使用String类型读入文件、再用默认的read函数解析整数是最大的性能瓶颈。Haskell默认的String是链表结构，单字符开销极大，默认read实现为了兼容通用语法规则也有大量冗余逻辑。可以换用bytestring库直接读取原始字节，跳过String中间层直接解析整数，这一项通常能带来3~5倍的性能提升。
• 增加严格性标注，避免惰性thunk堆积：当前尾递归实现中，比较结果b、累加的最大值m都是未求值的惰性表达式，遍历100万元素时会堆积100万个待计算的thunk，带来大量不必要的堆开销。可以开启BangPatterns扩展，给累加的最大值参数加上严格性标记!，或者用seq手动强制每一步的计算结果落地，保证每一步的最大值都是已经计算完成的具体数值。
• 用标准库的严格折叠替代手写递归：GHC内置的foldl'是经过高度优化的严格左折叠实现，比手写的递归模式匹配生成的核心代码效率更高，直接用foldl' max 0 numbers即可完成最大值遍历，避免手写递归时遗漏严格性带来的额外开销。
• 开足编译优化选项：不要用runhaskell或者默认无优化配置编译运行，编译时加上-O2选项，可额外添加-march=native生成适配当前CPU架构的机器码，运行时加上-threaded -RTS -N参数支持多核并行，这部分通常能带来30%以上的性能提升。
• 按需选择数值类型：如果你的32位整数实际不会超出有界整数范围，把Integer（无界大整数）换成Word32/Int这类机器原生整数类型，比较和运算的性能还能再提升一截，毕竟无界大整数本身就有额外的结构开销。

一个参考的优化后实现如下，实际运行速度完全可以超过Python版本：

{-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe (fromJust)
import Data.List (foldl')

main = do
    contents <- B.readFile "input.txt"
    let numbers = map (fst . fromJust . B.readInt) $ B.words contents
    let !max_number = foldl' max 0 numbers
    print max_number

编译命令参考：ghc -O2 -march=native Max.hs -threaded
运行命令参考：./Max +RTS -N

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