如何优化Haskell的mysum函数使其性能媲美C++版本？

核心问题分析 #

你的两个Haskell版本慢的主要原因：

• 第一个版本依赖惰性列表[1..100000000]，即便用严格折叠，列表构造仍会带来额外内存与计算开销；
• 第二个版本使用多态类型(Num a, Eq a)，GHC无法生成最优原生机器码，多态字典查找和装箱操作会拖慢执行速度；
• 默认编译选项和后端优化不足，未充分发挥GHC的优化能力。

具体优化方案 #

1. 改用具体原生类型，消除装箱与多态开销 #

把多态的Num a替换成和C++unsigned long long对应的Word64（无符号64位整数），避免Integer的装箱开销和多态字典查找：

module Main where

import Data.Word (Word64)

main :: IO ()
main = print $ mysum 0 100000000 0

mysum :: Word64 -> Word64 -> Word64 -> Word64
mysum !from !to !now
  | from > to = now
  | otherwise = mysum (from + 1) to (now + from)

2. 启用高级编译优化选项 #

使用LLVM后端和更高等级的优化，让GHC生成接近C++的高效机器码：

ghc -O2 -fllvm -optlo-O3 Main.hs

• -O2：启用比-O更激进的优化（如函数内联、循环展开）；
• -fllvm：切换到LLVM代码生成后端，其数值计算优化能力远强于GHC原生后端；
• -optlo-O3：给LLVM传递最高等级的优化参数，进一步打磨机器码。

3. 用数学公式直接计算（终极优化） #

求和0到n的结果可通过公式n*(n+1)/2直接计算，完全跳过循环，时间复杂度O(1)，性能碾压任何循环实现：

module Main where

import Data.Word (Word64)

main :: IO ()
main = print $ sumFrom0To 100000000

sumFrom0To :: Word64 -> Word64
sumFrom0To n = n * (n + 1) `div` 2

优化效果验证 #

• 用具体类型+LLVM编译的递归版本，性能会和C++版本非常接近（差距在10%以内）；
• 公式计算版本的速度是所有版本中最快的，几乎瞬间完成计算。

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