F# vs OCaml: переполнение стека

резюме:

• Я написал простую реализацию алгоритма... это не хвост-рекурсивный.
• я скомпилировал его с OCaml под Linux.
• Он работал нормально, а закончил в 0,14 секунды.

Это было тогда время для порта на F#.

• Я перевел код (прямой перевод) для F#.
• я скомпилировал под Windows, и запустить его - я получил переполнение стека.
• Я взял на бинарных под Linux, и запустить его под моно.
• это сработало, но работает очень медленно (84 секунды).

Я тогда написал в Stack Overflow-но некоторые люди решили закрыть вопрос (вздох).

• Я пробовал компилировать с --optimize+ -- checked -
• двоичный стек все еще переполнен под окнами...
• ...но запустите нормально (и закончите через 0,5 секунды) под Linux/Mono.

пришло время проверить размер стека: под Окна,еще один пост SO указал, что по умолчанию он установлен на 1MB. Под Linux, "uname-s" и компиляция тестовой программы ясно показал, что это 8 МБ.

это объясняло, почему программа работала под Linux, а не под Windows (программа использовала более 1 МБ стека). Это не объяснило, почему оптимизированная версия работает намного лучше под моно, чем неоптимизированная: 0,5 секунды против 84 секунд (хотя кажется, что --optimize+ установите по умолчанию, см. комментарий кита с извлечением " Expert F#"). Вероятно, это связано с сборщиком мусора Mono, который каким-то образом был доведен до крайности 1-й версией.

разница между Linux / OCaml и Linux/Mono / F# время выполнения (0,14 против 0,5) из-за простого способа я измерил его: "время ./двоичный. .."также измеряет время запуска, что важно для Mono/.NET (ну, важно для этой простой маленькой проблемы).

в любом случае, чтобы решить это раз и навсегда, я написал хвост-рекурсивную версию - где рекурсивный вызов в конце функции преобразуется в цикл (и, следовательно, использование стека не требуется - по крайней мере, в теории).

новая версия работает нормально под Windows, а также, и закончил в 0.5 секунд.

Итак, мораль истории:

• остерегайтесь использования стека, особенно если вы используете его много и работаете под Windows. Используйте EDITBIN с помощью / STACK option чтобы установить двоичные файлы на большие размеры стека, или еще лучше, напишите свой код таким образом, который не зависит от использования слишком большого стека.
• OCaml может быть лучше при устранении хвостовой рекурсии, чем F# - или это сборщик мусора делает лучшую работу в этой конкретной проблеме.
• не отчаивайтесь ...грубые люди закрывают ваши вопросы переполнения стека, хорошие люди будут противодействовать им в конце концов - если вопросы действительно хороши : -)

P.S. Некоторые дополнительные данные от доктора Джона Харропа:

...вам просто повезло,что OCaml не переполнялся. Вы уже определили, что фактические размеры стека различаются между платформами. Другой аспект той же проблемы заключается в том, что разные языковые реализации ешьте пространство стека с разной скоростью и имеют разную производительность характеристики при наличии глубоких стеков. Данные, используемые, моно .Чистая все используют разные данные представления и алгоритмы GC, которые влияют результаты исследования... (A) OCaml использует помеченные целые числа для различения указателей, давая компактные рамки стека, и будет пересекать все на стеке ищу указатели. Пометка по существу передает только достаточно информации для времени выполнения OCaml, чтобы иметь возможность пересекать кучу (b) Mono обрабатывает слова на стеке консервативно как указатели: если, как указатель, слово будет указывать в выделенный кучей блок, то этот блок считается достижимый. (c) я не знаю алгоритм .NET, но я не удивлюсь, если он съел стек пространство быстрее и все еще проходило каждое слово в стеке (это, конечно страдает патологической производительностью от GC, если несвязанный поток имеет глубокая стопка!)... Кроме того, использование выделенных кучами кортежей означает, что вы будете заполнять поколение питомника (например, gen0) быстро и поэтому, вызывая сборщик мусора, чтобы пройти эти глубокие стеки часто...