¿Por qué .NET / C # no se optimiza para la recursividad de llamadas finales?

Encontré esta pregunta sobre qué idiomas optimizan la recursividad de la cola. ¿Por qué C # no optimiza la recursividad de cola, siempre que sea posible?

Para un caso concreto, ¿por qué este método no está optimizado en un bucle ( Visual Studio 2008 de 32 bits, si eso importa) ?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

La compilación JIT es un acto de equilibrio complicado entre no dedicar demasiado tiempo a la fase de compilación (lo que ralentiza considerablemente las aplicaciones de corta duración) o no realizar el análisis suficiente para mantener la aplicación competitiva a largo plazo con una compilación estándar anticipada .

Curiosamente, los pasos de compilación de NGen no están destinados a ser más agresivos en sus optimizaciones. Sospecho que esto se debe a que simplemente no quieren tener errores en los que el comportamiento dependa de si el JIT o NGen fue responsable del código de la máquina.

El CLR en sí admite la optimización de llamadas de cola, pero el compilador específico del lenguaje debe saber cómo generar el código de operación relevante y el JIT debe estar dispuesto a respetarlo. El fsc de F # generará los códigos de operación relevantes (aunque para una recursividad simple puede convertir todo en un whilebucle directamente). El csc de C # no lo hace.

Consulte esta publicación de blog para obtener algunos detalles (posiblemente ahora esté desactualizado debido a los cambios recientes del JIT). Tenga en cuenta que el CLR cambia para 4.0 , x86, x64 e ia64 lo respetarán .

Este envío de comentarios de Microsoft Connect debería responder a su pregunta. Contiene una respuesta oficial de Microsoft, por lo que recomiendo seguir eso.

Gracias por la sugerencia. Hemos considerado la posibilidad de emitir instrucciones de llamada de cola en varios puntos del desarrollo del compilador de C #. Sin embargo, hay algunos problemas sutiles que nos han empujado a evitar esto hasta ahora: 1) En realidad, existe un costo general no trivial al usar la instrucción .tail en CLR (no es solo una instrucción de salto ya que las llamadas de cola finalmente se convierten en en muchos entornos menos estrictos, como los entornos de ejecución del lenguaje funcional donde las llamadas finales están muy optimizadas). 2) Hay pocos métodos reales de C # donde sería legal emitir llamadas de cola (otros lenguajes fomentan los patrones de codificación que tienen más recursividad de cola, y muchos que dependen en gran medida de la optimización de la cola de llamadas en realidad hacen una reescritura global (como transformaciones de Continuation Passing) para aumentar la cantidad de recursividad de la cola). 3) En parte debido a 2), los casos en los que los métodos de C # se desbordan debido a una recursividad profunda que deberían haber tenido éxito son bastante raros.

Dicho todo esto, seguimos analizando esto, y es posible que en una versión futura del compilador encontremos algunos patrones en los que tenga sentido emitir instrucciones .tail.

Por cierto, como se ha señalado, vale la pena señalar que la recursividad de cola está optimizada en x64.

¡C # no se optimiza para la recursividad de llamadas finales porque para eso es F #!

Para obtener más información sobre las condiciones que impiden que el compilador de C # realice optimizaciones de llamadas finales, consulte este artículo: Condiciones de llamada final de JIT CLR .

Interoperabilidad entre C # y F #

C # y F # interoperan muy bien, y debido a que .NET Common Language Runtime (CLR) está diseñado con esta interoperabilidad en mente, cada lenguaje está diseñado con optimizaciones que son específicas para su intención y propósitos. Para ver un ejemplo que muestra lo fácil que es llamar código F # desde código C #, consulte Llamar código F # desde código C # ; para ver un ejemplo de cómo llamar a funciones C # desde el código F #, consulte llamar a funciones Llamar a funciones C # desde F # .

Para la interoperabilidad de los delegados, consulte este artículo: Interoperabilidad delegada entre F #, C # y Visual Basic .

Diferencias teóricas y prácticas entre C # y F #

Aquí hay un artículo que cubre algunas de las diferencias y explica las diferencias de diseño de la recursividad de llamada de cola entre C # y F #: Generación de código de operación de llamada de cola en C # y F # .

Aquí hay un artículo con algunos ejemplos en C #, F # y C ++ \ CLI: Adventures in Tail Recursion en C #, F # y C ++ \ CLI

La principal diferencia teórica es que C # está diseñado con bucles, mientras que F # está diseñado según los principios del cálculo Lambda. Para obtener un muy buen libro sobre los principios del cálculo Lambda, consulte este libro gratuito: Estructura e interpretación de programas informáticos, de Abelson, Sussman y Sussman .

Para obtener un artículo introductorio muy bueno sobre las llamadas finales en F #, consulte este artículo: Introducción detallada a las llamadas finales en F # . Finalmente, aquí hay un artículo que cubre la diferencia entre la recursividad sin cola y la recursión de llamada de cola (en F #): recursión de cola versus recursión sin cola en F sostenido .

Recientemente me dijeron que el compilador de C # para 64 bits optimiza la recursividad de la cola.

C # también implementa esto. La razón por la que no siempre se aplica es que las reglas utilizadas para aplicar la recursividad de cola son muy estrictas.

Puede utilizar la técnica de trampolín para funciones recursivas de cola en C # (o Java). Sin embargo, la mejor solución (si solo le importa la utilización de la pila) es usar este pequeño método auxiliar para envolver partes de la misma función recursiva y hacerla iterativa mientras mantiene la función legible.

Como se mencionó en otras respuestas, CLR admite la optimización de llamadas de cola y parece que históricamente ha estado bajo mejoras progresivas. Pero admitirlo en C # tiene un Proposalproblema abierto en el repositorio de git para el diseño del lenguaje de programación C # Support tail recursion # 2544 .

Puede encontrar algunos detalles e información útiles allí. Por ejemplo @jaykrell mencionó

Déjame darte lo que sé.

A veces, el tailcall es una actuación en la que todos ganan. Puede ahorrar CPU. jmp es más barato que call / ret. Puede ahorrar pila. Tocar menos pila mejora la localidad.

A veces, tailcall es una pérdida de rendimiento, una ganancia de pila. El CLR tiene un mecanismo complejo en el que pasar más parámetros a la persona que llama de los que recibió la persona que llama. Me refiero específicamente a más espacio de pila para parámetros. Esto es lento. Pero conserva pila. Solo hará esto con la cola. prefijo.

Si los parámetros de la persona que llama son más grandes que los parámetros de la persona que llama, por lo general es una transformación de ganar-ganar bastante fácil. Puede haber factores como el cambio de posición de parámetro de administrado a entero / flotante, y generar StackMaps precisos y demás.

Ahora, hay otro ángulo, el de los algoritmos que exigen la eliminación del tailcall, con el fin de poder procesar datos arbitrariamente grandes con stack fijo / pequeño. No se trata de rendimiento, sino de capacidad para correr.

También déjeme mencionar (como información adicional), cuando estamos generando una lambda compilada usando clases de expresión en el System.Linq.Expressionsespacio de nombres, hay un argumento llamado 'tailCall' que, como se explica en su comentario, es

Un bool que indica si se aplicará la optimización de la llamada de cola al compilar la expresión creada.

Aún no lo probé y no estoy seguro de cómo puede ayudar en relación con su pregunta, pero probablemente alguien pueda probarlo y puede ser útil en algunos escenarios:

var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();