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.
There is an ant that can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from the cell (x, y) the ant can go to cells (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the x and y coordinates are greater than 25 are inaccessible to the ant. For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25. The question is: How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?
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
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.
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
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
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.
So this program...
Why?
EDIT: 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.
Executive summary:
It was then time to port to F#.
I then posted to Stack Overflow - but some people decided to close the question (sigh).
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.
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.
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).
The new version run fine under Windows as well, and finished in 0.5 seconds.
So, moral of the story:
P.S. Some additional input from Dr. Jon Harrop:
...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...