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

95

Спустя два года после оптимизации «делает-jvm-prevent-tail-call-call» , похоже, существует реализация прототипа, и MLVM уже некоторое время указывает эту функцию как «proto 80%».

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

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

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

soc
источник
14
Учитывая сообщение об исходе людей Sun из Oracle, я не ожидал, что какой-либо из текущих проектов продолжится, если об этом прямо не скажет Oracle :(
Торбьёрн Равн Андерсен
16
Обратите внимание, что ваш принятый ответ полностью неверен. Нет фундаментального конфликта между оптимизацией хвостового вызова и ООП, и, конечно же, некоторые языки, такие как OCaml и F #, имеют как ООП, так и TCO.
JD
2
Что ж, называть ООП языками OCaml и F # - в первую очередь плохая шутка. Но да, у ООП и TCO не так много общего, за исключением того факта, что среда выполнения должна проверять, что оптимизируемый метод не переопределен / не подклассифицирован где-то еще.
soc
5
+1 Исходя из опыта C, я всегда предполагал, что совокупная стоимость владения задана в любой современной JVM. Мне никогда не приходило в голову проверить, и когда я это сделал, результаты были удивительными ...
thkala
2
@soc: "за исключением того факта, что среда выполнения должна проверить, что оптимизируемый метод не переопределен / не подклассифицирован где-то еще". Ваш «факт» - полная чушь.
JD

Ответы:

32

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

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

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

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

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

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

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

Эмори
источник
62
FWIW, хвостовые вызовы - это не только саморекурсивные функции, как он подразумевает. Хвостовые вызовы - это любые вызовы функций, которые появляются в хвостовой позиции. Они не обязательно должны быть вызовами себе, и они не должны быть вызовами статически известных местоположений (например, они могут быть вызовами виртуальных методов). Описанная им проблема не является проблемой, если оптимизация хвостовых вызовов в общем случае выполнена правильно, и, следовательно, его пример отлично работает на объектно-ориентированных языках, поддерживающих хвостовые вызовы (например, OCaml и F #).
JD
3
«должно выполняться динамически JIT-компилятором», что означает, что это должно выполняться самой JVM, а не компилятором Java. Но OP спрашивает о JVM.
Raedwald
11
«вообще, преобразование не может быть выполнено статически на объектно-ориентированном языке». Это, конечно, цитата, но каждый раз, когда я вижу такое оправдание, я хотел бы спросить о числах - потому что я не удивлюсь, если на практике в большинстве случаев это можно будет установить во время компиляции.
greenoldman
5
Ссылка на процитированную статью теперь не работает, хотя Google ее кеширует. Что еще более важно, рассуждения автора ошибочны. В приведенном примере можно было бы оптимизировать хвостовой вызов, используя статическую, а не только динамическую компиляцию, если бы только компилятор вставил instanceofпроверку, чтобы увидеть, thisявляется ли Exampleобъект объектом (а не его подклассом Example).
Alex D
4
просто ссылка на
веб-
30

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

Я считаю, что Клементс и Фелляйзен [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
Алекс Миллер
источник
1
+1. Слушайте вопросы / ответы в конце этой презентации Брайана Гетца youtube.com/watch?v=2y5Pv4yN0b0&t=3739
mcoolive
15

Возможно, вы уже это знаете, но эта функция не так тривиальна, как может показаться, поскольку язык 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());
    }
}

Несмотря на то, что это имеет «хвостовой вызов», его нельзя оптимизировать. (Если она будет оптимизирована, она по- прежнему требует бухгалтерии всего вызова стека поскольку семантике программа опирается на него.)

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

aioobe
источник
17
Нашел ошибку в вашей мысли: «требует учета всего стека вызовов, так как семантика программы зависит от него». :-) Это похоже на новые «подавленные исключения». Программы, основанные на таких вещах, обязательно сломаются. На мой взгляд, поведение программы абсолютно правильное: выброс фреймов стека - это то, о чем идет речь в хвостовых вызовах.
soc,
4
@Marco, но практически любой метод может вызвать исключение, из-за которого будет доступен весь стек вызовов, верно? Кроме того, вы не можете заранее решить, какие методы будут косвенно вызывать gв этом случае ... подумайте, например, о полиморфизме и отражении.
aioobe
2
Это побочный эффект, вызванный добавлением ARM в Java 7. Это пример того, что вы не можете полагаться на такие вещи, которые вы показали выше.
soc
6
«тот факт, что язык предоставляет стек вызовов, затрудняет реализацию этого»: требует ли язык, чтобы трассировка стека, возвращаемая getStackTrace()из метода, x()который показывает исходный код, вызывается из метода, y()также показывает, что x()была вызвана из y()? Потому что, если есть некоторая свобода, реальной проблемы нет.
Raedwald
8
Это просто вопрос формулировки спецификации одного метода, от «дает вам все кадры стека» до «дает вам все активные кадры стека, исключая те, которые устарели из-за хвостовых вызовов». Кроме того, можно сделать это параметром командной строки или системным свойством, независимо от того, соблюдается ли хвостовой вызов.
Ingo
12

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

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

Oxbow_lakes
источник
16
@ Thorbjørn - Я написал программу, чтобы предсказать, остановится ли какая-либо конкретная программа за конечный промежуток времени. Он взял меня возрастов !
oxbow_lakes 01
3
Первые BASIC, которые я использовал, не имели функций, а имели GOSUB и RETURN. Я не думаю, что LOLCODE очень функциональный (и вы можете понимать это в двух смыслах).
Дэвид Торнли
1
@ Дэвид, функционал! = Имеет функции.
Торбьёрн Равн Андерсен,
2
@ Торбьёрн Равн Андерсен: Нет, но это своего рода предварительное условие, не так ли?
Дэвид Торнли,
3
«превращение JVM в платформу для других языков никогда не казалось первым в списке приоритетов Sun». Они приложили значительно больше усилий для превращения JVM в платформу для динамических языков, чем для функциональных языков.
JD