Оптимизированы ли хвостовые вызовы движков Javascript?

Question

У меня есть хвостовой рекурсивный алгоритм поиска пути, который я реализовал в Javascript и хотел бы знать, будут ли какие-либо (все?) Браузеры получать исключения переполнения стека.

Answer 1

Спецификация ECMAScript 4 изначально собиралась добавить поддержку TCO, но она была исключена.

http://lambda-the-ultimate.org/node/3047

Насколько я знаю, ни одна из широко распространенных реализаций JS в настоящее время не поддерживает автоматическую TCO. Это может быть полезно для вас, хотя:

http://www.paulbarry.com/articles/2009/08/30/tail-call-optimization

По сути, с помощью шаблона аккумулятора достигается тот же эффект.

Answer 2

На данный момент радости нет, но, к счастью, для Harmony запланированы правильные хвостовые вызовы (ECMAScript version 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Answer 3

Оптимизация вызовов в хвосте будет поддерживаться в строгом режиме ECMAScript 6 в будущем. Проверьте http://www.2ality.com/2015/06/tail-call-optimization.html для деталей.

Проверьте http://kangax.github.io/compat-table/es6/ для текущей поддержки двигателя.

На данный момент (05-01-2018) следующие механизмы поддерживают оптимизацию хвостовых вызовов:

• Safari 10
• iOS 10
• Кинома XS6

поддержка, если включен флаг "Экспериментальные функции JavaScript":

• Узел 6.5
• Chrome 54 / Opera 41 Текущая версия таблицы сравнения больше не содержит ее

Answer 4

Практически каждый браузер, с которым вы столкнетесь, будет "слишком много рекурсии". Вот запись в трекере ошибок V8, которая, вероятно, будет интересно читать.

Если это простая саморекурсия, то, вероятно, стоит усилий использовать явную итерацию, а не надеяться на устранение хвостовых вызовов.

Answer 5

Оптимизация вызова хвоста теперь доступна в LispyScript, который компилируется в javascript. Вы можете прочитать больше об этом здесь.

Answer 6

В настоящее время ни одна реализация JS не распознает хвостовую рекурсию. В ECMAScript 6 вносятся изменения, и, как говорили другие, на V8 есть открытый билет

Здесь вы можете увидеть сгенерированный ассемблер V8 для функции хвостовой рекурсии

https://gist.github.com/mcfedr/832e3553964a014621d5

Сравните это с тем, как clang скомпилировал ту же функцию в C

https://gist.github.com/mcfedr/63ad08370d856bad3694

V8 сохраняет рекурсивный вызов, тогда как компилятор C распознал хвостовую рекурсию и превратил ее в цикл