Optimización de llamada de cola C

Para responder a su última pregunta: El estándar definitivamente no debe hacer ninguna declaración sobre la optimización. Puede haber entornos en los que sea más o menos difícil de implementar.

Aunque los compiladores modernos PUEDEN hacer una optimización de llamada de cola si activa las optimizaciones, sus compilaciones de depuración probablemente se ejecutarán sin ella para que pueda obtener trazas de pila y entrar/salir del código y cosas maravillosas como esas. En esta situación, no se desea la optimización de llamadas de cola.

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

Creo que las optimizaciones de llamadas de cola deben garantizarse solo cuando se anticipa o requiere una gran cantidad de recursividad; es decir, en lenguajes que fomentan o imponen un estilo de programación funcional. (Con este tipo de lenguajes, puede encontrar que los bucles for o while están fuertemente desaconsejados, percibidos como poco elegantes, o probablemente incluso completamente ausentes del lenguaje, por lo que recurriría a la recursividad por todas estas razones, y probablemente más.)

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

Contraste esto de nuevo con un lenguaje de programación funcional que no tiene bucles while: Esto significa que necesitarecursión; 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 dicho lenguaje podría elegir prescribir la optimización de llamadas de cola.

P.d.: Tenga en cuenta un ligero defecto en mi argumento para optimización de llamada de 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, función las llamadas podrían implementarse de una manera totalmente diferente, y los desbordamientos de pila nunca serían un problema. Este sería otro argumento contra 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!)

El estándar de lenguaje define cómo se comporta el lenguaje, no cómo se requiere que los compiladores sean implementados. 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 código (se vuelve 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 en el solicitud.

Hay situaciones en las que la optimización de llamadas de cola podría romper el ABI o al menos ser muy difícil de implementar de una manera que preserve la semántica. Piense en colocar código independiente en bibliotecas compartidas, por ejemplo: Algunas plataformas permiten que los programas se vinculen dinámicamente con bibliotecas para guardar 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 mediante el uso de código independiente de posición para bibliotecas, de modo que el direccionamiento es relativo a un desplazamiento, en lugar de absoluto a un espacio de direcciones fijo. En muchas plataformas, sin embargo, el código independiente de posición no debe estar optimizado para llamadas de cola. El problema es que las compensaciones para navegar a través del programa tienen que mantenerse en registros; en Intel de 32 bits, se usa %ebx que es un destinatario guardado regístrese; otras plataformas siguen esa noción. A diferencia de las funciones que usan llamadas normales, aquellas que implementan llamadas tail tienen que restaurar los registros guardados del llamante antes de ramificarse a la subrutina, no cuando regresan ellos mismos. Normalmente, eso no es un problema, porque en este punto, la función que más llama no se preocupa por el valor almacenado en %ebx, pero el código independiente de la posición depende de este valor en cada comando de salto, llamada o rama.

Otros problemas podrían ser limpiezas pendientes en lenguajes orientados a objetos (C++), lo que significa que la última llamada en una función no es realmente la última llamada, las limpiezas 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 significa efectivamente 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 hay más razones técnicas que uno puede pensar de. Estas son solo algunas consideraciones.

Para aquellos que les gusta la prueba por construcción, aquí está godbolt haciendo una buena optimización de llamada de cola y en línea: https://godbolt.org/z/DMleUN

Sin embargo, si manivela la optimización a-O3 (o sin duda si espera unos años o utiliza un compilador diferente), la optimización elimina totalmente el bucle/recursión.

Aquí hay un ejemplo que optimiza hasta una sola instrucción incluso con-O2: https://godbolt.org/z/CNzWex

Es común que los compiladores reconozcan situaciones en las que una función no necesita hacer nada después de llamar a otra, y reemplacen esa llamada con un salto. Muchos casos en los que eso se puede hacer de forma segura son fáciles de reconocer, y tales casos califican como "fruta segura". Sin embargo, incluso en compiladores que pueden realizar dicha optimización, no siempre es obvio cuándo debería o se realizará. Varios factores pueden hacer que el costo de una llamada de cola sea mayor que el de una llamada normal, y estos factores pueden no ser siempre predecibles. Por ejemplo, si una función termina con return foo(1,2,3,a,b,c,4,5,6);, puede ser práctico copiar a, b y c en registros, limpiar la pila y luego preparar los argumentos para pasar, pero puede que no haya suficientes registros disponibles para manejar foo(a,b,c,d,e,f,g,h,i); del mismo modo.

Si un lenguaje tiene una sintaxis especial de "llamada de cola" que requiere que los compiladores, dado que hacen una llamada de cola si es posible, y rechazan la compilación de lo contrario, el código podría asumir con seguridad tales funciones podrían anidarse arbitrariamente profundo. Sin embargo, cuando se utiliza la sintaxis de llamada ordinaria, no hay una forma general de saber si un compilador sería capaz de realizar una llamada de cola más barata que una "ordinaria".