F#vs OCaml:堆栈溢出

Question

我最近在Python程序员面前发现了一个关于F#的演示文稿,看了之后,我决定自己实现"蚂蚁拼图"的解决方案.

有一只蚂蚁可以在平面网格上走动.蚂蚁可以一次向左,向右,向上或向下移动一个空间.也就是说,从单元格(x,y),蚂蚁可以进入单元格(x + 1,y),(x-1,y),(x,y + 1)和(x,y-1).蚂蚁无法访问x和y坐标的数字之和大于25的点.例如,点(59,79)是不可访问的,因为5 + 9 + 7 + 9 = 30,大于25.问题是:如果从(1000,1000)开始,蚂蚁可以访问多少个点,包括(1000,1000)本身？

我首先在30行OCaml中实现了我的解决方案,并尝试了它:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

整洁,我的结果与leonardo在D和C++中的实现相同.与leonardo的C++实现相比,OCaml版本的运行速度比C++慢大约2倍.这是好的,因为leonardo使用队列来删除递归.

然后我将代码翻译成F# ......这就是我得到的:

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException

堆栈溢出...有两个版本的F#我在我的机器中......出于好奇,我接着生成了二进制文件(ant.exe)并在Arch Linux/Mono下运行它:

$ mono -V | head -1
Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)

$ time mono ./ant.exe
Points: 148848

real    1m24.298s
user    0m0.567s
sys     0m0.027s

令人惊讶的是,它在Mono 2.10.5下运行(即没有堆栈溢出) - 但它需要84秒,即比OCaml慢587倍 - oops.

所以这个程序......

• 在OCaml下运行良好
• 在.NET/F#下根本不起作用
• 在Mono/F#下工作,但速度很慢.

为什么？

编辑:奇怪的继续 - 使用"--optimize + --checked-"使问题消失, 但只在ArchLinux/Mono下 ; 在Windows XP和Windows 7/64bit下,即使优化版本的二进制堆栈溢出也是如此.

最后的编辑:我自己找到了答案 - 见下文.

Answer 1

执行摘要:

• 我写了一个算法的简单实现......这不是尾递归的.
• 我在Linux下用OCaml编译它.
• 它运行良好,并在0.14秒内完成.

那是时候移植到F#了.

• 我将代码(直接翻译)翻译成F#.
• 我在Windows下编译,并运行它 - 我有一个堆栈溢出.
• 我在Linux下使用二进制文件,并在Mono下运行它.
• 它工作,但运行非常缓慢(84秒).

然后我发布到Stack Overflow - 但是有些人决定关闭这个问题(叹气).

• 我尝试用--optimize + --checked-编译
• Windows下的二进制仍然堆栈溢出...
• ...但在Linux/Mono下运行正常(并在0.5秒内完成).

是时候检查堆栈大小了:在Windows下,另一个SO帖子指出它默认设置为1MB.在Linux下,"uname -s"和测试程序的汇编清楚地表明它是8MB.

这解释了为什么程序在Linux下运行而不在Windows下运行(该程序使用超过1MB的堆栈).它没有解释为什么优化版本在Mono下比非优化版本运行得更好:0.5秒vs 84秒(即使-optimize +似乎默认设置,请参阅Keith评论"Expert F#"提取).可能与Mono的垃圾收集器有关,它在某种程度上被第一版驱动到了极端.

Linux/OCaml和Linux/Mono/F#执行时间(0.14 vs 0.5)之间的区别是因为我测量它的简单方法:"time ./binary ..."也测量启动时间,这对Mono来说很重要/.NET(对于这个简单的小问题很重要).

无论如何,为了一劳永逸地解决这个问题,我编写了一个尾递归版本 - 函数末尾的递归调用转换为循环(因此,不需要堆栈使用 - 至少在理论上).

新版本在Windows下运行良好,并在0.5秒内完成.

所以,故事的道德:

• 请注意您的堆栈使用情况,特别是如果您使用大量堆栈并在Windows下运行.使用带有/ STACK选项的EDITBIN将二进制文件设置为更大的堆栈大小,或者更好的是,以不依赖于使用过多堆栈的方式编写代码.
• OCaml可能比F#更好地消除尾部递归 - 或者它的垃圾收集器在这个特定问题上做得更好.
• 不要绝望......粗鲁的人关闭你的Stack Overflow问题,好人会最终抵制他们 - 如果问题真的很好:-)

PS Jon Harrop博士的一些额外意见:

......你很幸运,OCaml也没有溢出.您已经确定实际堆栈大小因平台而异.同一问题的另一个方面是不同的语言实现以不同的速率占用堆栈空间,并且在存在深层堆栈时具有不同的性能特征.OCaml,Mono和.NET都使用不同的数据表示和影响这些结果的GC算法......(a)OCaml使用标记的整数来区分指针,给出紧凑的堆栈帧,并遍历堆栈中寻找指针的所有内容.标记基本上传达了足够的信息,以便OCaml运行时能够遍历堆(b)Mono保守地将堆栈上的字视为指针:如果作为指针,一个字将指向堆分配的块,那么块被认为是可达的.(c)我不知道.NET的算法但是如果它更快地占用堆栈空间并且仍然遍历堆栈中的每个单词我都不会感到惊讶(如果不相关的线程有深堆栈,它肯定会受到GC的病态性能!) ...此外,使用堆分配的元组意味着您将快速填充托儿所生成(例如gen0),因此导致GC经常遍历那些深层堆栈...

Answer 2

让我试着总结一下答案.

有3点要做:

• 问题:递归函数发生堆栈溢出
• 它只发生在windows下:在linux上,对于检查的问题大小,它可以工作
• OCaml中的相同(或类似)代码有效
• 优化+编译器标志,对于检查的问题大小,工作

Stack Overflow异常是递归vall的结果,这是很常见的.如果调用处于尾部位置,则编译器可以识别它并应用尾调优化,因此递归调用不会占用堆栈空间.Tailcall优化可能发生在F#,CRL或两者中:

CLR尾部优化1

F#递归(更一般)2

F#尾调用3

正如其他人所说,"在Windows上失败,而不是在linux中失败"的正确解释是两个OS上的默认保留堆栈空间.或者更好的是,两个操作系统下编译器使用的保留堆栈空间.默认情况下,VC++仅保留1MB的堆栈空间.CLR(可能)是用VC++编译的,所以它有这个限制.保留的堆栈空间可以在编译时增加,但我不确定它是否可以在已编译的可执行文件上进行修改.

编辑:事实证明它可以完成(请参阅此博客文章http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx)我不会推荐它,但在极端情况下,至少它是可能.

OCaml版本可能有效,因为它是在Linux下运行的.但是,在Windows下测试OCaml版本也会很有趣.我知道OCaml编译器在尾部调用优化方面比F#更具攻击性.它甚至可以从原始代码中提取尾部可重用函数吗？

我对"--optimize +"的猜测是,它仍然会导致代码重现,因此它仍会在Windows下失败,但会通过使可执行文件运行得更快来缓解这个问题.

最后,最终的解决方案是使用尾递归(通过重写代码或通过重新分析积极的编译器优化); 这是一种避免使用递归函数的堆栈溢出问题的好方法.