Почему JVM все еще не поддерживает оптимизацию хвостового вызова?

Спустя два года после оптимизаций по методу " jvm-предотвращение хвоста", похоже, есть реализация прототипа, и MLVM уже некоторое время перечисляет эту функцию как "прото-80%".

Нет ли какой-либо активной заинтересованности со стороны Sun /Oracle в поддержке хвостовых вызовов или просто хвостовые вызовы "[...] обречены занимать второе место в каждом списке приоритетов функций [...]", как упоминалось в JVM Языковой саммит?

Мне было бы очень интересно, если бы кто-то протестировал сборку MLVM и мог бы поделиться некоторыми впечатлениями о том, насколько хорошо она работает (если вообще).

Обновление: обратите внимание, что некоторые виртуальные машины, такие как Avian, поддерживают правильные хвостовые вызовы без каких-либо проблем.

Источник

5 ответов

Решение

Диагностика кода Java. Повышение производительности вашего кода Java ( alt) объясняет, почему JVM не поддерживает оптимизацию хвостового вызова.

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

Затем приводится пример кода Java, который не будет трансформироваться.

Итак, как показывает пример в листинге 3, мы не можем ожидать, что статические компиляторы будут выполнять преобразование хвостовой рекурсии в коде Java, сохраняя семантику языка. Вместо этого мы должны полагаться на динамическую компиляцию с помощью JIT. В зависимости от JVM, JIT может или не может сделать это.

Затем он дает тест, который вы можете использовать, чтобы выяснить, делает ли это ваш JIT.

Естественно, поскольку это документ IBM, он включает в себя плагин:

Я запустил эту программу с парой Java SDK, и результаты оказались удивительными. Работа на Sun Hotspot JVM для версии 1.3 показывает, что Hotspot не выполняет преобразование. При настройках по умолчанию, пространство стека исчерпывается менее чем за секунду на моем компьютере. С другой стороны, IBM JVM для версии 1.3 без проблем мурлыкает, указывая на то, что он преобразует код таким образом.

Источник

Одна из причин, по которым я видел в прошлом неиспользование TCO (и это воспринималось как сложное) в Java, заключается в том, что модель разрешений в JVM чувствительна к стеку и, следовательно, вызовы tail должны обрабатывать аспекты безопасности.

Я полагаю, что Клементс и Феллайзен [1] [2] показали, что это не является препятствием, и я вполне уверен, что патч MLVM, упомянутый в вопросе, касается и этого.

Я понимаю, что это не отвечает на ваш вопрос; просто добавляю интересную информацию.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
Источник

Возможно, вы уже знаете это, но эта функция не так тривиальна, как может показаться, поскольку язык Java фактически предоставляет трассировку стека программисту.

Рассмотрим следующую программу:

public class Test {

    public static String f() {
        String s = Math.random() > .5 ? f() : g();
        return s;
    }

    public static String g() {
        if (Math.random() > .9) {
            StackTraceElement[] ste = new Throwable().getStackTrace();
            return ste[ste.length / 2].getMethodName();
        }
        return f();
    }

    public static void main(String[] args) {
        System.out.println(f());
    }
}

Даже при том, что это имеет "хвостовой вызов", это не может быть оптимизировано. (Если он оптимизирован, он все равно требует учета всего стека вызовов, так как семантика программы зависит от него.)

По сути, это означает, что трудно поддерживать это, все еще будучи обратно совместимым.

Источник

Java - это наименее функциональный язык, который вы могли бы себе представить (ну, хорошо, возможно, нет!), Но это было бы большим преимуществом для языков JVM, таких как Scala.

Мои наблюдения заключаются в том, что превращение JVM в платформу для других языков никогда не занимало верхних строчек в списке приоритетов для Sun, и, я полагаю, теперь для Oracle.

Источник

Это не проблема Java... это одна из JVM. Java — это просто прадедушка среди языков JVM.

Создание TCO - это переход к следующему кадру стека при удалении текущего, между запущенной программой и текущим стеком, вызывающим переменные, должно быть где-то еще... ;)

Лучшим способом было бы иметь новый специальный код операции вызова для вызова перехода в других кадрах, который делает материал. Они уже сделали это для виртуального звонка. На самом деле это не проблема в интерпретации, JIT, возможно, поднимает другие проблемы, а JVM достаточно раздута.

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

Ах! Если Рич Хикки добавил (повторяющийся...) материал (это не функция), то это из-за отсутствия реальной совокупной стоимости владения, он не хочет, чтобы люди думали, что она есть. Он мог очень легко сделать автоматический TCO во внутреннем звонке. Это также помогает обнаруживать плохие хвостовые вызовы, которые не находятся в хвостовой позиции.

Есть также (трамплин...) материал для внешней TCO, но он беспорядочный (как батут) и почти не используется, за исключением ужасных ситуаций со стеком.

Но да, многие ВМ управляют совокупной стоимостью владения. Я слышал, что CLR будет. Я даже видел платную JVM, которая этим управляет (давно, не помню...)

Пример батута в js: https://codeinjavascript.com/2020/06/13/tail-call-optimization-tco/

Старый тезис о совокупной стоимости владения на виртуальной машине HotSpot с перезаписью фрейма: https://ssw.jku.at/Research/Papers/Schwaighofer09Master/schwaighofer09master.pdf

Источник
Другие вопросы по тегам