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

    Уже давно определённые вещи из мира функционального программирования всё сильнее проникают в нефункциональные языки. Может показаться странным, что в Java смогли интегрировать лямбда-выражения, а вот оптимизацию хвостовой рекурсии (преобразование рекурсии в эквивалентный цикл) до сих пор не сделали, хотя она гораздо проще. Почему её нет?

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

    В первую очередь, пример. Предлагаю не мучить в этот раз несчастный факториал и использовать другую функцию:

    static int add(int x, int y) {
        if (y == 0) return x;
        return add(x ^ y, (x & y) << 1);
    }
    

    Это рекурсивный способ сложения 2-х целых чисел. Он подходит под определение хвостовой рекурсии: за каждым рекурсивным вызовом непосредственно следует операция return. Оптимизация заключается в том, чтобы при рекурсивном вызове не создавать новый кадр стэка, а переиспользовать текущий. Для этого нужно новые параметры положить на место старых и выполнить безусловный переход на первую инструкцию метода. В псевдокоде это будет выглядеть так:

    static int add(int x, int y) {
        start: {
            if (y == 0) return x;
            (x, y) = (x ^ y, (x & y) << 1);
            goto start;
        }
    }
    

    Далее возможны различные стилистические вариации, но в целом код после ручной оптимизации станет таким (можно и красивее, многословность тут лишь для ясности):

    static int add(int x, int y) {
        while (true) {
            if (y == 0) return x;
            int _x = x ^ y;
            int _y = (x & y) << 1;
            x = _x;
            y = _y;
        }
    }
    

    Сразу становится очевидным минус ручной оптимизации хвостовой рекурсии: код становится страшнее, особенно если рекурсивных вызовов более одного. Очень хочется, чтобы оптимизация производилась автоматически.

    И всё было бы хорошо, но есть одно НО: оптимизация ломает семантику выполнения программы. Всё потому, что в Java в любой точке кода доступна информация о стэке вызовов. И если в случае инлайна методов JIT ещё способен сам всё разрулить, то при замене рекурсивного вызова на GOTO мы теряем множество кадров стэка с информацией о точках входа, которая должна у нас быть по спецификации.

    Это неприятно и говорит о том, что, скорее всего, этой оптимизации в Java мы не увидим.

    Чтобы продолжить исследование, смиримся с тем, что из stacktrace пропадут несколько строк. Предположим, что выигрыш по быстродействию (или красоте кода) важнее. Определим другие факторы, которые могут помешать оптимизации:

    • полиморфизм:

      для того, чтобы осуществить GOTO, нужно точно знать, что по факту должен вызываться тот же метод. Это требование выполнено для:

      — статических методов;
      — приватных методов;
      — методов final классов;
      — явных вызовов invokespecial. Данный вариант не может быть создан компилятором из исходного Java кода, так как invokespecial доступен только для вызова методов суперкласса.

    • исключения:

      если вдруг рекурсивный вызов происходит внутри try блока, то мы не можем просто так взять и передать управление инструкции вне этого самого блока. Вот пример:

      static int f(boolean shouldThrow) {
          if (shouldThrow) throw new RuntimeException();
          try {
              f(!shouldThrow);
          } catch (Exception e) {
          }
          return -1;
      }
      

      Вызов f(false) должен возвратить -1, но если сделать GOTO в месте рекурсивного вызова, то мы получим RuntimeException, а это явно отличается от того, что должно происходить при корректной оптимизации.

    Есть минимум 2 проверенных способа модифицировать байткод Java-классов:

    • препроцессор — встраивается в компилятор, изменения байткода попадут в class файлы;
    • инструментатор — встраивается в ClassLoader, изменения будут видны только в рантайме.

    Я выбрал второй вариант и написал простенький Java Agent, оптимизирующий хвостовую рекурсию. Он сможет провести оптимизацию только при выше описанных условиях:
    • static method / final method / final class;
    • рекурсивные вызовы находятся вне try блоков.

    Для нетерпеливых ссылка на github: github.com/ibessonov/java-tailrec-agent.
    Там настроенный IDEA проект, в котором есть примеры, чтобы с ними поиграться. А для терпеливых — небольшое пояснение на примере.

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

    static int gcd(int n, int m) {
        try {
            if (m == 0) return n;
        } catch (Throwable t) {
            // do nothing
        }
        return gcd(m, n % m);
    }
    

    После компиляции метод будет выглядеть следующим образом (упрощено для читаемости, часть информации намеренно опущена):

    static gcd(II)I
        TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable
    TryBlockStart:
        ILOAD 1
        IFNE ElseBlock
        ILOAD 0
    TryBlockEnd:
        IRETURN
    CatchBlockStart:
        ASTORE 2 // сохранение исключения во временную переменную - дефолтный пустой обработчик
    ElseBlock:
        ILOAD 1
        ILOAD 0
        ILOAD 1
        IREM
        INVOKESTATIC Main.gcd(II)I
        IRETURN
    

    Каждый метод содержит в себе массив описаний try блоков. У каждого описания есть 4 составляющих: метка начала блока, метка конца блока, метка обработчика исключения и дескриптор класса исключения. Эта информация позволяет нам однозначно определить инструкции, находящиеся внутри try блоков, и не производить для них оптимизацию.

    Далее нужно найти все инструкции INVOKE* с дескриптором метода, совпадающим с самим методом (в данном случае ищется дескриптор gcd(II)I метода класса Main), за которыми непосредственно находится инструкция типа RETURN.

    Найденный INVOKESTATIC надо преобразовать из вызова в безусловный переход. Известно, что в момент вызова на стэке находятся все параметры. Для статических методов всё просто, нужно сохранить эти параметры обратно в локальные переменные и сделать безусловный переход в самое начало:

    static gcd(II)I
        TRYCATCHBLOCK TryBlockStart TryBlockEnd CatchBlockStart java/lang/Throwable
    StartLabel:
    TryBlockStart:
        ILOAD 1
        IFNE ElseBlock
        ILOAD 0
    TryBlockEnd:
        IRETURN
    CatchBlockStart:
        ASTORE 2
    ElseBlock:
        ILOAD 1
        ILOAD 0
        ILOAD 1
        IREM
    
        ISTORE 1
        ISTORE 0
        GOTO StartLabel
    

    Для нестатических методов встаёт одна интересная проблема: метод вызывается на объекте, который, вообще говоря, не обязан совпадать с this. Технически возможно найти в байткоде место вычисления этого объекта и проводить оптимизацию только тогда, когда это вычисление равно ALOAD 0.

    Я же поступил лениво и уже вычисленное значение нужного класса сохранил вместо текущего this (сделав ASTORE 0). Как ни странно, такой подход работает, но я, в силу недостаточности знаний, не могу гарантировать, что JIT в этой ситуации будет вести себя корректно. Хотел бы узнать ответ в комментариях — есть ли тут какие-нибудь риски.

    Помимо простых тестов я пробовал подключить агент к существующим приложениям. В Tomcat не нашлось ни одного метода, в котором можно было бы произвести оптимизацию. В IntelliJ IDEA таких методов нашлось не меньше десятка, но при этом приложение аварийно завершило свою работу. Учитывая наличие нескольких агентов и сложную логику работы загрузчиков классов в IDEA, я не рискну говорить, что пошло не так.

    В результате написан инструмент, производящий оптимизацию хвостовой рекурсии во всех методах, где это возможно сделать без нарушения семантики (за исключением модификации стэка вызовов). Из очевидных минусов можно отметить усложнение отладки. С другой стороны, отладку всегда можно произвести и при выключенном агенте.

    Стоит ли им где-то пользоваться — решать только вам.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 12

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

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

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

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


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

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


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

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


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

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


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

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

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

            и


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

            Все ок, production ready.

              +2

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

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

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

                  +2

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

                    0
                    В обычном проекте рекурсивные функции не так уж и часто встречаются.
                    Именно потому, что нет оптимизации хвостовых рекурсивных вызовов.
                    Любой ФП код при наличии такой оптимизации просто кишит рекурсивными методами.
                    0
                    IntelliJ IDEA собираются постепенно переписывать на Kotlin, а там такая рекурсия уже «из коробки».
                      0

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

                    Only users with full accounts can post comments. Log in, please.