OCaml 和 F# 中的堆栈溢出，但 Haskell 中没有堆栈溢出

Question

我一直在比较不同语言执行以下程序的速度： 对于 i 从 1 到 1000000 求和乘积 i*(sqrt i)

我的实现之一（不是唯一的）是构造一个列表 [1..1000000]，然后用特定函数折叠。

该程序在 Haskell 中运行良好且快速（即使使用 Foldl 而不是 Foldl' 时也是如此），但在 OCaml 和 F# 中会出现堆栈溢出。

这是 Haskell 代码：

test = foldl (\ a b -> a + b * (sqrt b)) 0

create 0 = []
create n = n:(create (n-1))

main = print (test (create 1000000))

这是 OCaml 代码：

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;;

let rec create = function
    | 0 -> []
    | n -> n::(create (n-1)) ;;

print_float (test (create 1000000));;

为什么 OCaml/F# 实现堆栈溢出？

Answer 1

create 的 Haskell 代码延迟计算列表，即当 foldl 需要元素时。不需要一次性提供整个列表。

相比之下，F# 和 OCaml 严格评估 create 列表，即代码在将其传递给 fold_left 之前尝试一次性生成整个列表。

F# 中的一种可能性是在 create 函数中使用 seq 表达式：这会以与 Haskell 相同的方式延迟生成列表。 （我不确定 OCaml 是否具有等效功能。）

Answer 2

首先，如果您要对数字内容进行性能比较，列表并不是最佳选择。尝试像 vector 包这样的包来实现快速数组。

请注意，由于循环融合，您可以在 Haskell 中做得更好。通过将创建函数编写为枚举，编译器可以将创建步骤和折叠循环合并到不分配中间数据结构的单个循环中。像这样进行通用融合的能力是 GHC Haskell 所独有的。

我将使用向量库（基于流的循环融合）：

import qualified Data.Vector as V

test = V.foldl (\ a b -> a + b * sqrt b) 0

create n = (V.enumFromTo 1 n)

main = print (test (create 1000000))

现在，在您的代码之前，编译器无法删除所有列表，我们最终会得到一个内部循环，例如：

$wlgo :: Double# -> [Double] -> Double#

$wlgo =
  \ (ww_sww :: Double#) (w_swy :: [Double]) ->
    case w_swy of _ {
      [] -> ww_sww;
      : x_aoY xs_aoZ ->
        case x_aoY of _ { D# x1_aql ->
        $wlgo
          (+##
             ww_sww (*## x1_aql (sqrtDouble# x1_aql)))
          xs_aoZ
        }
    }

$wcreate :: Double# -> [Double]

$wcreate =
  \ (ww_swp :: Double#) ->
    case ==## ww_swp 0.0 of _ {
      False ->
        :
          @ Double
          (D# ww_swp)
          ($wcreate (-## ww_swp 1.0));
      True -> [] @ Double
    }

注意如何有两个循环：创建生成一个（惰性）列表，以及使用它的折叠。由于懒惰，该列表的成本很便宜，因此它运行得体：

$ time ./C
4.000004999999896e14
./C  0.06s user 0.00s system 98% cpu 0.058 total

然而，在融合下，我们只得到一个循环！

main_$s$wfoldlM_loop :: Double# -> Double# -> Double#

main_$s$wfoldlM_loop =
  \ (sc_sYc :: Double#) (sc1_sYd :: Double#) ->
    case <=## sc_sYc 1000000.5 of _ {
      False -> sc1_sYd;
      True ->
        main_$s$wfoldlM_loop
          (+## sc_sYc 1.0)
          (+##
             sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc)))

GHC 将我们的创建和测试步骤减少到一个循环中，不使用任何列表。寄存器中只有 2 个双精度数。
循环数量减少一半，运行速度几乎提高一倍：

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make
$ time ./D
4.000005000001039e14
./D  0.04s user 0.00s system 95% cpu 0.038 total

这是保证纯度所提供的强大功能的一个很好的例子——编译器可以非常积极地重新排序代码。

Answer 3

修复代码以使其在 F# 中工作的另一种方法是使用也是延迟生成的序列表达式，并且以不会导致 StackOverflow 的方式生成（这在 OCaml 中不起作用，因为序列表达式是 F# 特定的）。这是代码：

let test nums = Seq.fold (fun a b -> 
  a + (float b) * (sqrt (float b))) 0.0 nums

let rec create count = seq {
  match count with
  | 0 -> do ()
  | n -> yield n
         yield! create (n-1) }

printf "%f" (test (create 1000000));; 

我不确定性能，但是编译器肯定在 create 函数中进行了优化，因此迭代生成的序列应该相当快。然而，序列表达式的目标主要是可读性（因为 F# 不是纯粹的，如果您确实需要它们，它为您提供了大量的手动优化空间，而不是 Haskell 需要优化您编写的纯代码）。不管怎样，如果你有一些测试，你可以尝试一下！

Answer 4

在这种形式中，您的 create 函数不是尾递归的。您可以以不会导致堆栈溢出的尾递归形式重写它：

let rec create n l =
    match n with 
    | 0 -> l
    | n -> create (n-1) (n::l)

print_float (test (create 1000000 []));;

Answer 5

该程序在 Haskell 中运行良好且快速（即使使用 Foldl 而不是 Foldl' 时也是如此），但在 OCaml 和 F# 中会出现堆栈溢出。

您的 Haskell 使用惰性列表，但您的 OCaml/F# 使用严格列表，因此您的程序是无可比拟的。

FWIW，在 F# 中使用按需序列的解决方案是：

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})