Expansión en línea - Inline expansion

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

La inserción es una optimización importante, pero tiene efectos complicados sobre el rendimiento. Como regla general , un poco de inserción mejorará la velocidad con un costo de espacio muy pequeño, pero el exceso de inserción afectará la velocidad, debido a que el código en línea consume demasiado de la caché de instrucciones y también cuesta un espacio significativo. En Peyton Jones & Marlow 1999 se ofrece un estudio de la modesta bibliografía académica sobre inlining de los años ochenta y noventa.

Descripción general

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 que se llama. Las funciones en línea se ejecutan un poco más rápido que las funciones normales, ya que se guardan los gastos generales de llamada a funciones, sin embargo, hay una penalización de memoria. Si una función está insertada 10 veces, habrá 10 copias de la función insertadas en el código. Por lo tanto, la inserción 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 la clase, están alineadas de forma predeterminada (no es necesario utilizar la palabra clave en línea ); de lo contrario, se necesita la palabra clave. El compilador puede ignorar el intento del programador de incorporar una función, principalmente si es particularmente grande.

La expansión en línea se utiliza para eliminar la sobrecarga de tiempo (exceso de tiempo) cuando se llama a una función. Suele utilizarse para funciones que se ejecutan con frecuencia. También tiene un beneficio de espacio para funciones muy pequeñas y es una transformación habilitadora para otras optimizaciones .

Sin funciones en línea, el compilador decide qué funciones incorporar. El programador tiene poco o ningún control sobre qué funciones están integradas y cuáles no. Dar este grado de control al programador permite el uso de conocimientos específicos de la aplicación para elegir qué funciones incorporar.

Normalmente, cuando se invoca una función, el control se transfiere a su definición mediante una rama o instrucción de llamada. Con la alineación, el control pasa directamente al código de la función, sin una rama o instrucción de llamada.

Los compiladores generalmente implementan declaraciones con inlining. Las condiciones del bucle y los cuerpos del bucle necesitan una evaluación lenta . Esta propiedad se cumple cuando el código para calcular las condiciones del bucle y los cuerpos del bucle está insertado. Las consideraciones de rendimiento son otra razón para las declaraciones en línea.

En el contexto de los lenguajes de programación funcionales , la expansión en línea suele ir seguida de la transformación de reducción beta .

Un programador puede incorporar una función manualmente a través de la programación de copiar y pegar , como una operación única en el código fuente . Sin embargo, son preferibles otros métodos para controlar la inserción (ver más abajo), porque no precipitan los 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 integrada.

Efecto sobre el rendimiento

El efecto directo de esta optimización es mejorar el rendimiento del tiempo (al eliminar la sobrecarga de llamadas), a costa de empeorar el uso del espacio (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 domina, excepto en casos simples, 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 más optimizaciones y una programación mejorada, 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. El impacto final de la expansión en línea en la velocidad es complicado, debido a los múltiples efectos sobre el rendimiento del sistema de memoria (principalmente la caché de instrucciones ), que domina el rendimiento en los procesadores modernos: según el programa y la caché específicos, las funciones particulares en línea pueden aumentar o disminuir el rendimiento .

El impacto de la integració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 bajo nivel, como C y Fortran, suele ser un aumento de velocidad del 10-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 se eliminan en línea. con un ejemplo extremo que es Self , donde un compilador vio factores de mejora de 4 a 55 mediante la inserción.

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

Sin embargo, el principal beneficio de la integración son las optimizaciones adicionales que permite. Las optimizaciones que cruzan los límites de la función se pueden realizar sin necesidad de optimización interprocedimiento (IPO): una vez que se ha realizado la inserción, se hacen posibles optimizaciones intraprocedimiento adicionales ("optimizaciones globales") en el cuerpo de función ampliado. Por ejemplo:

Estos se pueden hacer sin inlining, pero requieren un compilador y un enlazador significativamente más complicados (en caso de que el llamador y el destinatario estén en unidades de compilación separadas).

Por el contrario, en algunos casos, una especificación de lenguaje puede permitir que un programa haga suposiciones adicionales sobre argumentos a procedimientos que ya no puede realizar después de que el procedimiento está en línea, lo que evita algunas optimizaciones. Los compiladores más inteligentes (como Glasgow Haskell Compiler ) rastrearán esto, pero la inserción ingenua pierde esta información.

Otro beneficio de la inserción en línea para el sistema de memoria es:

  • La eliminación de ramas y el mantenimiento del código que se ejecuta juntos 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 más pequeño que las optimizaciones que apuntan específicamente a la secuencialidad, pero es significativo.

El costo directo de la inserción es un mayor 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 lo hace, es decir, 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, incluido el manejo de argumentos y valores de retorno), como los métodos de acceso triviales o el mutador. métodos (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 inserción puede minimizarse o eliminarse si se optimiza el tamaño del código, como suele ser el caso en los sistemas integrados .

La inserción 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. Esto es más significativo si, antes de la expansión, el conjunto de trabajo del programa (o una sección activa de código) encaja 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 resulta en frecuentes el caché falla en ese nivel. Debido a la diferencia significativa en el desempeño en los diferentes niveles de la jerarquía, esto perjudica considerablemente el desempeño. En el nivel más alto que esto puede provocar un aumento de los errores de página , la degradación del rendimiento debido a la catastrófica goleada , o en su defecto el programa para funcionar en absoluto. Esto último es poco común 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 integrados. Una forma de mitigar este problema es dividir las funciones en una ruta en línea caliente más pequeña ( ruta rápida ) y una ruta fría no en línea más grande (ruta lenta).

Inlining perjudica el rendimiento es principalmente un problema para las funciones grandes que se utilizan en muchos lugares, pero el punto de equilibrio más allá del cual el inlining 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 perfil. -Optimización guiada . Este es un problema similar a otras optimizaciones de expansión de código, como el desenrollado de bucles , que también reduce la cantidad de instrucciones procesadas, pero puede disminuir el rendimiento debido a un peor rendimiento de la caché.

El efecto preciso de la inserción 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 mejora el rendimiento de la caché. Para tamaños de caché cercanos al conjunto de trabajo, donde la alineación expande el conjunto de trabajo para que ya no quepa en el caché, esto domina y el rendimiento del caché disminuye. Para tamaños de caché más grandes que el conjunto de trabajo, la inserción 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 pérdidas de caché.

Soporte del compilador

Los compiladores utilizan una variedad de mecanismos para decidir qué llamadas de función deben estar en línea; Estos pueden incluir sugerencias manuales de los programadores para funciones específicas, junto con el control general a través de opciones de línea de comandos . La inserción se realiza automáticamente por muchos compiladores en muchos lenguajes, basándose en el juicio de si la inserción es beneficiosa, mientras que en otros casos se puede especificar manualmente a través de directivas del compilador , normalmente usando una palabra clave o directiva de compilador llamada inline . Por lo general, esto solo sugiere que se desea la inserción en línea, en lugar de requerir la inserción, con la fuerza de la sugerencia que varía según el lenguaje y el compilador.

Normalmente, los desarrolladores de compiladores tienen en cuenta los problemas de rendimiento anteriores 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.

Implementación

Una vez que el compilador ha decidido integrar una función en particular, realizar la operación de inserción en sí suele ser simple. Dependiendo de si el compilador en línea funciona a través del código en diferentes lenguajes, el compilador puede hacerlo en una representación intermedia de alto nivel (como árboles de sintaxis abstracta ) o 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 la llamada.

Los enlazadores también pueden hacer funciones de inserción. Cuando un enlazador funciona en línea, puede incluir funciones en línea cuya fuente no esté disponible, como las funciones de biblioteca (ver optimización del tiempo de enlace ). Un sistema en tiempo de ejecución también puede funcionar en línea. La integración en tiempo de ejecución puede utilizar información de perfiles dinámicos para tomar mejores decisiones sobre qué funciones incorporar, como en el compilador de Java Hotspot .

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

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

Antes de alinear:

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

Después de la alineación:

int func(int y) 
{
    int tmp;
    if (y   == 0) tmp  = 0; else tmp  = y - 1;       /* (1) */
    if (0   == 0) tmp += 0; else tmp += 0 - 1;       /* (2) */
    if (y+1 == 0) tmp += 0; else tmp += (y + 1) - 1; /* (3) */
    return tmp;
}

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

Inlining por ensamblaje macro expansión

Las macros de ensamblador proporcionan un enfoque alternativo al inlining mediante el cual una secuencia de instrucciones normalmente se puede generar en línea mediante la expansión de macro a partir de una única declaración de origen de macro (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 se procese en su lugar mediante una llamada en línea a la función. Ejemplo:

MOVE FROM=array1,TO=array2,INLINE=NO

Heurísticas

Se ha explorado una variedad de heurísticas diferentes para la inserción. Por lo general, un algoritmo de inserción tiene un presupuesto de código determinado (un aumento permitido en el tamaño del programa) y tiene como objetivo integrar los sitios de llamadas más valiosos sin exceder ese presupuesto. En este sentido, muchos algoritmos de inserción generalmente se modelan a partir del problema de Knapsack . Para decidir qué sitios de llamadas son más valiosos, un algoritmo en línea debe estimar su beneficio, es decir, la disminución esperada en el tiempo de ejecución. Normalmente, los inliners utilizan información de creación de perfiles sobre la frecuencia de ejecución de diferentes rutas de código para estimar los beneficios.

Además de la información de generación de perfiles, los compiladores just-in-time más nuevos aplican varias heurísticas más avanzadas, como:

  • Especular qué rutas de código dará como resultado la mejor reducción en el tiempo de ejecución (al permitir optimizaciones adicionales del compilador como resultado de la inserción) y aumentar el beneficio percibido de dichas rutas.
  • Ajustar de forma adaptativa el umbral de beneficio por costo para la inserción en función del tamaño de la unidad de compilación y la cantidad de código ya integrado.
  • Agrupar subrutinas en grupos e incluir grupos completos en lugar de subrutinas singulares. Aquí, la heurística adivina los clústeres agrupando aquellos métodos para los cuales insertar solo un subconjunto adecuado del clúster conduce a un rendimiento peor que insertar nada en absoluto.

Beneficios

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 el cuerpo de una función en el contexto de su sitio de llamada, a menudo con argumentos que pueden ser constantes fijas , es posible que pueda realizar 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 permitir la eliminación del código muerto , el movimiento del código invariante en bucle o la eliminación de la variable de inducción .

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

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

La nueva función se ve así:

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

Limitaciones

La expansión en línea completa no siempre es posible debido a la recursividad : la expansión en línea recursiva no termina las llamadas. Hay 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). Se produce un problema idéntico en la expansión de macros, ya que la expansión recursiva no termina y normalmente se resuelve prohibiendo las macros recursivas (como en C y C ++).

Comparación con macros

Tradicionalmente, en lenguajes como C , la expansión en línea se realizaba en el nivel de origen utilizando macros parametrizadas . El uso de verdaderas funciones en línea, como están disponibles en C99 , proporciona varios beneficios sobre este enfoque:

  • En C, las invocaciones de macros no realizan la verificación de tipos , ni siquiera verifican que los argumentos estén bien formados, mientras que las llamadas a funciones suelen hacerlo.
  • En C, una macro no puede usar la palabra clave return con el mismo significado que lo haría una función (haría que la función que solicitó la expansión terminara, 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 dentro de ella.
  • Dado que las macros de C utilizan una mera sustitución textual, esto puede provocar efectos secundarios no deseados e ineficacia debido a la reevaluación de los argumentos y el orden de las operaciones .
  • Los errores del compilador dentro de las macros a menudo son difíciles de entender, porque 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 en línea suele ser más útil que la del código expandido por macros.
  • Muchas construcciones son incómodas o imposibles de expresar usando macros, o usan una sintaxis significativamente diferente. Las funciones en línea utilizan la misma sintaxis que las funciones ordinarias, y se pueden insertar y quitar en línea a voluntad con facilidad.

Muchos compiladores también pueden expandir en línea algunas funciones recursivas ; 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.

Métodos de selección

Muchos compiladores funcionan agresivamente en línea siempre que sea beneficioso hacerlo. Aunque puede conducir a ejecutables más grandes , la inserción agresiva se ha vuelto cada vez más deseable ya que la capacidad de la memoria ha aumentado más rápido que la velocidad de la CPU. Inlining es una optimización crítica en lenguajes funcionales y lenguajes de programación orientados a objetos , que dependen de él para proporcionar suficiente contexto para sus funciones típicamente pequeñas para hacer efectivas las optimizaciones clásicas.

Ayuda de idioma

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. Otros lenguajes proporcionan construcciones para sugerencias explícitas, generalmente como directivas de compilación (pragmas).

En el lenguaje de programación Ada , existe un pragma para las funciones en línea.

Las funciones en Common Lisp pueden definirse como en línea mediante la inline declaración como tal:

 (declaim (inline dispatch))
 (defun dispatch (x)
   (funcall
     (get (car x) 'dispatch) x))

El compilador de Haskell GHC intenta integrar funciones o valores que son lo suficientemente pequeños, pero la inserción puede notarse explícitamente usando un pragma de lenguaje:

key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}

C y C ++

C y C ++ tienen una inline palabra clave, que funciona como una directiva del compilador, especificando que la inserción es deseada pero no requerida, 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 inserte a través de la cadena de herramientas C estándar, donde la compilación de archivos individuales (en lugar de unidades de traducción ) va seguida de la vinculación: para que el enlazador pueda incorporar funciones en línea, deben especificarse en el encabezado (para que sea visible) y marcado inline (para evitar la ambigüedad de múltiples definiciones).

Ver también

Notas

Referencias

enlaces externos