Оптимизация хвостовой рекурсии в Java

[igor_suhorukov]

В IntelliJ IDEA таких методов нашлось не меньше десятка, но при этом приложение аварийно завершило свою работу.

Вы ее убили?!

[senia]

Я года 3 назад разбирал как работает оптимизация хвостовых рекурсивных вызовов в scala на jvm. Может пригодиться.

[potan]

Оптимизация хвостовой рекурсии может делаться не только переходом на начало функции. Более общий случай (оптимизация хвостовых вызовов) — это специальная команда или распознавания jit-ом последовательности INVOKE* RETURN, которая сначала разрушает старый фрейм стека, а только потом создает новый. Проблема с полиморфизмом исчезает. Проблема с исключениями остается, но на мой взгляд она несущественна, в нормально написанной программе не должна влиять на логику и может лишь слегка затруднить отладку.

Но в JVM есть более серьезное возражение — модель безопасности. Права на различные действия в JVM ограничиваются по всем классам, присутствующих в стеке вызова и такая оптимизация потенциально может позволить зловредному коду вызвать не положенную ему функцию. С этим бороться значительно сложнее.

[ibessonov]

Спасибо за развёрнутый комментарий! У меня есть к нему несколько замечаний:

Проблема с исключениями остается, но на мой взгляд она несущественна

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

Оптимизация хвостовой рекурсии может делаться не только переходом на начало функции

Странно, среде выполнения ведь всё равно надо будет начать выполнение функции с первой команды независимо от того, был кадр стэка пересоздан или нет.

Проблема с полиморфизмом исчезает

Решение проблемы с полиморфизмом, предложенное вами, уже не имеет к хвостовой рекурсии никакого отношения, но да, такой подход в принципе реализуем. Насколько я понимаю, JIT делает что-то очень похожее с помощью инлайна методов.

такая оптимизация потенциально может позволить зловредному коду вызвать не положенную ему функцию

С этим я не согласен. В стэке вызовов мы заменяем цепочку одинаковых классов на единичный элемент. AccessControlContext это затронуть не должно.

[dougrinch]

но при этом приложение аварийно завершило свою работу

и

без нарушения семантики

Все ок, production ready.

[ibessonov]

В теории нарушения семантики не должно быть. На практике же всё немного сложнее — ошибка либо у меня, либо у IDEA, и тут я не знаю точного ответа.

[Nikelandjelo]

Я никогда не понимал почему хвостовая рекурсия так важна. В обычном проекте рекурсивные функции не так уж и часто встречаются. И создание нового кадра стека дешевая операция. Если уж действительно кусок кода, который рекурсивный и критичный по производительности, то можно и руками оптимизировать. А так правильный стек кажется куда важнее, плюс легче словить бесконечный цикл: без хвостовой рекурсии все свалится с StackOverflow, а с ней поток честно зависнет и фиг отдебажишь.

[ibessonov]

Сама по себе хвостовая рекурсия важна для функциональных языков, где циклов нет как таковых.
Что же касается нефункциональных языков — согласитесь, гораздо приятнее, когда оптимизациями занимается компилятор, а не программист. Плюс рекурсивный код зачастую выглядит красивее и более естественно, чем аналогичный итеративный (как пример — реализация gcd из поста, если из неё выкинуть try/catch, ну или метод add из самого начала).

[vba]

Если вы работаете с неизменяемыми структурами данных и особенно с коллекциями ХР архи удобна.

[senia]

В обычном проекте рекурсивные функции не так уж и часто встречаются.

Именно потому, что нет оптимизации хвостовых рекурсивных вызовов.
Любой ФП код при наличии такой оптимизации просто кишит рекурсивными методами.

[Beholder]

IntelliJ IDEA собираются постепенно переписывать на Kotlin, а там такая рекурсия уже «из коробки».

[vba]

Да но скорее всего основная причина переписки заключается в том что IntelliJ core написан на java 6