En informática , la expansión en línea o inlining es una optimización manual o del compilador que reemplaza el sitio de llamada de una 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 cambiar 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 en línea es una optimización importante, pero tiene efectos complicados en el rendimiento. [1] Como regla general , cierta inserción en línea mejorará la velocidad con un costo de espacio muy pequeño, pero una inserción en línea excesiva dañará la velocidad, debido a que el código insertado consume demasiado de la caché de instrucciones y también consume un espacio significativo. En Peyton Jones & Marlow 1999 se ofrece un estudio de la modesta literatura académica sobre la inserción en línea de los años 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 la 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 llamadas a funciones; sin embargo, hay una penalización de memoria. Si una función se incluye en línea 10 veces, habrá 10 copias de la función insertadas en el código. Por lo tanto, la inclusión en línea es mejor para funciones pequeñas que se llaman con frecuencia. En C++, las funciones miembro de una clase, si se definen dentro de la definición de clase, se incluyen en línea de forma predeterminada (no es necesario usar la palabra clave inline ); de lo contrario, se necesita la palabra clave. El compilador puede ignorar el intento del programador de incluir en línea una función, principalmente si es particularmente grande.
La expansión en línea se utiliza para eliminar la sobrecarga de tiempo (tiempo excedente) cuando se llama a una función. Se utiliza normalmente para funciones que se ejecutan con frecuencia. También tiene un beneficio de espacio para funciones muy pequeñas y es una transformación que permite otras optimizaciones .
Sin funciones en línea, el compilador decide qué funciones se incluyen en línea. El programador tiene poco o ningún control sobre qué funciones se incluyen en línea y cuáles no. Darle este grado de control al programador le permite usar el conocimiento específico de la aplicación para elegir qué funciones se incluyen en línea.
Normalmente, cuando se invoca una función, el control se transfiere a su definición mediante una instrucción de bifurcación o llamada. Con la inserción en línea, el control pasa directamente al código de la función, sin una instrucción de bifurcación o llamada.
Los compiladores suelen implementar sentencias con incrustación en línea. Las condiciones y los cuerpos de los bucles necesitan una evaluación diferida . Esta propiedad se cumple cuando el código para calcular las condiciones y los cuerpos de los bucles está incrustado en línea. Las consideraciones de rendimiento son otra razón para incrustar sentencias en línea.
En el contexto de los lenguajes de programación funcional , la expansión en línea suele ser seguida por la transformación de reducción beta .
Un programador puede insertar una función en línea manualmente mediante la programación de copiar y pegar , como una operación única en el código fuente . Sin embargo, otros métodos de control de la inserción en línea (ver a continuación) son preferibles, porque no precipitan errores que surgen cuando el programador pasa por alto una versión duplicada (posiblemente modificada) del cuerpo de la función original, mientras corrige un error en la función insertada en línea.
El efecto directo de esta optimización es mejorar el rendimiento en tiempo (eliminando 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 debido a la duplicación del cuerpo de la función predomina, excepto en casos simples, [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 beneficio principal de la expansión en línea es permitir optimizaciones adicionales y una mejor programació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. [3] El impacto final de la expansión en línea en la velocidad es complicado, debido a múltiples efectos en el rendimiento del sistema de memoria (principalmente caché de instrucciones ), que domina el rendimiento en los procesadores modernos: dependiendo del programa específico y la caché, la incorporación de funciones particulares puede aumentar o disminuir el rendimiento. [1]
El impacto de la incrustación varía según el lenguaje de programación y el programa, debido a los diferentes grados de abstracción. En lenguajes imperativos de nivel inferior, como C y Fortran, normalmente supone un aumento de velocidad del 10 al 20 %, con un impacto menor 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 incrustación; un ejemplo extremo es Self , donde un compilador vio factores de mejora de 4 a 55 gracias a la incrustación. [2]
Los beneficios directos de eliminar una llamada de función son:
Sin embargo, el principal beneficio de la inserción en línea es la optimización adicional que permite. Las optimizaciones que cruzan los límites de las funciones se pueden realizar sin necesidad de una optimización interprocedimental (IPO): una vez realizada la inserción en línea, se pueden realizar optimizaciones intraprocedimentales adicionales ("optimizaciones globales") en el cuerpo de la función ampliado. Por ejemplo:
Esto se puede hacer sin incrustar, pero requiere un compilador y enlazador significativamente más complicado (en caso de que el llamador y el llamado estén en unidades de compilación separadas).
Por el contrario, en algunos casos, una especificación de lenguaje puede permitir que un programa realice suposiciones adicionales sobre los argumentos de los procedimientos que ya no puede realizar después de que el procedimiento se inserta en línea, lo que impide algunas optimizaciones. Los compiladores más inteligentes (como Glasgow Haskell Compiler ) rastrearán esto, pero la inserción en línea ingenua pierde esta información.
Un beneficio adicional de la incrustación en línea para el sistema de memoria es:
El costo directo de la incrustación es el aumento del tamaño del código, debido a la duplicación del cuerpo de la función en cada sitio de llamada. Sin embargo, no siempre es así, a saber, en el caso de funciones muy cortas, donde el cuerpo de la función es más pequeño que el tamaño de una llamada de función (en el llamador, incluyendo el manejo de argumentos y valores de retorno), como métodos de acceso triviales o métodos mutadores (getters y setters); o para una función que solo se usa en un lugar, en cuyo caso no se duplica. Por lo tanto, la incrustación se puede minimizar o eliminar si se optimiza para el tamaño del código, como suele ser el caso en los sistemas integrados .
La inserción en línea también supone un coste 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. [6] Esto es más significativo si, antes de la expansión, el conjunto de trabajo del programa (o una sección activa del código) encajaba en un nivel de la jerarquía de memoria (por ejemplo, caché L1 ), pero después de la expansión ya no encaja, lo que da lugar a frecuentes fallos de caché en ese nivel. Debido a la diferencia significativa en el rendimiento en los diferentes niveles de la jerarquía, esto perjudica considerablemente el rendimiento. En el nivel más alto, esto puede dar lugar a un aumento de los fallos de página , una degradación catastrófica del rendimiento debido al thrashing o a que el programa no se ejecute en absoluto. Esto último es poco frecuente en las aplicaciones de escritorio y servidor comunes, donde el tamaño del código es pequeño en relación con la memoria disponible, pero puede ser un problema para los entornos con recursos limitados, como los sistemas integrados. Una forma de mitigar este problema es dividir las funciones en una ruta en línea activa más pequeña ( ruta rápida ) y una ruta no en línea fría más grande (ruta lenta). [6]
El rendimiento afectado por la incrustación es principalmente un problema para funciones grandes que se utilizan en muchos lugares, pero el punto de equilibrio más allá del cual la incrustación 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 optimización guiada por perfil . [7] Este es un problema similar a otras optimizaciones de expansión de código, como el desenrollado de bucle , que también reduce la cantidad de instrucciones procesadas, pero puede disminuir el rendimiento debido a un rendimiento de caché más deficiente.
El efecto preciso de la inserción en línea en el rendimiento de la caché es complicado. Para tamaños de caché pequeños (mucho más pequeños que el conjunto de trabajo antes de la expansión), predomina la mayor secuencialidad 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é, esto predomina y el rendimiento de la caché disminuye. Para tamaños de caché más grandes 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 las fallas de caché. [8]
Los compiladores utilizan una variedad de mecanismos para decidir qué llamadas de función deben incluirse en línea; estos pueden incluir sugerencias manuales de los programadores para funciones específicas, junto con un control general a través de opciones de línea de comandos . La inclusión en línea se realiza automáticamente por muchos compiladores en muchos lenguajes, en función de su criterio sobre si la inclusión en línea es beneficiosa, mientras que en otros casos se puede especificar manualmente a través de directivas del compilador , generalmente utilizando una palabra clave o directiva del compilador llamada inline. Por lo general, esto solo sugiere que se desea la inclusión en línea, en lugar de requerirla, y la fuerza de la sugerencia varía según el lenguaje y el compilador.
Normalmente, los desarrolladores de compiladores tienen en cuenta los problemas de rendimiento mencionados anteriormente e incorporan heurísticas en sus compiladores que eligen qué funciones incorporar para mejorar el rendimiento, en lugar de empeorarlo, en la mayoría de los casos.
Una vez que el compilador ha decidido incorporar una función en particular, realizar la operación de incorporación suele ser simple. Dependiendo de si el compilador incorpora funciones en código en diferentes lenguajes, el compilador puede realizar la incorporación en una representación intermedia de alto nivel (como árboles de sintaxis abstracta ) o en una representación intermedia de bajo nivel. En cualquier caso, el compilador simplemente calcula los argumentos , los almacena en variables correspondientes a los argumentos de la función y luego inserta el cuerpo de la función en el sitio de llamada.
Los enlazadores también pueden incorporar funciones en línea. Cuando un enlazador incorpora funciones en línea, puede incorporar funciones cuyo código fuente no está disponible, como funciones de biblioteca (consulte optimización en tiempo de enlace ). Un sistema en tiempo de ejecución también puede incorporar funciones en línea. La incorporación en línea en tiempo de ejecución puede utilizar información de creación de perfiles dinámica para tomar mejores decisiones sobre qué funciones incorporar en línea, como en el compilador Java Hotspot . [9]
A continuación se muestra un ejemplo simple de expansión en línea realizada "a mano" en el nivel de origen en el lenguaje de programación C :
int pred ( int x ) { si ( x == 0 ) devuelve 0 ; de lo contrario devuelve x - 1 ; } Antes de la inserción en línea:
int func ( int y ) { devuelve pred ( y ) + pred ( 0 ) + pred ( y + 1 ); } Después de la inserción en línea:
int func ( int y ) { int tmp ; si ( y == 0 ) tmp = 0 ; de lo contrario tmp = y - 1 ; /* (1) */ si ( 0 == 0 ) tmp += 0 ; de lo contrario tmp += 0 - 1 ; /* (2) */ si ( y + 1 == 0 ) tmp += 0 ; de lo contrario tmp += ( y + 1 ) - 1 ; /* (3) */ devolver tmp ; } Tenga en cuenta que esto es solo un ejemplo. En una aplicación C real, sería preferible utilizar una característica del lenguaje de incrustación, 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.
Las macros de ensamblador proporcionan un enfoque alternativo a la inserción en línea, mediante el cual una secuencia de instrucciones normalmente se puede generar en línea mediante la expansión de macros a partir de una única declaración de origen de macros (con cero o más parámetros). Uno de los parámetros podría ser una opción para generar alternativamente una subrutina separada de una sola vez que contenga la secuencia y que se procese en su lugar mediante una llamada en línea a la función. Ejemplo:
MOVER DESDE=matriz1,A=matriz2,ENLINEA=NO
Se han explorado una variedad de diferentes heurísticas para la inserción en línea. Por lo general, un algoritmo de inserción en línea tiene un presupuesto de código determinado (un aumento permitido en el tamaño del programa) y tiene como objetivo insertar en línea los sitios de llamada más valiosos sin exceder ese presupuesto. En este sentido, muchos algoritmos de inserción en línea suelen estar modelados según el problema de la mochila . [10] Para decidir qué sitios de llamada son más valiosos, un algoritmo de inserción en línea debe estimar su beneficio, es decir, la disminución esperada en el tiempo de ejecución. Comúnmente, los algoritmos de inserción en línea utilizan información de perfil sobre la frecuencia de ejecución de diferentes rutas de código para estimar los beneficios. [11]
Además de la información de perfiles, los compiladores just-in-time más nuevos aplican varias heurísticas más avanzadas, como: [4]
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 una transformación habilitadora . Es decir, una vez que el compilador expande un cuerpo de función en el contexto de su sitio de llamada (a menudo con argumentos que pueden ser constantes fijas ), puede ser capaz de hacer una variedad de transformaciones que antes no eran posibles. Por ejemplo, una rama condicional puede resultar siempre verdadera o siempre falsa en este sitio de llamada en particular. Esto, a su vez, puede habilitar la eliminación de código muerto , el movimiento de código invariante de bucle o la eliminación de variable por 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:
tmp += 0instrucciones en las líneas marcadas (2) y (3) no hacen nada. El compilador puede eliminarlas.0 == 0siempre es verdadera, por lo que el compilador puede reemplazar la línea marcada (2) con el consecuente tmp += 0(que no hace nada).y+1 == 0a y == -1.(y + 1) - 1a y.yy y+1no pueden ser ambas iguales a cero. Esto permite que el compilador elimine una prueba.if (y == 0) return yel valor de yse conoce en el cuerpo y se puede incluir en línea.La nueva función se ve así:
int func ( int y ) { si ( y == 0 ) devuelve 0 ; si ( y == -1 ) devuelve -2 ; devuelve 2 * y - 1 ; } La expansión en línea completa no siempre es posible debido a la recursión : la expansión en línea recursiva de las llamadas no terminará. Existen varias soluciones, como expandir una cantidad limitada o analizar el gráfico de llamadas y romper bucles en ciertos nodos (es decir, no expandir algún borde en un bucle recursivo). [12] 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 lograba en el nivel de fuente mediante macros parametrizadas . El uso de funciones en línea reales, como las que están disponibles en C99 , ofrece varias ventajas con respecto a este enfoque:
Muchos compiladores también pueden expandir en línea algunas funciones recursivas ; [13] las macros recursivas suelen ser ilegales.
A Bjarne Stroustrup , el diseñador de C++, le gusta enfatizar que las macros deben evitarse siempre que sea posible y aboga por el uso extensivo de funciones en línea.
Muchos compiladores incorporan funciones de forma agresiva siempre que sea beneficioso hacerlo. Aunque puede dar lugar a ejecutables más grandes , la incorporació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 incorporación es una optimización fundamental en los lenguajes funcionales y los lenguajes de programación orientados a objetos , que dependen de ella para proporcionar suficiente contexto para sus funciones típicamente pequeñas para que las optimizaciones clásicas sean efectivas.
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. [4] Otros lenguajes proporcionan construcciones para sugerencias explícitas, generalmente como directivas del compilador (pragmas).
En el lenguaje de programación Ada , existe un pragma para funciones en línea.
Las funciones en Common Lisp pueden definirse como en línea mediante la inlinedeclaración como tal: [14]
( declaim ( despacho en línea )) ( defun despacho ( x ) ( funcall ( get ( car x ) 'despacho ) x )) El compilador Haskell GHC intenta incorporar en línea funciones o valores que sean lo suficientemente pequeños, pero la incorporación en línea se puede indicar explícitamente mediante un pragma de lenguaje: [15]
función_clave :: Int -> String -> ( Bool , Double ) {-# INLINE función_clave #-} C y C++ tienen una inlinepalabra clave que funciona como directiva del compilador (especificando que la inserción en línea es deseada pero no obligatoria ) y también cambia la visibilidad y el comportamiento de vinculación. El cambio de visibilidad es necesario para permitir que la función se incorpore en línea a través de la cadena de herramientas estándar de C, donde la compilación de archivos individuales (en lugar de unidades de traducción ) es seguida por la vinculación: para que el enlazador pueda incorporar funciones en línea, deben especificarse en el encabezado (para que sean visibles) y marcarse inline(para evitar la ambigüedad de múltiples definiciones).
