Резюме:
- Я написал простую реализацию алгоритма ... которая не была хвостовой рекурсивной.
- Я скомпилировал его с OCaml под Linux.
- Он работал нормально и закончил через 0,14 секунды.
Затем пришло время портировать на F #.
- Я перевел код (прямой перевод) на F #.
- Я скомпилировал под Windows и запустил - переполнение стека.
- Я взял бинарный файл под Linux и запустил его под Mono.
- Работает, но работает очень медленно (84 секунды).
Затем я написал в Stack Overflow, но некоторые решили закрыть вопрос (вздох).
- Я попытался скомпилировать с --optimize + --checked-
- Бинарный стек по-прежнему переполнен в Windows ...
- ... но работает нормально (и завершается через 0,5 секунды) под Linux / Mono.
Настало время проверить размер стека: под Windows другой пост SO указал, что по умолчанию он установлен в 1MB . Под Linux "uname -s" и компиляция тестовой программы ясно показали, что это 8 МБ.
Это объясняет, почему программа работала под Linux, а не под Windows (программа использовала более 1 МБ стека). Это не объясняет, почему оптимизированная версия работает намного лучше в Mono, чем неоптимизированная: 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 , чтобы установить в ваших двоичных файлах больший размер стека или, что еще лучше, написать свой код так, чтобы он не зависел от использования слишком большого количества стеков.
- OCaml может быть лучше в устранении хвостовой рекурсии, чем F # - или сборщик мусора справляется с этой конкретной задачей лучше.
- Не отчаивайтесь из-за ... грубых людей, закрывающих ваши вопросы о переполнении стека, хорошие люди в конце концов будут противодействовать им - если вопросы действительно хорошие: -)
P.S. Некоторые дополнительные материалы от доктора Джона Харропа:
... вам просто повезло, что OCaml также не переполнен.
Вы уже определили, что фактические размеры стека варьируются в зависимости от платформы.
Другой аспект той же проблемы заключается в том, что разные языковые реализации
есть место в стеке с разной скоростью и иметь разную производительность
характеристики при наличии глубоких стеков. OCaml, Mono и .NET
все используют разные представления данных и алгоритмы GC, которые влияют
эти результаты ... (а) OCaml использует теговые целые, чтобы различать указатели,
давая компактные кадры стека, и будет проходить все в стеке
ищу указатели. Пометка в основном передает достаточно информации
для времени выполнения OCaml, чтобы иметь возможность пересечь кучу (б) Mono обрабатывает слова
в стеке консервативно как указатели: если в качестве указателя слово будет указывать
в блок, выделенный из кучи, этот блок считается достижимым.
(c) Я не знаю алгоритм .NET, но я не удивлюсь, если он съел стек
пространство быстрее и по-прежнему проходит каждое слово в стеке (это, безусловно,страдает патологическими характеристиками от GC, если неродственный поток имеет
глубокий стек!) ... Более того, использование кортежей, выделенных для кучи, означает, что вы
быстро заполнить детское поколение (например, gen0) и, следовательно,
заставляя GC часто проходить эти глубокие стеки ...