Cada vez que hay una discusión sobre un nuevo lenguaje de programación dirigido a la JVM, inevitablemente hay personas que dicen cosas como:
"La JVM no admite la optimización de llamadas de cola, por lo que predigo muchas pilas explosivas"
Hay miles de variaciones sobre ese tema.
Ahora sé que algunos lenguajes, como Clojure, por ejemplo, tienen una construcción recurrente especial que puedes usar.
Lo que no entiendo es: ¿qué tan grave es la falta de optimización de la cola? ¿Cuándo debería preocuparme por eso?
Mi principal fuente de confusión probablemente proviene del hecho de que Java es uno de los lenguajes más exitosos de la historia y parece que a algunos de los lenguajes JVM les está yendo bastante bien. ¿Cómo es eso posible si la falta de TCO es realmente de cualquier preocupación?
fuente
GOTO
, la JVM no. Y x86 no se utiliza como plataforma de interoperabilidad. La JVM no tieneGOTO
y una de las principales razones para elegir la Plataforma Java es la interoperabilidad. Si desea implementar TCO en la JVM, debe hacer algo a la pila. Adminístrelo usted mismo (es decir, no use la pila de llamadas JVM), use trampolines, use excepciones comoGOTO
, algo así. En todos esos casos, se vuelve incompatible con la pila de llamadas JVM. Es imposible ser compatible con Java, tener TCO y un alto rendimiento. Tienes que sacrificar uno de esos tres.Respuestas:
Considere esto, digamos que nos deshicimos de todos los bucles en Java (los escritores del compilador están en huelga o algo así). Ahora queremos escribir factorial, por lo que podríamos corregir algo como esto
Ahora nos sentimos bastante listos, ¡hemos logrado escribir nuestro factorial incluso sin bucles! Pero cuando probamos, notamos que con cualquier número de tamaño razonable, estamos obteniendo errores de stackoverflow ya que no hay TCO.
En Java real, esto no es un problema. Si alguna vez tenemos un algoritmo recursivo de cola, podemos transformarlo en un bucle y estar bien. Sin embargo, ¿qué pasa con los idiomas sin bucles? Entonces solo estás manguera. Es por eso que clojure tiene esta
recur
forma, sin ella, ni siquiera está completa (no hay forma de hacer bucles infinitos).La clase de lenguajes funcionales que se dirigen a JVM, Frege, Kawa (Scheme), Clojure siempre están tratando de lidiar con la falta de llamadas de cola, porque en estos idiomas, TC es la forma idiomática de hacer bucles. Si se traduce al Esquema, ese factorial anterior sería un buen factorial. Sería muy inconveniente si el bucle de 5000 veces hiciera que su programa se bloqueara. Sin embargo, esto se puede solucionar, con
recur
formas especiales, anotaciones que sugieren optimizar las auto llamadas, el trampolín, lo que sea. Pero todos fuerzan los golpes de rendimiento o el trabajo innecesario en el programador.Ahora Java tampoco se libera, ya que hay más en TCO que solo recursividad, ¿qué pasa con las funciones recursivas mutuas? No se pueden traducir directamente a bucles, pero la JVM todavía no los optimiza. Esto hace que sea espectacularmente desagradable tratar de escribir algoritmos usando recursividad mutua usando Java ya que si quieres un rendimiento / rango decente debes hacer magia oscura para que encaje en los bucles.
Entonces, en resumen, esto no es un gran problema para muchos casos. La mayoría de las llamadas de cola solo proceden un frameframe de profundidad, con cosas como
o son recursivas. Sin embargo, para la clase de TC que no encaja en esto, cada lenguaje JVM siente el dolor.
Sin embargo, hay una razón decente por la que todavía no tenemos TCO. La JVM nos da rastros de pila. Con TCO eliminamos sistemáticamente los cuadros de pila que sabemos que están "condenados", ¡pero la JVM podría desearlos más tarde para un seguimiento de pila! Digamos que implementamos un FSM como este, donde cada estado llama a la siguiente. Borraríamos todos los registros de estados anteriores para que un rastreo nos muestre qué estado, pero no nada sobre cómo llegamos allí.
Además, y de manera más apremiante, gran parte de la verificación de bytecode se basa en la pila, eliminando lo que nos permite verificar bytecode no es una perspectiva agradable. Entre esto y el hecho de que Java tiene bucles, TCO parece un poco más problemático de lo que vale para los ingenieros de JVM.
fuente
La optimización de llamadas de cola es principalmente importante debido a la recursividad de cola. Sin embargo, existe un argumento de por qué es realmente bueno que la JVM no optimice las llamadas de cola: como TCO reutiliza una parte de la pila, un seguimiento de la pila de una excepción será incompleto, lo que dificultará un poco la depuración.
Hay formas de evitar las limitaciones de la JVM:
Esto puede necesitar un ejemplo más amplio. Considere un lenguaje con cierres (por ejemplo, JavaScript o similar). Podemos escribir el factorial como
Ahora podemos hacer que devuelva una devolución de llamada:
Esto ahora funciona en un espacio de pila constante, lo cual es un poco tonto porque de todos modos es recursivo. Sin embargo, esta técnica puede aplanar todas las llamadas de cola en un espacio de pila constante. Y si el programa está en CPS, esto significa que la pila de llamadas es constante en general (en CPS, cada llamada es una llamada de cola).
Una desventaja importante de esta técnica es que es mucho más difícil de depurar, un poco más difícil de implementar y menos eficaz: vea todos los cierres e indirectas que estoy usando.
Por estas razones, sería muy preferible que la VM implementara una llamada de cola. Los lenguajes como Java que tienen buenas razones para no admitir llamadas de cola no tendrían que usarlo.
fuente
return foo(....);
en el métodofoo
(2), por supuesto. Aún así, aceptamos el rastreo incompleto de bucles, asignaciones (!), Secuencias de instrucciones. Por ejemplo, si encuentra un valor inesperado en una variable, seguramente querrá saber cómo llegó allí. Pero no te quejas de las huellas faltantes en ese caso. Debido a que de alguna manera está grabado en nuestros cerebros que a) ocurre solo en llamadas b) ocurre en todas las llamadas. Ambos no tiene sentido, en mi humilde opinión.Una parte importante de las llamadas en un programa son llamadas de cola. Cada subrutina tiene una última llamada, por lo que cada subrutina tiene al menos una llamada de cola. Las llamadas de cola tienen las características de rendimiento
GOTO
pero la seguridad de una llamada de subrutina.Tener llamadas de cola adecuadas le permite escribir programas que de otro modo no podría escribir. Tomemos, por ejemplo, una máquina de estados. Una máquina de estados puede implementarse muy directamente haciendo que cada estado sea una subrutina y cada transición de estado sea una llamada de subrutina. En ese caso, pasa de un estado a otro haciendo una llamada tras otra, ¡y en realidad nunca regresas! Sin llamadas de cola adecuadas, inmediatamente volarías la pila.
Sin PTC, debe usar
GOTO
Trampolines o excepciones como flujo de control o algo así. Es mucho más feo, y no tanto una representación directa 1: 1 de la máquina de estado.(Observe cómo ingeniosamente evité usar el aburrido ejemplo de "bucle". Este es un ejemplo donde los PTC son útiles incluso en un lenguaje con bucles).
Deliberadamente utilicé el término "Llamadas de cola adecuadas" aquí en lugar de TCO. TCO es un compilador de optimización. PTC es una función de lenguaje que requiere que cada compilador realice TCO.
fuente
The vast majority of calls in a program are tail calls.
No, si "la gran mayoría" de los métodos llamados realizan más de una llamada propia.Every subroutine has a last call, so every subroutine has at least one tail call.
Esta es trivialmente demostrable como falso:return a + b
. (A menos que esté en un lenguaje loco donde las operaciones aritméticas básicas se definen como llamadas a funciones, por supuesto).Cualquiera que diga esto, ya sea (1) no entiende la optimización de la cola, o (2) no entiende la JVM, o (3) ambos.
Comenzaré con la definición de llamadas de cola de Wikipedia (si no te gusta Wikipedia, aquí hay una alternativa ):
En el siguiente código, la llamada a
bar()
es la llamada de cola defoo()
:La optimización de la llamada de cola ocurre cuando la implementación del lenguaje, al ver una llamada de cola, no utiliza la invocación de método normal (que crea un marco de pila), sino que crea una rama. Esta es una optimización porque un marco de pila requiere memoria, y requiere ciclos de CPU para insertar información (como la dirección de retorno) en el marco, y porque se supone que el par de llamada / retorno requiere más ciclos de CPU que un salto incondicional.
El TCO a menudo se aplica a la recursividad, pero ese no es su único uso. Tampoco es aplicable a todas las recursiones. El código recursivo simple para calcular un factorial, por ejemplo, no puede ser optimizado, porque lo último que sucede en la función es una operación de multiplicación.
Para implementar la optimización de llamadas de cola, necesita dos cosas:
Eso es. Como he señalado en otra parte, la JVM (como cualquier otra arquitectura completa de Turing) tiene un goto. Resulta que tiene un goto incondicional , pero la funcionalidad podría implementarse fácilmente utilizando una rama condicional.
El análisis estático es lo que es complicado. Dentro de una sola función, no hay problema. Por ejemplo, aquí hay una función Scala recursiva de cola para sumar los valores en a
List
:Esta función se convierte en el siguiente código de bytes:
Tenga
goto 0
en cuenta el al final. En comparación, una función Java equivalente (que debe usar unIterator
para imitar el comportamiento de romper una lista Scala en cabeza y cola) se convierte en el siguiente código de bytes. Tenga en cuenta que las dos últimas operaciones son ahora una invocación , seguida de un retorno explícito del valor producido por esa invocación recursiva.La optimización de la llamada de cola de una sola función es trivial: el compilador puede ver que no hay código que use el resultado de la llamada, por lo que puede reemplazar la invocación con a
goto
.Donde la vida se vuelve difícil es si tienes múltiples métodos. Las instrucciones de ramificación de la JVM, a diferencia de las de un procesador de uso general como el 80x86, se limitan a un solo método. Todavía es relativamente sencillo si tiene métodos privados: el compilador es libre de incorporar esos métodos según corresponda, por lo que puede optimizar las llamadas de cola (si se pregunta cómo podría funcionar esto, considere un método común que use un
switch
para controlar el comportamiento). Incluso puede extender esta técnica a varios métodos públicos en la misma clase: el compilador integra los cuerpos de los métodos, proporciona métodos de puentes públicos y las llamadas internas se convierten en saltos.Pero, este modelo se rompe cuando considera los métodos públicos en diferentes clases, particularmente a la luz de las interfaces y cargadores de clases. El compilador de nivel de origen simplemente no tiene suficiente conocimiento para implementar optimizaciones de cola. Sin embargo, a diferencia de las implementaciones "bare-metal", el * JVM (tiene la información para hacer esto, en la forma del compilador Hotspot (al menos, el compilador ex-Sun sí lo tiene). No sé si realmente funciona optimizaciones de llamada de cola, y sospecho que no, pero podría .
Lo que me lleva a la segunda parte de su pregunta, que reformularé como "¿debería importarnos?"
Claramente, si su lenguaje usa la recursividad como su única primitiva para la iteración, le importa. Pero los idiomas que necesitan esta característica pueden implementarla; El único problema es si un compilador para dicho lenguaje puede producir una clase que pueda llamar y ser llamada por una clase arbitraria de Java.
Fuera de ese caso, voy a invitar votos negativos diciendo que es irrelevante. La mayor parte del código recursivo que he visto (y he trabajado con muchos proyectos gráficos) no es optimizable . Al igual que el factorial simple, utiliza la recursividad para construir el estado, y la operación de cola es una combinación.
Para el código que es optimizable en cola, a menudo es sencillo traducir ese código en una forma iterable. Por ejemplo, esa
sum()
función que mostré anteriormente se puede generalizar comofoldLeft()
. Si observa la fuente , verá que en realidad se implementa como una operación iterativa. Jörg W Mittag tenía un ejemplo de una máquina de estado implementada mediante llamadas de función; Hay muchas implementaciones de máquinas de estado eficientes (y mantenibles) que no dependen de llamadas de funciones que se traducen en saltos.Terminaré con algo completamente diferente. Si busca en Google las notas al pie en el SICP, puede terminar aquí . Personalmente considero que un lugar mucho más interesante que tener mi compilador sustituir
JSR
porJUMP
.fuente
return foo(123);
podría ejecutarse mejor en líneafoo
que generando código para manipular la pila y realizar un salto, pero no veo por qué la llamada de cola sería diferente de una llamada ordinaria en a ese respecto.