在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

Haskell代码用于create懒惰地评估列表,即需要元素foldl.一次不需要整个列表.

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

F#中的一种可能性是seq在create函数中使用表达式:这会以与Haskell相同的方式懒惰地生成列表.(我不确定OCaml是否具有相同的功能.)

Answer 2

首先,如果您正在对数字内容进行性能比较,列表不是最佳选择.尝试像矢量包这样的包用于快速数组.

请注意,由于循环融合,您可以在Haskell中做得更好.通过将create函数编写为枚举,编译器可以将create步骤和fold循环组合到一个不分配中间数据结构的循环中.像这样做一般融合的能力是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 []));;