listas - Optimización de llamadas de cola C
listas enlazadas ejemplos (8)
Declaraciones como "C no realiza la eliminación de llamadas de cola" no tienen sentido. Como se indicó correctamente, cosas como estas dependen completamente de la implementación. Y sí, cualquier implementación decente puede convertir fácilmente la recursión de la cola en [un equivalente de] un ciclo. Por supuesto, los compiladores de C normalmente no ofrecen ninguna garantía sobre qué optimizaciones y cuáles no ocurrirán en cada pieza de código en particular. Tienes que compilarlo y verlo por ti mismo.
A menudo escucho a la gente decir que C no realiza la eliminación de llamadas de cola. A pesar de que no está garantizado por la norma, ¿no se realiza en la práctica por alguna implementación decente de todos modos? Suponiendo que solo está apuntando 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 la llamada de cola en C?
Además, ¿cuál fue la razón para dejar la optimización de llamadas de cola fuera del estándar?
El estándar de lenguaje define cómo se comporta el lenguaje, no cómo se requiere que se implementen los compiladores. La optimización no es obligatoria porque no siempre es deseada. Los compiladores proporcionan opciones para que el usuario pueda habilitar las optimizaciones si lo desean, 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 en una línea por línea), por lo que tiene sentido realizar solo la optimización a petición del usuario.
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 reemplaza esa llamada con un salto. Muchos casos en los que se puede hacer de manera segura son fáciles de reconocer, y tales casos se califican como "fruta segura y fácil de colgar". Sin embargo, incluso en los compiladores que pueden realizar dicha optimización, puede que no siempre sea obvio cuando 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 no siempre son 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, yc en registros, limpiar la pila y luego preparar los argumentos para su aprobación, pero puede que no haya suficientes registros disponibles para manejar foo(a,b,c,d,e,f,g,h,i); igualmente.
Si un idioma tuviera una sintaxis especial de "llamada de cola" que requiera que los compiladores, dado que hacen una llamada de cola si es posible, y de lo contrario se nieguen a compilar, el código podría asumir con seguridad que tales funciones podrían estar anidadas arbitrariamente. Sin embargo, cuando se usa la sintaxis de llamadas ordinarias, no hay una manera general de saber si un compilador podría realizar una llamada de cola más barata que una "ordinaria".
Hay situaciones en las que la optimización de la llamada de cola podría romper el ABI o, al menos, ser muy difícil de implementar de forma semántica. Piense en el código independiente de la posición en las bibliotecas compartidas, por ejemplo: algunas plataformas permiten que los programas se vinculen dinámicamente con las bibliotecas para ahorrar 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 la posición 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 independiente de la posición no debe estar optimizado para llamadas de cola. El problema involucrado es que las compensaciones para navegar a través del programa deben mantenerse en registros; en Intel de 32 bits, se utiliza %ebx que es un registro guardado de la persona que llama; Otras plataformas siguen esa noción. A diferencia de las funciones que usan llamadas normales, aquellos que implementan llamadas de cola tienen que restaurar los registros guardados de la persona que llama antes de pasar a la subrutina, no cuando regresan ellos mismos. Normalmente, esto no es un problema, porque en este punto, la función de mayor número de llamadas 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 ramificación.
Otros problemas podrían estar pendientes de limpiezas en lenguajes orientados a objetos (C ++), lo que significa que la última llamada en una función no es en realidad la última llamada, son las limpiezas. Por lo tanto, el compilador generalmente no optimiza, cuando este es el caso.
Por supuesto, también setjmp y longjmp son problemáticos, ya que esto efectivamente significa que una función puede finalizar 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. Estas son sólo algunas consideraciones.
Para aquellos que gustan de la prueba por construcción, aquí está Godbolt haciendo una buena optimización de llamadas de cola y en línea: https://godbolt.org/z/DMleUN
Sin embargo, si inicia 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
Para responder a su última pregunta: el estándar definitivamente no debe hacer ninguna declaración sobre la optimización. Puede haber entornos donde sea más o menos difícil de implementar.
Si bien los compiladores modernos PUEDEN hacer una optimización de llamadas de cola si activa las optimizaciones, sus compilaciones de depuración probablemente se ejecutarán sin ella para que pueda obtener rastros de pila y entrar / salir de código y cosas maravillosas como esa. En esta situación, no se desea la optimización de la llamada de cola.
Dado que la optimización de la llamada de cola no siempre es deseable, no tiene sentido mandarla a los compiladores del compilador.
Creo que las optimizaciones de llamadas de cola solo deben garantizarse cuando se anticipa o requiere mucha recursión; es decir, en lenguajes que fomentan o imponen un estilo de programación funcional. (Con este tipo de idiomas, es posible que los bucles o los bucles se desalienten fuertemente, que se perciban como poco elegantes o while estén completamente ausentes del idioma, por lo que recurriría a la recursión por todos estos motivos, y probablemente más).
El lenguaje de programación C (IMHO) claramente no fue diseñado teniendo en cuenta la programación funcional. Hay todo tipo de construcciones de bucle que se usan generalmente en 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, ya que no es estrictamente necesario para garantizar que los programas funcionen.
Contraste esto nuevamente con un lenguaje de programación funcional que no tiene bucles while: Esto significa que necesitará recursión; lo que a su vez significa que el idioma 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 idioma podría elegir prescribir la optimización de llamadas de cola.
PD: tenga en cuenta un ligero defecto en mi argumento para la optimización de la 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, las llamadas a funciones podrían implementarse de una manera totalmente diferente, y los desbordamientos de pila nunca serían un problema. Este sería otro argumento más contra la prescripción de optimización de llamadas de cola en un estándar. (Pero no me malinterpretes, puedo ver los méritos de tales optimizaciones, ¡incluso sin una pila!)