F＃VS OCaml的：堆棧溢出

Question

我最近發現一個演示約F# for Python programmers，並觀看後，決定實施一個解決方案，我自己的「蟻族之謎」。

沒有可走動在平面網格的螞蟻。螞蟻可以一次向左，向右，向上或向下移動一個空間。也就是說，從細胞（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）本身？

我實現了我的解決方案中的OCaml first 30日線，並嘗試過了：

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

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

整潔，我的結果是一樣的，即leonardo's implementation, in D and C++。與leonardo的C++實現相比，OCaml版本的運行速度比C++慢大約2倍。這是可以的，因爲萊昂納多使用隊列來消除遞歸。

然後我translated the code to 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秒，即慢於587倍OCaml - 哎呀。

所以這個程序...

• 運行OCaml的
• 下罰款不工作在所有的.NET下/ F＃
• 作品，但速度很慢，下單聲道/ F＃。

爲什麼？

編輯：怪誕繼續 - 使用 「--optimize + --checked-」 使問題消失，但只下的ArchLinux /單聲道;在Windows XP和Windows 7/64bit下，即使是二進制堆棧的優化版本也會溢出。

最終剪輯：我找到了自己的答案 - 見下文。

Answer 1

內容提要：

• 我寫了一個簡單的實現算法的...這是不是尾遞歸。
• 我在Linux下用OCaml編譯它。
• 它工作正常，並在0.14秒內完成。

然後是時候移植到F＃。

• 我將代碼（直接翻譯）翻譯成F＃。
• 我在Windows下編譯並運行它 - 我得到了堆棧溢出。
• 我在Linux下使用了二進制文件，並在Mono下運行它。
• 它工作，但運行非常緩慢（84秒）。

然後我發佈到堆棧溢出 - 但有些人決定關閉這個問題（嘆氣）。

• 我試着用--optimize + --checked-
• Linux下的二進制文件在Windows下仍然棧溢出...
• ...但運行良好（並在0.5秒內完成）/單聲道編譯。

是時候檢查堆棧大小：在Windows下，another SO post pointed out that it is set by default to 1MB。在Linux下，「uname -s」和a compilation of a test program清楚地表明它是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很重要（對於這個簡單的小問題來說很重要）。

無論如何，要徹底解決這個問題，我在wrote a tail-recursive version - 函數末尾的遞歸調用被轉換爲循環（因此，至少在理論上不需要使用堆棧）。

新版本在Windows下運行良好，並在0.5秒內完成。

所以，這個故事的寓意是：

• 當心你的堆棧使用的，特別是如果你使用它的地段和Windows下運行。使用EDITBIN with the /STACK option可將您的二進制文件設置爲更大的堆棧大小，或者更好的是，以不依賴於使用太多堆棧的方式編寫代碼。
• OCaml在尾部遞歸消除方面可能比F＃更好 - 或者它的垃圾回收器在這個特殊問題上做得更好。
• 不在約......粗魯的人關閉您的堆棧溢出的問題感到絕望，善良的人們將抵消他們到底 - 如果問題真的很不錯:-)

附： Jon Harrop博士的一些額外的輸入：

......你真是幸運，OCaml也沒有溢出。 您已經確定實際堆棧大小因平臺而異。 同一問題的另一個方面是不同的語言實現 以不同的速率吃掉堆棧空間並且在存在深度堆棧的情況下具有不同的性能 特性。 OCaml，Mono和。（a）OCaml使用標記的整數來區分指針， 給出緊湊的棧幀，並且將遍歷堆棧中的所有內容，尋找指針。標記實質上傳達了OCaml運行時間的足夠信息，以便能夠遍歷堆（b）Mono保守地將棧上的詞 作爲指針處理：如果作爲指針，詞將 指向堆分配塊，那麼該塊被認爲是可達的。 （c）我不知道.NET的算法，但我不會感到驚訝，如果它快速地堆棧 空間並且仍然遍歷堆棧中的每個單詞（當然，如果不相關的線程有 ，那麼它會遭受來自GC的病態性能的 ）... ...此外，您使用堆分配元組意味着您將快速填充幼兒園代（例如gen0），因此， 會導致GC經常遍歷那些深度堆棧...

Answer 2

讓我試着總結了答案。

有3點進行：

• 問題：堆棧溢出發生在一個遞歸函數
• 它只會發生在Windows：在Linux上，對檢查proble大小，它的工作原理
• 相同（或相似）OCaml中代碼工作
• 優化+編譯器標誌，用於檢查的proble大小，工作

堆棧溢出異常是遞歸的結果是非常常見的。如果調用處於尾部位置，編譯器可能會識別它並應用尾調優化，因此遞歸調用不會佔用堆棧空間。 尾調用優化可能發生在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下失敗，但會通過使可執行文件運行速度更快緩解這個問題。最後，最終的解決方案是使用尾遞歸（通過重寫代碼或通過在激進的編譯器優化上實現）;這是避免遞歸函數的堆棧溢出問題的好方法。