Almacenamiento en caché en línea

El almacenamiento en caché en línea es una técnica de optimización empleada por algunos entornos de ejecución de lenguajes , desarrollada inicialmente para Smalltalk . ^{[ 1 ]} El objetivo del almacenamiento en caché en línea es acelerar la vinculación de métodos en tiempo de ejecución al recordar los resultados de una búsqueda de método anterior directamente en el punto de llamada . El almacenamiento en caché en línea es especialmente útil para lenguajes de tipado dinámico , donde la mayor parte, si no toda, la vinculación de métodos ocurre en tiempo de ejecución y donde las tablas de métodos virtuales a menudo no se pueden utilizar.

La siguiente función de ECMAScript recibe un objeto, invoca su método toString y muestra los resultados en la página donde está insertado el script.

función dump ( obj ) { document . write ( obj . toString ()); }

Dado que no se especifica el tipo de objeto y debido a la posible sobrecarga de métodos , es imposible decidir de antemano qué implementación concreta del método `toString` se invocará. En su lugar, se debe realizar una búsqueda dinámica en tiempo de ejecución. En los entornos de ejecución de lenguajes que no utilizan algún tipo de almacenamiento en caché, esta búsqueda se realiza cada vez que se invoca un método. Dado que los métodos pueden definirse varios niveles más abajo en la cadena de herencia , una búsqueda dinámica puede ser una operación costosa.

Para lograr un mejor rendimiento, muchos entornos de ejecución de lenguajes emplean algún tipo de almacenamiento en caché no en línea, donde los resultados de un número limitado de búsquedas de métodos se almacenan en una estructura de datos asociativa . Esto puede aumentar considerablemente el rendimiento, siempre que los programas ejecutados sean compatibles con la caché (es decir, que haya un conjunto limitado de métodos que se invoquen con frecuencia). Esta estructura de datos se denomina normalmente caché de búsqueda de métodos de primer nivel . ^{[ 1 ]}

El concepto de almacenamiento en caché en línea se basa en la observación empírica de que los objetos que aparecen en un punto de llamada específico suelen ser del mismo tipo. En estos casos, el rendimiento puede mejorarse considerablemente almacenando el resultado de la búsqueda de un método directamente en el punto de llamada. Para facilitar este proceso, se asignan diferentes estados a los puntos de llamada. Inicialmente, un punto de llamada se considera "no inicializado". Una vez que el entorno de ejecución del lenguaje llega a un punto de llamada no inicializado, realiza la búsqueda dinámica, almacena el resultado en el punto de llamada y cambia su estado a "monomórfico". Si el entorno de ejecución del lenguaje vuelve a llegar al mismo punto de llamada, recupera la función llamada y la invoca directamente sin realizar más búsquedas. Para tener en cuenta la posibilidad de que aparezcan objetos de diferentes tipos en el mismo punto de llamada, el entorno de ejecución del lenguaje también debe insertar condiciones de guarda en el código. Generalmente, estas se insertan en el preámbulo de la función llamada en lugar de en el punto de llamada para aprovechar mejor la predicción de bifurcaciones y ahorrar espacio, ya que se utiliza una sola copia en el preámbulo en lugar de varias copias en cada punto de llamada. Si un punto de llamada que se encuentra en el estado "monomórfico" encuentra un tipo distinto al que espera, tiene que volver al estado "no inicializado" y realizar de nuevo una búsqueda dinámica completa.

La implementación canónica ^{[ 1 ]} consiste en la carga de un registro con una constante, seguida de una instrucción de llamada. El estado "no inicializado" se denomina mejor "no enlazado". El registro se carga con el selector de mensaje (normalmente la dirección de algún objeto) y la llamada se realiza a la rutina de tiempo de ejecución, que buscará el mensaje en la clase del receptor actual, utilizando la caché de búsqueda de métodos de primer nivel mencionada anteriormente. La rutina de tiempo de ejecución reescribe las instrucciones, cambiando la instrucción de carga para cargar el registro con el tipo del receptor actual y la instrucción de llamada para llamar al preámbulo del método de destino, "enlazando" ahora el sitio de llamada al método de destino. La ejecución continúa inmediatamente después del preámbulo. Una ejecución posterior llamará directamente al preámbulo. El preámbulo deriva entonces el tipo del receptor actual y lo compara con el del registro; si coinciden, el receptor es del mismo tipo y el método continúa ejecutándose. Si no, el preámbulo vuelve a llamar a la rutina de tiempo de ejecución y son posibles varias estrategias, una de ellas es volver a enlazar el sitio de llamada para el nuevo tipo de receptor.

Las mejoras en el rendimiento provienen de tener que realizar una sola comparación de tipos, en lugar de al menos una comparación de tipos y una comparación de selectores para la caché de búsqueda de métodos de primer nivel, y de utilizar una llamada directa (que se beneficiará de la precarga de instrucciones y la segmentación) en contraposición a la llamada indirecta en una búsqueda de métodos o un despacho de tabla virtual .

Si un punto de llamada específico recibe con frecuencia diferentes tipos de objetos, las ventajas de rendimiento del almacenamiento en caché en línea pueden verse fácilmente anuladas por la sobrecarga derivada de los frecuentes cambios de estado de dicho punto. El siguiente ejemplo constituye el peor escenario posible para el almacenamiento en caché en línea monomórfico:

var values ​​= [ 1 , "a" , 2 , "b" , 3 , "c" , 4 , "d" ]; for ( var i in values ​​) { document . write ( values ​​[ i ]. toString ()); }

Nuevamente, el método toString se invoca en un objeto cuyo tipo no se conoce de antemano. Sin embargo, lo más importante es que el tipo del objeto cambia con cada iteración del bucle circundante. Por lo tanto, una implementación ingenua de almacenamiento en caché monomórfico en línea alternaría constantemente entre los estados "no inicializado" y "monomórfico". Para evitar que esto suceda, la mayoría de las implementaciones de almacenamiento en caché monomórfico en línea admiten un tercer estado, a menudo denominado estado "megamórfico". Este estado se alcanza cuando un sitio de llamada particular ha visto un número predeterminado de tipos diferentes. Una vez que un sitio de llamada ha entrado en el estado "megamórfico", se comportará igual que en el estado "no inicializado", con la excepción de que nunca volverá a entrar en el estado "monomórfico" (algunas implementaciones de almacenamiento en caché monomórfico en línea revierten los sitios de llamada "megamórficos" al estado "no inicializado" después de que haya transcurrido cierto tiempo o una vez que se haya realizado un ciclo completo de recolección de basura ).

Para gestionar mejor los puntos de llamada que frecuentemente ven un número limitado de tipos diferentes, algunos entornos de ejecución de lenguajes emplean una técnica denominada almacenamiento en caché en línea polimórfico. ^{[ 2 ]} Con el almacenamiento en caché en línea polimórfico, una vez que un punto de llamada que se encuentra en su estado "monomórfico" ve su segundo tipo, en lugar de volver al estado "no inicializado", cambia a un nuevo estado llamado "polimórfico". Un punto de llamada "polimórfico" decide cuál de un conjunto limitado de métodos conocidos invocar en función del tipo que se le presenta en ese momento. En otras palabras, con el almacenamiento en caché en línea polimórfico, se pueden registrar múltiples resultados de búsqueda de métodos en el mismo punto de llamada. Dado que cada punto de llamada en un programa puede ver potencialmente todos los tipos del sistema, suele haber un límite superior en la cantidad de resultados de búsqueda que se registran en cada punto de llamada. Una vez que se alcanza ese límite superior, los puntos de llamada se vuelven "megamórficos" y no se realiza más almacenamiento en caché en línea.

La implementación canónica ^{[ 2 ]} es una tabla de saltos que consta de un preámbulo que deriva el tipo del receptor y una serie de comparaciones constantes y saltos condicionales que saltan al código que sigue al preámbulo en el método relevante para cada tipo de receptor. La tabla de saltos se asigna normalmente a un sitio de llamada particular cuando un sitio de llamada monomórfico encuentra un tipo diferente. La tabla de saltos tendrá un tamaño fijo y podrá crecer, agregando casos a medida que se encuentren nuevos tipos hasta un pequeño número máximo de casos como 4, 6 u 8. Una vez que alcanza su tamaño máximo, la ejecución para un nuevo tipo de receptor "desaparecerá" del final y entrará en el tiempo de ejecución, normalmente para realizar una búsqueda de método comenzando con la caché de métodos de primer nivel.

La observación de que, en conjunto, las cachés en línea monomórficas y polimórficas recopilan información del tipo de receptor por sitio de llamada como un efecto secundario de la optimización de la ejecución del programa ^{[ 2 ]} condujo al desarrollo de la optimización adaptativa en Self , donde el tiempo de ejecución optimiza los "puntos críticos" en el programa utilizando la información de tipo en las cachés en línea para guiar las decisiones de inserción especulativa.

Si un entorno de ejecución utiliza caché en línea monomórfica y polimórfica, en estado estable, los únicos envíos no enlazados que se produzcan serán aquellos de envíos que caen fuera de los extremos de las cachés en línea polimórficas. Dado que dichos envíos son lentos, ahora puede ser rentable optimizar estos sitios. Se puede implementar una caché en línea megamórfica creando código para realizar una búsqueda de método de primer nivel para un sitio de llamada particular. En este esquema, una vez que un envío cae fuera del extremo de una caché en línea polimórfica, se crea una caché megamórfica específica para el selector del sitio de llamada (o se comparte si ya existe una), y el sitio de envío se vuelve a enlazar para llamarla. El código puede ser significativamente más eficiente que una sonda de búsqueda de método de primer nivel normal ya que el selector ahora es una constante, lo que disminuye la presión de registro, el código para la búsqueda y el despacho se ejecuta sin llamar al entorno de ejecución, y el despacho puede beneficiarse de la predicción de bifurcación .

Las mediciones empíricas ^{[ 3 ]} muestran que en los programas Smalltalk grandes, alrededor de 1/3 de todos los sitios de envío en los métodos activos permanecen sin enlazar, y de los 2/3 restantes, el 90% son monomórficos, el 9% polimórficos y el 1% (0,9%) son megamórficos.

• Memorización

• Artículo sobre el almacenamiento en caché en línea en la máquina virtual Cog Smalltalk