C optimización de llamadas de cola

Question

A menudo escucho a la gente decir que C no realiza la eliminación de llamadas de cola. Aunque no está garantizado por el estándar, ¿no se realiza en la práctica mediante alguna implementación decente de todos modos? Suponiendo que solo se dirige a compiladores maduros y bien implementados, y no le importa la máxima portabilidad absoluta a los compiladores primitivos escritos para plataformas oscuras, ¿es razonable confiar en la eliminación de las llamadas finales en C?

Además, ¿cuál fue el motivo para dejar la optimización de la cola de llamadas fuera de la norma?

Answer 1

Declaraciones como "C no realiza la eliminación de la llamada final" no tienen sentido. Como se señaló correctamente a sí mismo, cosas como esta dependen completamente de la implementación. Y sí, cualquier implementación decente puede fácilmente convertir la recursión de cola en [un equivalente de] un ciclo. Por supuesto, los compiladores de C normalmente no dan ninguna garantía sobre qué optimizarán y qué optimizaciones no sucederán en cada fragmento de código en particular. Tienes que compilarlo y verlo por ti mismo.

Answer 2

Para responder su última pregunta: La norma definitivamente no debe hacer ninguna declaración sobre la optimización. Puede haber entornos donde es más o menos difícil de implementar.

Answer 3

El estándar de idioma define cómo se comporta el lenguaje, no cómo se deben implementar los compiladores. La optimización no es obligatoria porque no siempre se desea. Los compiladores proporcionan opciones para que el usuario pueda habilitar optimizaciones si así lo desea y también puede desactivarlas. La optimización del compilador puede afectar la capacidad de depurar el código (se hace más difícil hacer coincidir C con el ensamblaje línea por línea), por lo que tiene sentido realizar solo la optimización a petición del usuario.

Answer 4

Creo que las optimizaciones de las llamadas finales deben garantizarse solo cuando mucho de recursión sea anticipado o requerido; es decir, en idiomas que fomentan o imponen un estilo de programación funcional. (Con este tipo de idiomas, puede descubrir que los bucles for o while están muy desaconsejados, percibidos como poco elegantes o, probablemente, incluso completamente ausentes del idioma, por lo que recurriría a recurrencia por todos estos motivos, y probablemente más)

El lenguaje de programación C (en mi humilde opinión) era no diseñado con programación funcional en mente. Hay todo tipo de construcciones de bucle que generalmente se utilizan a favor de la recursión: for, do .. while, while. En tal lenguaje, no tendría mucho sentido prescribir la optimización de la cola de llamadas en un estándar, porque no es estrictamente necesario para garantizar los programas en funcionamiento.

Contraste esto otra vez con un lenguaje de programación funcional que no tiene while bucles: Esto significa que necesidad recursividad; lo que a su vez significa que el lenguaje debe asegurarse de que, con muchas iteraciones, los desbordamientos de pila no se conviertan en un problema; por lo tanto, el estándar oficial para tal lenguaje podría elegir prescribir la optimización de la cola de llamadas.

---

P.S .: nota un ligero defecto en mi argumento para la optimización de llamada cola. Hacia el final de, menciono desbordamientos de pila. ¿Pero quién dice que las llamadas a funciones siempre requieren una pila? En algunas plataformas, las llamadas a funciones podrían implementarse de una manera totalmente diferente, y los desbordamientos de la pila nunca serían un problema. Este sería otro argumento más en contra de la prescripción de optimización de llamadas de cola en un estándar. (Pero no me malinterpreten, puedo ver los méritos de tales optimizaciones, ¡incluso sin una pila!)

Answer 5

Aunque los compiladores modernos PUEDEN realizar optimizaciones de cola si activa las optimizaciones, las compilaciones de depuración probablemente se ejecutarán sin él para que pueda obtener trazas de pila y entrar o salir del código y cosas maravillosas como esa. En esta situación, no se desea optimizar la cola de llamada.

Dado que la optimización de la cola de cola no siempre es deseable, no tiene sentido ordenarla a los escritores del compilador.

Answer 6

Existen situaciones en las que la optimización de la cola podría romper el ABI o, al menos, ser muy difícil de implementar de forma semántica. Piense en el código de posición independiente en bibliotecas compartidas, por ejemplo: algunas plataformas permiten que los programas se vinculen dinámicamente con bibliotecas para guardar la memoria principal cuando varias aplicaciones diferentes dependen de la misma funcionalidad. En tales casos, la biblioteca se carga una vez y se asigna a cada una de las memorias virtuales del programa como si fuera la única aplicación en un sistema. En UNIX y también en algunos otros sistemas, esto se logra utilizando un código de posición independiente para las bibliotecas, de modo que el direccionamiento es relativo a un desplazamiento, en lugar de absoluto a un espacio de direcciones fijo. Sin embargo, en muchas plataformas, el código de posición independiente no debe ser optimizado. El problema involucrado es que las compensaciones para navegar a través del programa deben mantenerse en registros; en Intel 32 bits, se usa %ebx que es un registro guardado en línea; otras plataformas siguen esa noción. A diferencia de las funciones que utilizan llamadas normales, las que despliegan llamadas de cola deben restaurar los registros guardados en línea antes de la bifurcación en la subrutina, no cuando se devuelven. Normalmente, eso no es un problema, porque en este punto, la función de llamada más alta no se preocupa por el valor almacenado en %ebx, pero el código de posición independiente depende de este valor en cada comando de salto, llamada o bifurcación.

Otros problemas podrían estar pendientes de las limpiezas en los lenguajes orientados a objetos (C++), lo que significa que la última llamada de una función no es realmente la última llamada; las limpiezas sí lo son. Por lo tanto, el compilador generalmente no optimiza, cuando este es el caso.

También setjmp y longjmp son problemáticos, por supuesto, ya que esto efectivamente significa que una función puede terminar la ejecución más de una vez, antes de que realmente termine. ¡Difícil o imposible de optimizar en tiempo de compilación!

Probablemente haya razones más técnicas que se puedan imaginar. Estas son solo algunas consideraciones.