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

Encontré esta pregunta sobre qué idiomas optimizan la recursividad de 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 comstackción de JIT es un acto de equilibrio engañoso entre no pasar demasiado tiempo haciendo la fase de comstackción (lo que ralentiza considerablemente las aplicaciones de corta duración) versus no hacer suficiente análisis para mantener la aplicación competitiva a largo plazo con una comstackción anticipada estándar. .

Curiosamente, los pasos de comstackción de NGen no están destinados a ser más agresivos en sus optimizaciones. Sospecho que esto es porque simplemente no quieren tener errores donde el comportamiento depende 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 finales, pero el comstackdor específico del idioma 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 recursión simple puede simplemente convertir todo en un ciclo while directamente). C # ‘s csc no.

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

Este envío de comentarios de Microsoft Connect debe responder a su pregunta. Contiene una respuesta oficial de Microsoft, así que recomiendo pasar por eso.

Gracias por la sugerencia. Consideramos emitir instrucciones de llamada final en varios puntos del desarrollo del comstackdor de C #. Sin embargo, hay algunos problemas sutiles que nos han obligado a evitar esto hasta el momento: 1) En realidad, hay un costo indirecto no trivial para usar la instrucción .tail en el CLR (no es solo una instrucción de salto, ya que las llamadas finales finalmente se vuelven en muchos entornos menos estrictos, como entornos de tiempo de ejecución de lenguaje funcional donde las llamadas finales están muy optimizadas). 2) Hay pocos métodos C # reales en los que sería legal emitir llamadas finales (otros idiomas fomentan patrones de encoding que tienen más recursividad de cola, y muchos que dependen en gran medida de la optimización de llamadas finales realmente realizan una reescritura global (como las transformaciones de Continuing Passing) ) para boost la cantidad de recursividad de cola). 3) En parte debido a 2), los casos en que los métodos C # astackn el desbordamiento debido a una recursión profunda que debería haber tenido éxito son bastante raros.

Dicho todo esto, continuamos observando esto, y es posible que en una versión futura del comstackdor 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 se optimiza en x64.

C # no se optimiza para la recursión de la cola de cola porque ¡para eso es F #!

Para conocer con detalle las condiciones que impiden que el comstackdor de C # realice optimizaciones de llamadas de cola, consulte este artículo: Condiciones de JIT CLR tail-call .

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 un ejemplo que muestra cuán fácil es llamar al código F # del código C #, vea Llamar al código F # del código C # ; para un ejemplo de invocación de funciones C # del código F #, consulte Funciones de llamada C # desde F # .

Para la interoperabilidad de delegates, consulte este artículo: Delegar interoperabilidad 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 cola entre C # y F #: Generación de código de operación de llamada y 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 un muy buen libro sobre los principios del cálculo Lambda, vea este libro gratuito: Estructura e Interpretación de Progtwigs de Computación, por Abelson, Sussman y Sussman .

Para ver un artículo introductorio muy bueno sobre las llamadas de cola en F #, consulte este artículo: Introducción detallada a las llamadas de cola en F # . Finalmente, aquí hay un artículo que cubre la diferencia entre la recursividad sin cola y la recurrencia de la cola (en F #): recurrencia de la cola vs. recurrencia sin cola en F sharp .

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

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

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