¿Por qué la JVM todavía no soporta la optimización de tail-call?


Dos años después de does-the-jvm-prevent-tail-call-optimizations , parece haber un prototipo la implementación y MLVM ha enumerado la característica como "proto 80%" desde hace algún tiempo.

¿No hay un interés activo del lado de Sun / Oracle en apoyar las llamadas de cola o es solo que las llamadas de cola son " [...] destinado a ocupar el segundo lugar en cada lista de prioridades de características [...] "como se mencionó en el JVM Language Summit?

I estaría realmente interesado si alguien ha probado una compilación de MLVM y podría compartir algunas impresiones de lo bien que funciona (si es que lo hace).

Actualizar: Tenga en cuenta que algunas máquinas virtuales como Avian admiten llamadas de cola adecuadas sin ningún problema.

Author: Community, 2010-09-01

4 answers

Diagnóstico de Código Java: Mejorar el Rendimiento de su Código Java (alt) explica por qué la JVM no soporta la optimización de tail-call.

Pero aunque es bien sabido cómo transformar automáticamente una función recursiva de cola en un bucle simple, la especificación Java no requiere que se realice esta transformación. Presumiblemente, una razón por la que no es un requisito es que, en general, la transformación no se puede hacer estáticamente en un objeto orientado idioma. En su lugar, la transformación de función recursiva de cola a bucle simple debe hacerse dinámicamente por un compilador JIT.

Luego da un ejemplo de código Java que no se transformará.

Así que, como muestra el ejemplo en Listing 3, no podemos esperar que los compiladores estáticos realicen la transformación de la recursión de cola en código Java mientras preservan la semántica del lenguaje. En su lugar, debemos confiar en la compilación dinámica por el JIT. Dependiendo de la JVM, la JIT puede o puede no hagas esto.

Entonces da una prueba que puede usar para averiguar si su JIT hace esto.

Naturalmente, como este es un documento de IBM, incluye un plug:

Ejecuté este programa con un par de los SDK de Java, y los resultados fueron sorprendente. Corriendo en el Hotspot del Sol JVM para la versión 1.3 revela que Hotspot no realiza el transformación. En la configuración predeterminada, el espacio de la pila se agota en menos que un segundo en mi máquina. En el la otra mano, JVM de IBM para la versión 1.3 ronronea sin problema, lo que indica que transforma la código de esta manera.

 33
Author: emory,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-29 12:53:03

Una razón que he visto en el pasado para no implementar TCO (y que se ve como difícil) en Java es que el modelo de permisos en la JVM es sensible a la pila y, por lo tanto, las llamadas de cola deben manejar los aspectos de seguridad.

Creo que Clements y Felleisen demostraron que esto no era un obstáculo [1] [2] y estoy bastante seguro de que el parche MLVM mencionado en la pregunta también lo trata.

Me doy cuenta de que esto no responde a su pregunta; simplemente agregando interesante información.

  1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
  2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf
 30
Author: Alex Miller,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-11 00:43:10

Tal vez ya lo sepa, pero la característica no es tan trivial como puede sonar, ya que el lenguaje Java realmente expone el seguimiento de la pila al programador.

Considere el siguiente programa:

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());
    }
}

Aunque esto tiene una "llamada de cola", puede que no esté optimizado. (Si está optimizado, todavía requiere llevar la contabilidad de toda la pila de llamadas ya que la semántica del programa depende de ella.)

Básicamente, esto significa que es difícil soportar esto mientras todavía ser compatible con versiones anteriores.

 14
Author: aioobe,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-03-11 08:45:54

Java es el lenguaje menos funcional que puedas imaginar (bueno, OK, quizás no!) pero esto sería una gran ventaja para los lenguajes JVM, como Scala, que lo son.

Mis observaciones son que hacer de la JVM una plataforma para otros lenguajes nunca ha parecido estar en la parte superior de la lista de prioridades para Sun y, supongo, ahora para Oracle.

 12
Author: oxbow_lakes,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-09-01 09:11:45