Переполнение стека оптимизации рекурсии ES6
Прочитав описание доктора Раушмайера о рекурсивной оптимизации хвостового вызова в es6, я с тех пор пытался воссоздать выполнение "нулевого стека" рекурсивной факториальной функции, которую он детализирует.
Используя отладчик Chrome для перехода между кадрами стека, я вижу, что оптимизация хвоста не происходит, и кадр стека создается для каждой рекурсии.
Я также попытался проверить оптимизацию, вызвав функцию без отладчика, но вместо этого передав 100000 к факториальной функции. Это приводит к ошибке "максимальный стек", что означает, что он на самом деле не оптимизирован.
Вот мой код:
const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )
Результат:
Uncaught RangeError: Maximum call stack size exceeded
2 ответа
V8, движок JavaScript в Chrome, какое-то время имел поддержку TCO, но на этот обновленный ответ (ноябрь 2017 года) он больше не работает, и на момент написания этой статьи не было активной разработки TCO в V8, и ни одна не планируется. Вы можете прочитать подробности в ошибке отслеживания V8.
Поддержка TCO, похоже, достигла достойного уровня в V8 в какой-то момент, но осталась за флагом по нескольким причинам (проблемы отладки, ошибки). Но затем произошло несколько вещей, не в последнюю очередь, что команда V8 подняла значительные проблемы с TCO и решительно поддержала изменение спецификации, называемое синтаксическими хвостовыми вызовами (STC), которое потребовало бы, чтобы хвостовые вызовы были преднамеренно отмечены в исходном коде (например, return continue doThat();). Это предложение стало неактивным в июле 2017 года. Также в июле, когда работа над TCO не проводилась, команда V8 удалила код для поддержки TCO из исходного кода для TurboFan*, так как в противном случае он был бы подвержен битроту. (Например, стать поддерживающей болью и источником ошибок.)
Таким образом, в настоящее время (ноябрь 2017 года) неясно, будет ли когда-нибудь "невидимая" TCO в V8, придут ли какие-то STC или как. Страница состояния платформы Chrome для этого указывает на "смешанные" публичные сигналы от Mozilla (Firefox/SpiderMonkey) и Microsoft (Edge/Chakra) о поддержке TCO, о том, что Safari поставляется с TCO, и что веб-разработчики "положительно" относятся к этой функции. Посмотрим, куда мы пойдем отсюда. Если где угодно.
* (TurboFan = текущий передовой JIT-компилятор в V8, теперь они переключились с Full-Codegen [JIT] + Crankshaft [агрессивная оптимизация JIT] на Ignition [интерпретатор +] и TurboFan [агрессивная оптимизация JIT])
Команда V8 (двигатель JS Chrome) в настоящее время не внедряет TCO. Это вырвано из самых последних версий ( см. Эту ветку).
Из основных браузеров только Safari реализовал эту функцию.
В Node.JS версии 8 и новее TCO недоступен.
Может быть некоторая надежда на внедрение TCO: на недавнем собрании WebAssembly Google и все другие присутствующие группы были нейтральными или позитивными в отношении дальнейшего изучения внедрения TCO.