Почему JVM все еще не поддерживает оптимизацию хвостового вызова? - PullRequest
95 голосов
/ 01 сентября 2010

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

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

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

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

Ответы [ 4 ]

32 голосов
/ 10 сентября 2010

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

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

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

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

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

Естественно, поскольку это документ IBM, в него входит заглушка:

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

30 голосов
/ 24 февраля 2011

Одна из причин, по которым я видел в прошлом неиспользование 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
14 голосов
/ 07 сентября 2010

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

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

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

12 голосов
/ 01 сентября 2010

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...