F#vs OCaml:堆栈溢出 [英] F# vs OCaml: Stack overflow

问题描述

我最近找到了一个有关针对Python程序员的F#的演示文稿，看完之后，我决定自己实施蚂蚁拼图"的解决方案.

I recently found a presentation about F# for Python programmers, and after watching it, I decided to implement a solution to the "ant puzzle" on my own.

有一只蚂蚁可以在平面网格上四处走动.蚂蚁可以一次向左，向右，向上或向下移动一个空间.也就是说，蚂蚁可以从单元格(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中实现了解决方案，然后进行了尝试:

I implemented my solution in 30 lines of OCaml first, and tried it out:

$ 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使用队列删除了递归，这没关系.

Neat, my result is the same as that of leonardo's implementation, in D and C++. Comparing to Leonardo's C++ implementation, the OCaml version runs approx 2 times slower than C++. Which is OK, given that Leonardo used a queue to remove recursion.

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

I then translated the code to F# ... and here's what I got:

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下运行:

Stack overflow... with both versions of F# I have in my machine... Out of curiosity, I then took the generated binary (ant.exe) and run it under 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倍-哎呀.

Surprisingly, it runs under Mono 2.10.5 (i.e. no stack overflow) - but it takes 84 seconds, i.e. 587 times slower than OCaml - oops.

所以这个程序...

• 在OCaml下运行良好
• 在.NET/F#下根本无法工作
• 可以正常工作，但是在Mono/F#下非常慢.

为什么?

古怪继续-使用"--optimize + --checked-"使问题消失，但仅在ArchLinux/Mono下；在Windows XP和Windows 7/64bit下，甚至二进制堆栈的优化版本也会溢出.

Weirdness continues - Using "--optimize+ --checked-" makes the problem disappear, but only under ArchLinux/Mono ; under Windows XP and Windows 7/64bit, even the optimized version of the binary stack overflows.

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

Final EDIT: I found out the answer myself - see below.

推荐答案

执行摘要:

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

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

It was then time to port to F#.

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

然后我发布了Stack Overflow-但有些人决定结束这个问题(叹气).

I then posted to Stack Overflow - but some people decided to close the question (sigh).

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

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

It was time to check the stack size: Under Windows, another SO post pointed out that it is set by default to 1MB. Under Linux, "uname -s" and a compilation of a test program clearly showed that it is 8MB.

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

This explained why the program worked under Linux and not under Windows (the program used more than 1MB of stack). It didn't explain why the optimized version run so much better under Mono than the non-optimized one: 0.5 seconds vs 84 seconds (even though the --optimize+ appears to be set by default, see comment by Keith with "Expert F#" extract). Probably has to do with the garbage collector of Mono, which was somehow driven to extremes by the 1st version.

Linux/OCaml和Linux/Mono/F#执行时间之间的差异(0.14 vs 0.5)是因为我测量它的简单方法:"time ./binary ..."也测量了启动时间，即对于Mono/.NET来说意义重大(嗯，对于这个简单的小问题意义重大).

The difference between Linux/OCaml and Linux/Mono/F# execution times (0.14 vs 0.5) is because of the simple way I measured it: "time ./binary ..." measures the startup time as well, which is significant for Mono/.NET (well, significant for this simple little problem).

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

Anyway, to solve this once and for all, I wrote a tail-recursive version - where the recursive call at the end of the function is transformed into a loop (and hence, no stack usage is necessary - at least in theory).

新版本也可以在Windows下正常运行，并在0.5秒内完成.

The new version run fine under Windows as well, and finished in 0.5 seconds.

所以，故事的寓意是

• 当心您的堆栈使用情况，尤其是当您使用大量堆栈并在Windows下运行时.将 EDITBIN与/STACK选项一起使用将您的二进制文件设置为更大的堆栈大小，或者更好的是，以不依赖于使用过多堆栈的方式编写代码.
• OCaml在消除尾递归方面可能比F#更好-或者它的垃圾收集器在解决此特定问题方面做得更好.
• 不要对...粗鲁的人关闭您的Stack Overflow问题感到绝望，如果问题真的很好，好人最终将抵消他们的烦恼:-)

• Beware of your stack usage, especially if you use lots of it and run under Windows. Use EDITBIN with the /STACK option to set your binaries to larger stack sizes, or better yet, write your code in a manner that doesn't depend on using too much stack.
• OCaml may be better at tail-recursion elimination than F# - or it's garbage collector is doing a better job at this particular problem.
• Don't despair about ...rude people closing your Stack Overflow questions, good people will counteract them in the end - if the questions are really good :-)

P.S.乔恩·哈罗普(Jon Harrop)博士的一些补充意见:

...您很幸运，OCaml也没有溢出. 您已经确定实际的堆栈大小在平台之间有所不同. 同一问题的另一个方面是不同的语言实现 以不同的速度吃掉堆栈空间并具有不同的性能 深堆存在时的特征. OCaml，Mono和.NET 都使用不同的数据表示和GC算法来影响 这些结果...(a)OCaml使用带标记的整数来区分指针， 提供紧凑的堆栈框架，并将遍历堆栈上的所有内容 寻找指针.标记实质上传达了足够的信息 使OCaml运行时能够遍历堆(b)Mono对待单词 在栈上保守地作为指针:如果作为指针，一个单词会指向 放入堆分配的块中，则认为该块是可到达的. (c)我不知道.NET的算法，但是如果它吃了堆栈，我不会感到惊讶 速度更快，但仍然遍历堆栈中的每个单词(当然 如果不相关的线程具有 更深的堆栈！)...此外，使用堆分配的元组意味着您将 快速填充育苗代(例如gen0)，因此， 导致GC经常遍历这些深层堆栈...

...you were just lucky that OCaml didn't overflow as well. You already identified that actual stack sizes vary between platforms. Another facet of the same issue is that different language implementations eat stack space at different rates and have different performance characteristics in the presence of deep stacks. OCaml, Mono and .NET all use different data representations and GC algorithms that impact these results... (a) OCaml uses tagged integers to distinguish pointers, giving compact stack frames, and will traverse everything on the stack looking for pointers. The tagging essentially conveys just enough information for the OCaml run time to be able to traverse the heap (b) Mono treats words on the stack conservatively as pointers: if, as a pointer, a word would point into a heap-allocated block then that block is considered to be reachable. (c) I do not know .NET's algorithm but I wouldn't be surprised if it ate stack space faster and still traversed every word on the stack (it certainly suffers pathological performance from the GC if an unrelated thread has a deep stack!)... Moreover, your use of heap-allocated tuples means you'll be filling the nursery generation (e.g. gen0) quickly and, therefore, causing the GC to traverse those deep stacks often...

这篇关于F#vs OCaml:堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！