Inline expansion

In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the called function. Inline expansion is similar to macro expansion, but occurs during compiling, without changing the source code (the text), while macro expansion occurs before compiling, and results in different text that is then processed by the compiler.

Inlining is an important optimization, but has complex effects on performance.^[1] As a rule of thumb, some inlining will improve speed at very minor cost of space, but excess inlining will hurt speed, due to inlined code consuming too much of the instruction cache, and also cost significant space. A survey of the modest academic literature on inlining from the 1980s and 1990s is given in Peyton Jones & Marlow 1999.^[2]

Inline expansion is similar to macro expansion as the compiler places a new copy of the function in each place it is called. Inlined functions run a little faster than the normal functions as function-calling-overheads are saved, however, there is a memory penalty. If a function is inlined 10 times, there will be 10 copies of the function inserted into the code. Hence inlining is best for small functions that are called often. In C++ the member functions of a class, if defined within the class definition, are inlined by default (no need to use the inlinereserved word (keyword)); otherwise, the keyword is needed. The compiler may ignore the programmer’s attempt to inline a function, mainly if it is particularly large.

Inline expansion is used to eliminate the time overhead (excess time) when a function is called. It is typically used for functions that execute frequently. It also has a space benefit for very small functions, and is an enabling transformation for other optimizations.

Without inline functions, the compiler decides which functions to inline. The programmer has little or no control over which functions are inlined and which are not. Giving this degree of control to the programmer allows for the use of application-specific knowledge in choosing which functions to inline.

Ordinarily, when a function is invoked, control is transferred to its definition by a branch or call instruction. With inlining, control drops through directly to the code for the function, without a branch or call instruction.

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.

The precise effect of inlining on cache performance is complex. For small cache sizes (much smaller than the working set before expansion), the increased sequentiality dominates, and inlining improves cache performance. For cache sizes close to the working set, where inlining expands the working set so it no longer fits in cache, this dominates and cache performance decreases. For cache sizes larger than the working set, inlining has negligible impact on cache performance. Further, changes in cache design, such as load forwarding, can offset the increase in cache misses.^[9]

Compilers use a variety of mechanisms to decide which function calls should be inlined; these can include manual hints from programmers for specific functions, together with overall control via command-line options. Inlining is done automatically by many compilers in many languages, based on judgment of whether inlining is beneficial, while in other cases it can be manually specified via compiler directives, typically using a keyword or compiler directive called inline. Typically this only hints that inlining is desired, rather than requiring inlining, with the force of the hint varying by language and compiler.

Typically, compiler developers keep the above performance issues in mind, and incorporate heuristics into their compilers that choose which functions to inline so as to improve performance, rather than worsening it, in most cases.

Once the compiler has decided to inline a particular function, performing the inlining operation itself is usually simple. Depending on whether a compiler inlines functions across code in different languages, the compiler can inline on either a high-level intermediate representation (like abstract syntax trees) or a low-level intermediate representation. In either case, the compiler simply computes the arguments, stores them in variables corresponding to the function's arguments, and then inserts the body of the function at the call site.

Linkers can also do function inlining. When a linker inlines functions, it may inline functions whose source is not available, such as library functions (see link-time optimization). A runtime system can inline a function also. Runtime inlining can use dynamic profiling information to make better decisions about which functions to inline, as in the Java HotSpot compiler.^[10]

Here is a simple example of inline expansion performed "by hand" at the source level in the C language:

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