Expansión en línea

En informática , la expansión en línea , o inlining , es una optimización manual o del compilador que reemplaza una llamada a función con el cuerpo de la función llamada. La expansión en línea es similar a la expansión de macros , pero ocurre durante la compilación, sin modificar el código fuente (el texto), mientras que la expansión de macros ocurre antes de la compilación y da como resultado un texto diferente que luego es procesado por el compilador .

La inserción de código en línea es una optimización importante, pero tiene efectos complejos en el rendimiento. ^{[ 1 ]} Como regla general , cierta inserción de código en línea mejorará la velocidad con un coste mínimo de espacio, pero un exceso de inserción de código en línea la perjudicará, debido a que el código insertado consume demasiado espacio en la caché de instrucciones , y también costará un espacio significativo. En Peyton Jones y Marlow (1999) se presenta una revisión de la escasa literatura académica sobre inserción de código en línea de las décadas de 1980 y 1990. ^{[ 2 ]}

La expansión en línea es similar a la expansión de macros, ya que el compilador coloca una nueva copia de la función en cada lugar donde se llama. Las funciones en línea se ejecutan un poco más rápido que las funciones normales, ya que se ahorran los costos de las llamadas a funciones; sin embargo, existe una penalización de memoria. Si una función se expande en línea 10 veces, se insertarán 10 copias de la función en el código. Por lo tanto, la expansión en línea es mejor para funciones pequeñas que se llaman con frecuencia. En C++, las funciones miembro de una clase, si están definidas dentro de la definición de la clase, se expanden en línea por defecto (no es necesario usar la palabra reservada ` inline` ); de lo contrario, se necesita la palabra clave `inline`. El compilador puede ignorar el intento del programador de expandir una función en línea, principalmente si es particularmente grande.

La expansión en línea se utiliza para eliminar la sobrecarga de tiempo (tiempo excesivo) al llamar a una función. Se suele emplear para funciones que se ejecutan con frecuencia. Además, ofrece ventajas en cuanto al espacio para funciones muy pequeñas y facilita otras optimizaciones .

Sin funciones en línea, el compilador decide qué funciones insertar. El programador tiene poco o ningún control sobre qué funciones se insertan y cuáles no. Otorgar este grado de control al programador permite utilizar el conocimiento específico de la aplicación para elegir qué funciones insertar.

Normalmente, cuando se invoca una función, el control se transfiere a su definición mediante una instrucción de salto o llamada. Con la inserción en línea, el control pasa directamente al código de la función, sin necesidad de una instrucción de salto o llamada.

Los compiladores suelen implementar las sentencias con inserción en línea. Las condiciones y los cuerpos de los bucles requieren evaluación diferida . Esta propiedad se cumple cuando el código para calcular las condiciones y los cuerpos de los bucles se inserta en línea. Las consideraciones de rendimiento son otra razón para insertar sentencias en línea.

En el contexto de los lenguajes de programación funcional , la expansión en línea suele ir seguida de la transformación de reducción beta . ^{[ 3 ]}

Un programador podría insertar una función manualmente mediante copiar y pegar código , como una operación única sobre el código fuente . Sin embargo, otros métodos para controlar la inserción de funciones (véase más abajo) son preferibles, ya que evitan errores que surgen cuando el programador pasa por alto una versión duplicada (posiblemente modificada) del cuerpo de la función original al corregir un error en la función insertada.

El efecto directo de esta optimización es mejorar el rendimiento temporal (al eliminar la sobrecarga de llamadas), a costa de empeorar el uso del espacio ^{[ a ]} (debido a la duplicación del cuerpo de la función). La expansión del código debida a la duplicación del cuerpo de la función predomina, excepto en casos sencillos, ^{[ b ]} y, por lo tanto, el efecto directo de la expansión en línea es mejorar el tiempo a costa del espacio.

Sin embargo, el principal beneficio de la expansión en línea es permitir optimizaciones adicionales y una mejor planificación, debido al aumento del tamaño del cuerpo de la función, ya que es posible una mejor optimización en funciones más grandes. ^{[ 4 ]} El impacto final de la expansión en línea en la velocidad es complejo, debido a los múltiples efectos en el rendimiento del sistema de memoria (principalmente la caché de instrucciones ), que domina el rendimiento en los procesadores modernos: dependiendo del programa y la caché específicos, la inserción en línea de funciones particulares puede aumentar o disminuir el rendimiento. ^{[ 1 ]}

El impacto de la inserción de código en línea varía según el lenguaje de programación y el programa, debido a los diferentes grados de abstracción. En lenguajes imperativos de bajo nivel como C y Fortran, suele suponer un aumento de velocidad del 10-20%, con un impacto mínimo en el tamaño del código, mientras que en lenguajes más abstractos puede ser significativamente más importante, debido a la cantidad de capas que elimina la inserción de código en línea. Un ejemplo extremo es Self , donde un compilador observó factores de mejora de 4 a 55 gracias a la inserción de código en línea. ^{[ 2 ]}

Los beneficios directos de eliminar una llamada a una función son:

• Elimina las instrucciones necesarias para una llamada a función , tanto en la función que realiza la llamada como en la función llamada: colocar los argumentos en una pila o en registros , la llamada a la función en sí, el prólogo de la función , luego al regresar el epílogo de la función , la instrucción de retorno , y luego obtener el valor de retorno, y eliminar los argumentos de las pilas y restaurar los registros (si es necesario).
• Al no necesitar registros para pasar argumentos, reduce el desbordamiento de registros .
• Elimina la necesidad de pasar referencias y luego desreferenciarlas, cuando se utiliza el paso por referencia (o paso por dirección , o paso por compartición ).

Sin embargo, la principal ventaja de la inserción en línea reside en las optimizaciones adicionales que permite. Se pueden realizar optimizaciones que trascienden los límites de las funciones sin necesidad de optimización interprocedimental (IPO): una vez realizada la inserción en línea, es posible añadir optimizaciones intraprocedimentales ("optimizaciones globales") al cuerpo de la función ampliado. Por ejemplo:

• Una constante pasada como argumento a menudo se puede propagar a todas las instancias del parámetro correspondiente, o parte de la función se puede "extraer" de un bucle (mediante movimiento de código invariante al bucle ).
• La asignación de registros se puede realizar en todo el cuerpo de la función.
• Las optimizaciones de alto nivel, como el análisis de escape y la duplicación de cola , pueden realizarse en un ámbito más amplio y ser más efectivas, sobre todo si el compilador que implementa dichas optimizaciones se basa principalmente en el análisis intraprocedimental. ^{[ 5 ]} Estas pueden realizarse sin inlining, pero requieren un compilador y un enlazador significativamente más complejos (en caso de que la función que llama y la función llamada se encuentren en unidades de compilación separadas).

Por el contrario, en algunos casos, la especificación del lenguaje puede permitir que un programa haga suposiciones adicionales sobre los argumentos de los procedimientos que ya no puede hacer después de que el procedimiento se haya insertado en línea, lo que impide algunas optimizaciones. Los compiladores más avanzados (como Glasgow Haskell Compiler (GHC)) detectan esto, pero la inserción en línea simple pierde esta información.

Otra ventaja de la inserción en línea para el sistema de memoria es:

• Eliminar bifurcaciones y mantener el código que se ejecuta cerca en la memoria mejora el rendimiento de la caché de instrucciones al mejorar la localidad de referencia (localidad espacial y secuencialidad de las instrucciones). Esto es menor que las optimizaciones que se centran específicamente en la secuencialidad, pero es significativo. ^{[ 6 ]}

El coste directo de la inserción en línea es el aumento del tamaño del código, debido a la duplicación del cuerpo de la función en cada llamada. Sin embargo, no siempre ocurre, especialmente en el caso de funciones muy cortas, donde el cuerpo de la función es menor que el tamaño de una llamada a la función (en la función que la llama, incluyendo el manejo de argumentos y valores de retorno), como los métodos de acceso o modificación triviales (obtenidos y setters); o para una función que se usa solo en un lugar, en cuyo caso no se duplica. Por lo tanto, la inserción en línea puede minimizarse o eliminarse si se optimiza el tamaño del código, como suele ocurrir en los sistemas embebidos .

La inserción en línea también impone un costo en el rendimiento, debido a que la expansión del código (debido a la duplicación) perjudica el rendimiento de la caché de instrucciones. ^{[ 7 ]} Esto es más significativo si, antes de la expansión, el conjunto de trabajo del programa (o una sección de código de uso frecuente) cabía en un nivel de la jerarquía de memoria (por ejemplo, la caché L1 ), pero después de la expansión ya no cabe, lo que resulta en fallos de caché frecuentes en ese nivel. Debido a la diferencia significativa en el rendimiento en diferentes niveles de la jerarquía, esto perjudica considerablemente el rendimiento. En el nivel más alto, esto puede resultar en un aumento de fallos de página , una degradación catastrófica del rendimiento debido a la sobrecarga , o que el programa no se ejecute en absoluto. Esto último es raro en aplicaciones comunes de escritorio y servidor, donde el tamaño del código es pequeño en relación con la memoria disponible, pero puede ser un problema para entornos con recursos limitados, como los sistemas embebidos. Una forma de mitigar este problema es dividir las funciones en una ruta en línea de uso frecuente más pequeña ( ruta rápida ) y una ruta no en línea de uso poco frecuente más grande (ruta lenta). ^{[ 7 ]}

La desventaja del rendimiento que supone la inserción en línea es un problema principalmente para funciones grandes que se utilizan en muchos lugares, pero el punto de equilibrio a partir del cual la inserción en línea reduce el rendimiento es difícil de determinar y depende en general de la carga precisa, por lo que puede estar sujeto a optimización manual o a optimización guiada por perfiles . ^{[ 8 ]} Este es un problema similar al de otras optimizaciones de expansión de código, como el desenrollado de bucles , que también reduce el número de instrucciones procesadas, pero puede disminuir el rendimiento debido a un rendimiento de caché inferior.

El efecto preciso de la inserción en línea sobre el rendimiento de la caché es complejo. Para tamaños de caché pequeños (mucho menores que el conjunto de trabajo antes de la expansión), predomina la secuencialidad aumentada y la inserción en línea mejora el rendimiento de la caché. Para tamaños de caché cercanos al conjunto de trabajo, donde la inserción en línea expande el conjunto de trabajo de modo que ya no cabe en la caché, predomina este efecto y el rendimiento de la caché disminuye. Para tamaños de caché mayores que el conjunto de trabajo, la inserción en línea tiene un impacto insignificante en el rendimiento de la caché. Además, los cambios en el diseño de la caché, como el reenvío de carga , pueden compensar el aumento de fallos de caché. ^{[ 9 ]}

Los compiladores utilizan diversos mecanismos para decidir qué llamadas a funciones deben insertarse en línea; estos pueden incluir sugerencias manuales de los programadores para funciones específicas, junto con el control general mediante opciones de línea de comandos . Muchos compiladores realizan la inserción en línea automáticamente en muchos lenguajes, basándose en un criterio sobre si resulta beneficiosa, mientras que en otros casos puede especificarse manualmente mediante directivas del compilador , normalmente utilizando una palabra clave o directiva del compilador llamada ` inlineinlining`. Por lo general, esto solo sugiere que se desea la inserción en línea, en lugar de exigirla, y la fuerza de la sugerencia varía según el lenguaje y el compilador.

Por lo general, los desarrolladores de compiladores tienen en cuenta los problemas de rendimiento mencionados anteriormente e incorporan heurísticas en sus compiladores que eligen qué funciones insertar en línea para mejorar el rendimiento, en lugar de empeorarlo, en la mayoría de los casos.

Una vez que el compilador decide insertar una función en línea, realizar la operación de inserción suele ser sencillo. Dependiendo de si el compilador inserta funciones en código escrito en diferentes lenguajes, puede hacerlo sobre una representación intermedia de alto nivel (como árboles de sintaxis abstracta ) o sobre una de bajo nivel. En ambos casos, el compilador simplemente calcula los argumentos , los almacena en variables que corresponden a los argumentos de la función y, a continuación, inserta el cuerpo de la función en el punto de llamada.

Los enlazadores también pueden realizar la inserción de funciones en línea. Cuando un enlazador inserta funciones en línea, puede hacerlo incluso cuando el código fuente no está disponible, como en el caso de las funciones de biblioteca (véase la optimización en tiempo de enlace ). Un sistema de tiempo de ejecución también puede insertar una función en línea. La inserción en línea en tiempo de ejecución puede utilizar información de perfilado dinámico para tomar mejores decisiones sobre qué funciones insertar, como en el compilador Java HotSpot . ^{[ 10 ]}

Aquí hay un ejemplo simple de expansión en línea realizada "manualmente" a nivel de código fuente en el lenguaje C :

int pred ( int x ) { if ( x == 0 ) { return 0 ; } else { return x - 1 ; } }

Antes de insertar en línea:

int func ( int y ) { return pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }

Después de la inserción en línea:

int func ( int y ) { int tmp ;// (1) si ( y == 0 ) { tmp = 0 ; } else { tmp = y - 1 ; }// (2) si ( 0 == 0 ) { tmp += 0 ; } else { tmp += 0 - 1 ; }// (3) si ( y + 1 == 0 ) { tmp += 0 ; } else { tmp += ( y + 1 ) - 1 ; }devolver tmp ; }

Tenga en cuenta que esto es solo un ejemplo. En una aplicación C real, sería preferible usar una característica del lenguaje de inserción de código, como macros parametrizadas o funciones en línea, para indicarle al compilador que transforme el código de esta manera. La siguiente sección enumera formas de optimizar este código.

MOVER DESDE=array1,HACIA=array2,EN LÍNEA=NO

La expansión en línea en sí misma es una optimización, ya que elimina la sobrecarga de las llamadas, pero es mucho más importante como transformación habilitadora . Es decir, una vez que el compilador expande el cuerpo de una función en el contexto de su punto de llamada —a menudo con argumentos que pueden ser constantes fijas— puede realizar diversas transformaciones que antes no eran posibles. Por ejemplo, una bifurcación condicional puede resultar siempre verdadera o siempre falsa en ese punto de llamada en particular. Esto, a su vez, puede permitir la eliminación de código muerto , el movimiento de código invariante en bucles o la eliminación de variables de inducción .

En el ejemplo de C de la sección anterior, abundan las oportunidades de optimización. El compilador puede seguir esta secuencia de pasos:

• Las tmp += 0instrucciones en las líneas marcadas con (2) y (3) no hacen nada. El compilador puede eliminarlas.
• La condición 0 == 0siempre es verdadera, por lo que el compilador puede reemplazar la línea marcada con (2) con el consecuente, tmp += 0(lo cual no hace nada).
• El compilador puede reescribir la condición y+1 == 0a y == -1.
• El compilador puede reducir la expresión (y + 1) - 1a y.
• Las expresiones yy y+1no pueden ser ambas iguales a cero. Esto permite al compilador eliminar una prueba.
• En declaraciones como if (y == 0) return yel valor de yse conoce en el cuerpo y se puede insertar en línea.

La nueva función tiene el siguiente aspecto:

int func ( int y ) { if ( y == 0 ) { return 0 ; } if ( y == -1 ) { return -2 ; } return 2 * y - 1 ; }

La expansión completa en línea no siempre es posible debido a la recursión : expandir recursivamente las llamadas en línea no terminará. Existen varias soluciones, como expandir una cantidad limitada o analizar el grafo de llamadas y romper los bucles en ciertos nodos (es decir, no expandir alguna arista en un bucle recursivo). ^{[ 13 ]} Un problema idéntico ocurre en la expansión de macros, ya que la expansión recursiva no termina, y generalmente se resuelve prohibiendo las macros recursivas (como en C y C++).

Tradicionalmente, en lenguajes como C , la expansión en línea se realizaba a nivel de código fuente mediante macros parametrizadas . El uso de funciones en línea reales, como las disponibles en C99 , ofrece varias ventajas sobre este enfoque:

• En C, las llamadas a macros no realizan comprobaciones de tipo , ni siquiera verifican que los argumentos estén bien formados, mientras que las llamadas a funciones sí lo hacen.
• En C, una macro no puede usar la palabra clave `return` con el mismo significado que una función (esto provocaría la terminación de la función que solicitó la expansión, en lugar de la macro). En otras palabras, una macro no puede devolver nada que no sea el resultado de la última expresión invocada en su interior.
• Dado que las macros de C utilizan una mera sustitución de texto, esto puede dar lugar a efectos secundarios no deseados e ineficiencia debido a la reevaluación de los argumentos y el orden de las operaciones .
• Los errores de compilación dentro de las macros suelen ser difíciles de entender, ya que se refieren al código expandido, en lugar del código que escribió el programador. Por lo tanto, la información de depuración para el código insertado en línea suele ser más útil que la del código expandido mediante macros.
• Muchas estructuras son difíciles o imposibles de expresar mediante macros, o bien utilizan una sintaxis significativamente diferente. Las funciones en línea utilizan la misma sintaxis que las funciones regulares y se pueden insertar o extraer fácilmente a voluntad.

Muchos compiladores también pueden expandir en línea algunas funciones recursivas ; ^{[ 14 ]} las macros recursivas suelen ser ilegales.

A Bjarne Stroustrup , el diseñador de C++, le gusta recalcar que se deben evitar las macros siempre que sea posible, y aboga por el uso extensivo de funciones en línea.

Muchos compiladores optimizan agresivamente las funciones mediante la inserción en línea siempre que sea beneficioso. Si bien esto puede generar ejecutables más grandes, la inserción agresiva se ha vuelto cada vez más deseable a medida que la capacidad de memoria ha aumentado más rápido que la velocidad de la CPU. La inserción en línea es una optimización fundamental en lenguajes de programación funcional y orientada a objetos , que dependen de ella para proporcionar suficiente contexto a sus funciones, generalmente pequeñas, y así hacer efectivas las optimizaciones clásicas.

Muchos lenguajes, incluidos Java y los lenguajes funcionales, no proporcionan construcciones de lenguaje para funciones en línea, pero sus compiladores o intérpretes a menudo realizan una expansión en línea agresiva. ^{[ 5 ]} Otros lenguajes proporcionan construcciones para sugerencias explícitas, generalmente como directivas del compilador (pragmas).

El lenguaje Ada tiene una directiva pragma para funciones en línea.

Las funciones en Common Lisp se pueden definir como inline mediante la inlinedeclaración de la siguiente manera: ^{[ 15 ]}

( declamar ( despacho en línea )) ( despacho defunción ( x ) ( llamada de función ( obtener ( coche x ) 'despachar ) x ))

El compilador de Haskell GHC intenta insertar en línea funciones o valores que sean lo suficientemente pequeños, pero la inserción en línea puede indicarse explícitamente mediante una directiva pragma del lenguaje: ^{[ 16 ]}

función_clave :: Int -> String -> ( Bool , Double ) {-# INLINE función_clave #-}

• Macro (informática)
• Evaluación parcial
• Eliminación de llamadas de cola
• Esquema de código

• Chen, WY; Chang, PP; Conte, TM; Hwu, WW (septiembre de 1993). "El efecto de las optimizaciones de expansión de código en el diseño de la caché de instrucciones" (PDF) . IEEE Transactions on Computers . 42 (9): 1045– 1057. Bibcode : 1993ITCmp..42.1045C . doi : 10.1109/12.241594 . hdl : 2142/74513 .
• Peyton Jones, Simon ; Marlow, Simon (septiembre de 1999). Secretos del compilador Glasgow Haskell Inliner (Informe técnico).

• " Eliminación de llamadas a funciones virtuales en programas C++ "; Gerald Aigner, Urs Hölzle
• " Reducción de la sobrecarga de las llamadas a funciones indirectas en programas C++ "; Brad Calder, Dirk Grumwald
• ALTO: un optimizador de tiempo de enlace para DEC Alpha
• " Técnicas avanzadas "; John R. Levine
• " Optimización completa del programa con Visual C++ .NET "; Brandon Bray