F # против OCaml: переполнение стека
Я недавно нашел презентацию оF # для программистов на Pythonи, посмотрев его, решил самостоятельно реализовать решение «муравьиной головоломки».
Есть муравей, который может ходить по плоской сетке. Муравей может перемещаться на одну позицию за раз влево, вправо, вверх или вниз. То есть из ячейки (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
Аккуратно, мой результат такой же, как уРеализация Леонардо, в D и C ++, По сравнению с реализацией leonardo C ++, версия OCaml работает примерно в 2 раза медленнее, чем C ++. Что нормально, учитывая, что Леонардо использовал очередь для удаления рекурсии.
После, яперевел код на 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
Удивительно, но это не так, как в Mono 2.10.5 (то есть без переполнения стека) - но это занимает 84 секунды, то есть в 587 раз медленнее, чем OCaml - упс.
Итак, эта программа ...
отлично работает под OCamlне работает вообще под .NET / F #работает, но очень медленно, под Mono / F #.Почему?
РЕДАКТИРОВАТЬ: Странность продолжается - использование «--optimize + --checked-» устраняет проблему,но только под ArchLinux / Mono ; в Windows XP и Windows 7 / 64bit даже оптимизированная версия двоичного стека переполняется.
Окончательное редактированиеЯ сам узнал ответ - см. Ниже.