F# 与 OCaml：堆栈溢出

我最近发现了一个关于适合 Python 程序员的 F# http://combiol.org/fs/FSUG_FS4PPv2.pptx，看完之后，我决定自己实现一个“蚂蚁谜题”的解决方案。

有一只蚂蚁可以在平面网格上走动。蚂蚁一次可以向左、向右、向上或向下移动一格。也就是说，蚂蚁可以从单元格 (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 http://pastebin.com/EzMt466b，并尝试了一下：

$ 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++ 实现 http://leonardo-m.livejournal.com/。与 Leonardo 的 C++ 实现相比，OCaml 版本的运行速度大约比 C++ 慢 2 倍。鉴于 Leonardo 使用队列来删除递归，这没关系。

I then 将代码翻译为 F# http://pastebin.com/0Vx5GTBQ...这就是我得到的：

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 倍 - 哎呀。

所以这个程序...

• 在 OCaml 下运行良好
• 在 .NET/F# 下根本不起作用
• 在 Mono/F# 下可以工作，但速度非常慢。

Why?

EDIT:怪异仍在继续 - 使用“--optimize+ --checked-”使问题消失，但仅限于 ArchLinux/Mono 下;在Windows XP和Windows 7/64位下，即使是优化版本的二进制堆栈也会溢出。

最终编辑：我自己找到了答案 - 见下文。

执行摘要：

• 我编写了一个算法的简单实现......它不是尾递归的。
• 我在Linux下用OCaml编译了它。
• 效果很好，0.14秒就完成了。

然后是时候移植到 F# 了。

• 我将代码（直接翻译）翻译为F#。
• 我在 Windows 下编译并运行它 - 我遇到了堆栈溢出。
• 我在 Linux 下获取了二进制文件，并在 Mono 下运行它。
• 它有效，但运行速度非常慢（84 秒）。

然后我发布到 Stack Overflow - 但有些人决定关闭这个问题（叹气）。

• 我尝试使用 --optimize+ --checked- 进行编译
• Windows 下二进制仍然堆栈溢出...
• ...但在 Linux/Mono 下运行良好（并在 0.5 秒内完成）。

是时候检查堆栈大小了：在 Windows 下，另一篇SO帖子指出它默认设置为1MB https://stackoverflow.com/questions/823724/stack-capacity-in-c。在 Linux 下，“uname -s”和测试程序的编译 http://www.linuxquestions.org/questions/linux-newbie-8/default-stack-size-on-linux-glibc-pthreads-358438/清楚地显示它是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（嗯，对于这个简单的小问题很重要）。

无论如何，为了一劳永逸地解决这个问题，我写了一个尾递归版本 http://pastebin.com/jZy8jKRL- 函数末尾的递归调用被转换为循环（因此，不需要使用堆栈 - 至少在理论上）。

新版本在Windows下也运行良好，并在0.5秒内完成。

所以，这个故事的寓意是：

• 请注意堆栈的使用情况，尤其是当您使用大量堆栈并在 Windows 下运行时。使用使用 /STACK 选项进行编辑 http://msdn.microsoft.com/en-us/library/d25ddyfc(v=vs.80).aspx要将二进制文件设置为更大的堆栈大小，或者更好的是，以不依赖于使用太多堆栈的方式编写代码。
• OCaml 在尾递归消除方面可能比 F# 更好 - 或者它的垃圾收集器在这个特定问题上做得更好。
• 不要对...粗鲁的人关闭你的 Stack Overflow 问题感到绝望，好人最终会抵消它们 - 如果问题真的很好:-)

附： Jon Harrop 博士的一些补充意见：

...你很幸运 OCaml 也没有溢出。 您已经发现实际堆栈大小因平台而异。 同一问题的另一个方面是不同的语言实现 以不同的速率占用堆栈空间并具有不同的性能 存在深堆栈时的特征。 OCaml、Mono 和 .NET 都使用不同的数据表示和 GC 算法，从而影响 这些结果... (a) OCaml 使用标记整数来区分指针， 给出紧凑的堆栈帧，并将遍历堆栈上的所有内容 寻找指点。标签基本上传达了足够的信息 让 OCaml 运行时能够遍历堆 (b) Mono 处理单词 在堆栈上保守地作为指针：如果作为指针，一个单词将指向 到堆分配的块中，则该块被认为是可访问的。 (c) 我不知道 .NET 的算法，但如果它吃掉堆栈我不会感到惊讶 space 更快，并且仍然遍历堆栈上的每个单词（当然 如果不相关的线程有一个 深栈！）...此外，您使用堆分配的元组意味着您将 快速填充苗圃一代（例如 gen0），因此， 导致 GC 经常遍历这些深栈......