15

我一直在比较有趣的不同语言在执行以下程序时的速度：for i from 1 to 1000000 sum the product 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# 实现堆栈溢出？

4

5 回答 5

28

Haskell 代码create懒惰地评估列表，即foldl. 不需要一次全部列出整个列表。

相比之下，F# 和 OCamlcreate严格评估列表，即代码尝试在将整个列表传递给fold_left.

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

于 2010-02-20T14:39:29.670 回答
22

首先，如果您要对数字内容进行性能比较，列表不是最佳选择。尝试一个包，比如用于快速数组的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

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

于 2010-02-20T18:23:43.463 回答
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）。无论如何，如果你有一些测试，你可以试一试！

于 2010-02-20T15:07:45.307 回答
7

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

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

print_float (test (create 1000000 []));;
于 2010-02-20T14:43:10.693 回答
3

该程序在 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})
于 2010-05-11T02:31:55.373 回答