F＃vs OCaml：堆栈溢出

 

我最近为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倍。 这是可以的，因为莱昂纳多使用队列来消除递归。

然后我将代码翻译成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

令人惊讶的是，它运行在单声道2.10.5（即没有堆栈溢出） - 但它需要84秒，即比OCaml-oops慢587倍。

所以这个程序...

  • 在OCaml下运行良好
  • 在.NET / F＃下无法正常工作
  • 工作，但在Mono / F＃下非常缓慢。

    • 为什么？

    编辑：古怪继续 - 使用“--optimize + --checked-”使问题消失， 但只在ArchLinux / Mono下 ; 在Windows XP和Windows 7 / 64bit下，即使是二进制堆栈的优化版本也会溢出。

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

    执行摘要：

  • 我写了一个简单的算法实现......这不是尾递归的。
  • 我在Linux下用OCaml编译它。
  • 它工作正常，并在0.14秒内完成。

    • 现在是时候转移到F＃。

  • 我将代码（直接翻译）翻译成F＃。
  • 我在Windows下编译并运行它 - 我得到了堆栈溢出。
  • 我在Linux下使用了二进制文件，并在Mono下运行它。
  • 它工作，但运行速度很慢（84秒）。

    • 然后我发布到堆栈溢出 - 但有些人决定关闭这个问题（叹气）。

  • 我试着用--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下运行。 使用EDITBIN和/ STACK选项将二进制文件设置为更大的堆栈大小，或者更好的是，以不依赖于使用太多堆栈的方式编写代码。
  • OCaml在尾部递归消除方面可能比F＃更好 - 或者它的垃圾回收器在这个特殊问题上做得更好。
  • 不要对......粗鲁的人关闭Stack Overflow问题感到绝望，好人最终会抵消他们 - 如果问题真的很好:-)

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

    ......你真幸运，OCaml也没有溢出。 您已经确定实际堆栈大小因平台而异。 同样问题的另一个方面是，不同的语言实现以不同的速率吃掉堆栈空间，并且在存在深度堆栈的情况下具有不同的性能特征。 OCaml，Mono和.NET都使用不同的数据表示和GC算法来影响这些结果......（a）OCaml使用带标记的整数来区分指针，给出紧凑的堆栈帧，并遍历堆栈中的所有内容以查找指针。 标记本质上为OCaml运行时提供了足够的信息以便能够遍历堆（b）Mono将栈中的单词作为指针保守地处理：如果作为指针，一个单词将指向堆分配块，那么块被认为是可达的。 （c）我不知道.NET的算法，但是如果它更快地读取堆栈空间并且仍然遍历堆栈中的每个单词（当然，如果不相关的线程具有深度堆栈，它会受到GC的病态性能的影响，我不会感到惊讶）。 ...此外，使用堆分配元组意味着您将快速填充幼儿园代（例如gen0），因此，GC经常会遍历那些深度堆栈...

    让我试着总结答案。

    有3点要做：

  • 问题：堆栈溢出发生在递归函数上
  • 它只发生在windows下：在linux上，为了检查有问题的大小，它工作
  • OCaml中的相同（或类似）代码工作
  • 优化+编译器标志，对于检查的有问题的大小，起作用

    • 堆栈溢出异常是递归的结果是非常常见的。 如果调用处于尾部位置，编译器可能会识别它并应用尾调优化，因此递归调用不会占用堆栈空间。 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下它仍然会失败，但是通过使可执行文件运行得更快来缓解这个问题。

    最后，最终的解决方案是使用尾递归（通过重写代码或通过实现积极的编译器优化）; 这是避免递归函数的堆栈溢出问题的好方法。

    链接地址: http://www.djcxy.com/p/80551.html

    上一篇: F# vs OCaml: Stack overflow

    下一篇: F# Create Factorial function without recursion, library functions or loops