performance - ¿Scala es compatible con la optimización de recursividad de cola?

tail-recursion

Question

¿Scala es compatible con la optimización de recursividad de cola?

Answer 1

En Scala 2.8 puede usar @tailrec para marcar el método específico que espera que el compilador optimice:

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

Si un método no puede optimizarse, recibe una advertencia.

Answer 2

Scala 2.7.x es compatible con la optimización de la cola de llamadas para la auto-recursión (una función que se llama a sí misma) de los métodos finales y las funciones locales.

Scala 2.8 podría venir con soporte de biblioteca para trampolín también, que es una técnica para optimizar funciones mutuamente recursivas.

Se puede encontrar una gran cantidad de información sobre el estado de la recurrencia de Scala en el blog de Rich Dougherty .

Answer 3

Scala realiza la optimización de la recursividad en tiempo de compilación, como han dicho otros carteles. Es decir, el compilador transforma una función recursiva de cola en un bucle (una invocación de método se transforma en un salto), como se puede ver en el seguimiento de pila cuando se ejecuta una función recursiva de cola.

Prueba el siguiente fragmento:

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

e inspecciona el rastro de la pila. Mostrará solo una llamada al auge de funciones, por lo tanto, el bytecode compilado no es recursivo.

Hay una propuesta flotando para implementar llamadas finales a nivel de JVM , lo que en mi opinión sería una gran cosa, ya que la JVM podría hacer optimizaciones de tiempo de ejecución, en lugar de solo compilar optimizaciones de tiempo del código, y posiblemente podría significar más recursividad de cola flexible. Básicamente, una tailcall invoke se comportaría exactamente como una invoke método normal, pero abandonará la pila de la llamada cuando sea seguro hacerlo: la especificación de la JVM establece que las estructuras de pila deben conservarse, por lo que el JIT debe realizar un análisis de código estático para averiguar si los marcos de pila nunca serán utilizados.

El estado actual es proto 80% . No creo que se haga a tiempo para Java 7 ( invokedynamic tiene una mayor prioridad, y la implementación está casi lista) pero Java 8 podría verlo implementado.

Answer 4

Solo en casos muy simples en que la función es auto recursiva.

Prueba de la capacidad de recursión de la cola.

Sin embargo, parece que Scala 2.8 podría estar mejorando el reconocimiento de recursividad de cola.