ibessonov Mar 12 2017 at 20:37

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

5 min

24K

Java*Functional Programming*

+36

Comments 12

igor_suhorukov Mar 13 2017 at 00:46

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

Вы ее убили?!

-1

senia Mar 13 2017 at 10:03

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

potan Mar 13 2017 at 15:12

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

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

ibessonov Mar 13 2017 at 15:51

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

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

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

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

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

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

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

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

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

dougrinch Mar 13 2017 at 15:21

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

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

Все ок, production ready.

ibessonov Mar 13 2017 at 15:53

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

Nikelandjelo Mar 13 2017 at 17:34

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

ibessonov Mar 13 2017 at 17:46

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

vba Mar 13 2017 at 20:10

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

senia Mar 13 2017 at 22:30

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

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

Beholder Mar 13 2017 at 23:10

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

vba Mar 13 2017 at 23:38

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

Show the best of all time