Haskell递归求和函数编译为WASM后复杂度变为二次的问题问询

以下是涉及的Haskell代码：

{-# LANGUAGE ForeignFunctionInterface #-}
module Main where

import Data.Word (Word32)

sum' :: Word32 -> Word32
sum' 0 = 0
sum' n = n + sum' (n-1)

foreign export javascript "sum" sum' :: Word32 -> Word32

main :: IO ()
main = print (sum' 10000000)

上述递归求和函数编译为WASM后，时间复杂度从预期的线性变成了O(n²)，运行速度比原生版本慢数百万倍，不符合WASM的预期表现。想问这是编译器bug还是操作有误？

使用环境与操作步骤：

• GHC版本：GHC 9.11.20240817
• 编译命令：

wasm32-wasi-ghc main.hs -O2 -no-hs-main -optl-mexec-model=reactor

• 链接后处理步骤：

$(wasm32-wasi-ghc --print-libdir)/post-link.mjs -i main.wasm -o main.js

之后从JS中导入sum函数并传入不同n值调用。

分析与解决 #

这不是编译器bug，问题出在递归函数的导出方式上：你直接导出了递归的sum'函数，导致每一层递归调用都会触发JS与WASM之间的跨边界上下文切换——而这种切换本身带有固定开销。n层递归就会产生n次跨边界调用，总开销叠加后就表现为O(n²)的时间复杂度，最终速度暴跌。

解决方法 #

1. 隔离递归与导出边界

把递归逻辑封装在Haskell内部，只暴露一个顶层入口函数，让递归完全在WASM运行时内完成，不经过JS边界：

{-# LANGUAGE ForeignFunctionInterface #-}
module Main where

import Data.Word (Word32)

-- 纯Haskell递归，仅在内部调用
sumInternal :: Word32 -> Word32
sumInternal 0 = 0
sumInternal n = n + sumInternal (n-1)

-- 仅导出顶层入口，只在初始调用时走一次JS边界
foreign export javascript "sum" sumWrapper :: Word32 -> Word32
sumWrapper = sumInternal

main :: IO ()
main = print (sumInternal 10000000)

修改后递归完全在WASM内部执行，不会重复触发跨边界开销，时间复杂度回到线性。

2. 改用尾递归进一步优化

GHC对尾递归有自动优化（搭配-O2），可以将其转换为循环结构，消除函数调用栈的开销：

sumInternal :: Word32 -> Word32
sumInternal = go 0
  where
    go acc 0 = acc
    go acc n = go (acc + n) (n - 1)

这种写法在-O2优化下会被编译为类似循环的代码，性能更接近原生。

另外确保编译时-O2参数生效，它会帮助GHC完成尾递归消除、内联等关键优化，进一步提升WASM版本的运行效率。

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