F＃vs OCaml：堆栈溢出
最近我发现了一个关于Python程序员的F＃的演示，在看完之后，决定自己实现一个解决“ant难题”的解决scheme。
有一只可以在平面网格上走动的ant。 ant可以一次向左，向右，向上或向下移动一个空间。 也就是说，从细胞（x，y），ant可以进入细胞（x + 1，y），（x-1，y），（x，y + 1）和（x，y-1）。 ant无法进入x和y坐标的数字之和大于25的点。 例如，点（59,79）是不可访问的，因为5 + 9 + 7 + 9 = 30，它大于25.问题是：如果ant在（1000,1000）开始时访问多less个点，包括（1000，1000）本身？
我首先在30行OCaml中实现了我的解决scheme，并试用了它：
$ 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倍。 这是可以的，因为莱昂纳多使用队列来消除recursion。
然后我把代码翻译成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 -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
令人惊讶的是，它运行在单声道2.10.5（即没有堆栈溢出） – 但它需要84秒，即比OCaml – oops慢587倍。
所以这个程序…
- 在OCaml下运行良好
- 在.NET / F＃下不工作
- 工作，但是在Mono / F＃下非常慢。
为什么？
编辑：古怪继续 – 使用“–optimize + –checked-”使问题消失， 但只有在ArchLinux /单声道 ; 在Windows XP和Windows 7 / 64bit下，即使是二进制堆栈的优化版本也会溢出。
最终编辑 ：我自己find答案 – 见下文。
执行摘要：
- 我写了一个algorithm的简单实现…这不是尾recursion的。
- 我在Linux下用OCaml编译它。
- 它工作正常，并在0.14秒完成。
现在是时候去F＃了。
- 我将代码（直接翻译）翻译成F＃。
- 我在Windows下编译并运行它 – 我得到了堆栈溢出。
- 我在Linux下使用二进制文件，并在Mono下运行。
- 它工作，但运行速度很慢（84秒）。
然后我发布到堆栈溢出 – 但有些人决定closures这个问题（叹气）。
- 我试着用–optimize + –checked-
- 在Windows下二进制仍然堆栈溢出…
- …但在Linux / Mono下运行正常（并在0.5秒内完成）。
是时候检查堆栈大小了：在Windows下， 另一个SOpost指出它默认设置为1MB 。 在Linux下，“uname -s”和一个testing程序的编译清楚地表明它是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（很好，对于这个简单的小问题很重要）。
无论如何，要彻底解决这个问题，我写了一个尾recursion版本 – 函数末尾的recursion调用被转换成一个循环（因此，至less在理论上不需要使用堆栈）。
新版本在Windows下运行良好，并在0.5秒内完成。
那么，故事的寓意：
- 注意你的堆栈使用情况，特别是如果你使用了很多，并在Windows下运行。 使用EDITBIN和/ STACK选项来设置你的二进制文件到更大的堆栈大小，或者更好的是用不依赖太多堆栈的方式编写你的代码。
- OCaml在消除尾部recursion方面可能比F＃更好 – 或者垃圾回收器在这个特殊问题上做得更好。
- 不要绝望…closures你的堆栈溢出问题的粗鲁的人，好人最终会抵消他们 – 如果问题真的很好:-)
PS Jon Harrop博士的一些补充意见：
…你真幸运，OCaml也没溢出。 您已经确定实际堆栈大小因平台而异。 同样问题的另一个方面是不同的语言实现以不同的速率吃掉堆栈空间，并且在存在深度堆栈的情况下具有不同的性能特征。 OCaml，Mono和.NET都使用不同的数据表示和GCalgorithm来影响这些结果。（a）OCaml使用带标记的整数来区分指针，给出紧凑的栈帧，并遍历堆栈中的所有指针。 标记本质上为OCaml运行时提供了足够的信息以便能够遍历堆（b）Mono将栈中的单词作为指针保守地处理：如果作为指针，一个单词将指向堆分配的块，那么块被认为是可达的。 （c）我不知道.NET的algorithm，但是如果它更快地读取堆栈空间，并且仍然遍历堆栈中的每个单词（当然，如果不相关的线程有很深的堆栈，它会受到GC的病态性能的影响，我不会感到惊讶）。此外，使用堆分配元组意味着您将快速填充托儿所代（例如gen0），因此导致GC经常遍历那些深度堆栈…
让我试着总结一下答案。
有3点要做：
- 问题：堆栈溢出发生在recursion函数上
- 它只发生在Windows下：在Linux上，对于检查的有问题的大小，它的工作原理
- OCaml中的相同（或类似）代码工作
- 优化+编译器标志，为检查的问题大小，工程
堆栈溢出exception是recursion的结果是很常见的。 如果调用处于尾部位置，编译器可以识别它并应用尾调优化，因此recursion调用不会占用堆栈空间。 Tailcall优化可能发生在F＃，CRL或两者中：
CLR尾部优化1
F＃recursion（更一般） 2
F＃尾调用3
正如其他人所说的，“在windows上不运行，在linux上运行”的正确解释是两个OS上的默认保留堆栈空间。 或者更好的是，这两个操作系统下编译器使用的保留堆栈空间。 默认情况下，VC ++只保留1MB的堆栈空间。 CLR（可能）用VC ++编译，所以它有这个限制。 保留堆栈空间可以在编译时增加，但我不确定是否可以在编译的可执行文件上修改。
编辑：事实certificate，它可以完成（见这个博客文章http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx ）我不会推荐它，但在极端的情况下，至less是可能。
OCaml版本可能工作，因为它在Linux下运行。 但是，在Windows下testingOCaml版本也是很有趣的。 我知道OCaml编译器在尾部调用优化方面比F＃更加激进。它甚至可以从你的原始代码中提取一个可重新引用的函数吗？
我对“–optimize +”的猜测是，它仍然会导致代码重现，因此在Windows下它仍然会失败，但是通过使可执行文件运行得更快来缓解这个问题。
最后，最终的解决scheme是使用尾recursion（通过重写代码或通过实现积极的编译器优化）; 这是避免recursion函数的堆栈溢出问题的好方法。
