OCaml和F#中的堆栈溢出，但在Haskell中不会。

Question

OCaml和F#中的堆栈溢出，但在Haskell中不会。

haskellf#ocamlstack-overflowlazy-evaluation

15

我出于娱乐目的，比较了不同语言在执行以下程序时的速度：

对于 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#的实现会导致栈溢出？

- FDP

5个回答

22

如果你正在进行数值比较的性能对比，首先要注意列表不是最佳选择。尝试使用类似vector这样的包来获得快速数组。

还要注意，在Haskell中，由于循环融合(loop fusion)的特性，你可以做得更好。通过将创建函数编写为枚举方式，编译器可以将创建步骤和折叠循环合并为一个单独的循环，从而不会分配任何中间数据结构。像这样进行通用融合的能力是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
    }

请注意有两个循环：create生成一个（惰性）列表，而fold则消耗它。由于惰性，该列表的成本很低，因此其运行速度相当快：

$ 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

这是一个很好的例子，展示了纯度保证所提供的强大功能--编译器可以非常激进地重新排列您的代码。

- Don Stewart

奇怪，我的版本只需要44毫秒执行时间，而你的需要76毫秒！ - FDP

需要对矢量库进行补丁以支持可熔双精度数（从向量的darcs版本获取，http:://code.haskell.org/vector）。 - Don Stewart

@Farnand Pajot：你使用了dons的命令行编译代码吗？我认为只有在启用优化时才会发生循环融合。 - liwp

是的，我使用了那些优化方式来优化一个简单的尾递归函数（没有涉及列表），执行时间快了3倍！ - FDP

9

修复代码让其在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需要优化你编写的纯代码）。无论如何，如果您有一些测试，可以试试！

- Tomas Petricek

1

为了使OCaml版本像Haskell版本一样懒惰地工作，您可以使用BatteriesIncluded中的Lazy_list模块。http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy_list.html - aneccodeal

感谢您的补充 - F# 还有 LazyList 模块（可以在 PowerPack 中找到），但它使用频率比 sequence expressions 低。 - Tomas Petricek

7

在这个表单中，您的create函数不是尾递归的。您可以将其重写为尾递归形式，这样就不会导致堆栈溢出：

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

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

- elmattic

1

没错，但出于某种原因它会对性能产生巨大影响（至少对于Haskell而言），执行时间会乘以3。 - FDP

2

@Fernand：在Haskell中，由于惰性求值的存在，最好使用你原来的函数。在没有惰性求值的情况下，最好 - 实际上几乎是必需的 - 使用尾递归版本。 - Michał Marczyk

在这个版本中，OCaml 是否仍然需要在计算 fold 之前将整个列表构建在内存中？在 Haskell 中，列表是按照消耗的顺序构建的，因此永远不会一次性全部存在内存中。 - MtnViewMark

3

在OCaml中，你可以使用Batteries Included中的LazyList模块，这样它就能与Haskell版本非常相似地工作：http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy_list.html - aneccodeal

3

这个程序在Haskell中运行得很好且速度快（即使使用foldl而不是foldl'），但在OCaml和F#中会导致堆栈溢出。

你的Haskell使用延迟列表，但你的OCaml/F#使用严格列表，所以你的程序无法比较。

顺便说一句，使用按需序列的F#解决方案如下：

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

- J D

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Robinson · Accepted Answer

create 的 Haskell 代码对列表进行惰性求值，也就是说，只有在 foldl 需要元素时才会计算。不需要一次性计算整个列表。

相比之下，F# 和 OCaml 对 create 列表进行严格求值，即在将其传递给 fold_left 之前，代码尝试一口气生成整个列表。

在 F# 中的一种可能性是，在 create 函数中使用 seq 表达式：这样可以像 Haskell 一样惰性地生成列表。（我不确定 OCaml 是否有类似的功能。）