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

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

89 голосов
/ 07 сентября 2010

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

Ответы [ 6 ]

47 голосов
/ 07 сентября 2010

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

http://lambda -the-ultimate.org / узел / 3047

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

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

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

26 голосов
/ 08 мая 2011

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

12 голосов
/ 07 сентября 2010

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

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

9 голосов
/ 23 мая 2016

Оптимизация вызовов в хвосте будет поддерживаться в строгом режиме 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
  • Kinoma XS6

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

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

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

2 голосов
/ 08 ноября 2014

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

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

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

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

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

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

...