El almacenamiento en caché en línea es una técnica de optimización empleada por algunos entornos de ejecución de lenguajes y desarrollada por primera vez 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 recordando los resultados de una búsqueda de método anterior directamente en el sitio de llamada . El almacenamiento en caché en línea es especialmente útil para lenguajes tipados dinámicamente donde la mayoría, 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 usar.
La siguiente función ECMAScript recibe un objeto, invoca su método toString y muestra los resultados en la página en la que está incrustado el script.
función dump ( obj ) { documento.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 va a invocar. En su lugar, se debe realizar una búsqueda dinámica en tiempo de ejecución. En los tiempos de ejecución de lenguajes que no emplean alguna forma de almacenamiento en caché, esta búsqueda se realiza cada vez que se invoca un método. Debido a que los métodos se pueden definir varios pasos 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 alguna forma de almacenamiento en caché no en línea, en el que los resultados de una cantidad limitada 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 memoria 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 se encuentran en un sitio de llamada en particular suelen ser del mismo tipo. En esos casos, el rendimiento se puede aumentar en gran medida almacenando el resultado de una búsqueda de método "en línea"; es decir, directamente en el sitio de llamada. Para facilitar este proceso, a los sitios de llamada se les asignan diferentes estados. Inicialmente, se considera que un sitio de llamada está "no inicializado". Una vez que el entorno de ejecución del lenguaje llega a un sitio de llamada no inicializado en particular, realiza la búsqueda dinámica, almacena el resultado en el sitio de llamada y cambia su estado a "monomórfico". Si el entorno de ejecución del lenguaje llega nuevamente al mismo sitio de llamada, recupera al destinatario de la llamada y lo invoca directamente sin realizar más búsquedas. Para tener en cuenta la posibilidad de que puedan aparecer objetos de diferentes tipos en el mismo sitio de llamada, el entorno de ejecución del lenguaje también tiene que insertar condiciones de protección en el código. Lo más común es que se inserten en el preámbulo del destinatario de la llamada en lugar de en el sitio de llamada para aprovechar mejor la predicción de bifurcaciones y ahorrar espacio debido a una copia en el preámbulo en lugar de múltiples copias en cada sitio de llamada. Si un sitio de llamada que está en estado "monomórfico" encuentra un tipo diferente al esperado, debe volver al estado "no inicializado" y realizar nuevamente una búsqueda dinámica completa.
La implementación canónica [1] es una carga de registro de una constante seguida de una instrucción de llamada. El estado "no inicializado" se denomina mejor "no vinculado". El registro se carga con el selector de mensajes (normalmente la dirección de algún objeto) y la llamada es a la rutina de tiempo de ejecución que buscará el mensaje en la clase del receptor actual, utilizando el caché de búsqueda de métodos de primer nivel mencionado anteriormente. La rutina de tiempo de ejecución luego 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, ahora "vinculando" el sitio de llamada al método de destino. La ejecución luego continúa inmediatamente después del preámbulo. Una ejecución posterior llamará al preámbulo directamente. El preámbulo luego deriva 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 al tiempo de ejecución y son posibles varias estrategias, una de las cuales es volver a vincular el sitio de llamada para el nuevo tipo de receptor.
Las ganancias de rendimiento provienen de tener que hacer una comparación de tipos, en lugar de al menos una comparación de tipos y una comparación de selectores para el caché de búsqueda de métodos de primer nivel, y de usar una llamada directa (que se beneficiará de la precarga de instrucciones y la canalización) en lugar de la llamada indirecta en una búsqueda de métodos o un envío de vtable .
Si un sitio de llamada en particular ve con frecuencia distintos tipos de objetos, los beneficios de rendimiento del almacenamiento en caché en línea pueden verse fácilmente anulados por la sobrecarga inducida por los cambios frecuentes en el estado del sitio de llamada. El siguiente ejemplo constituye un escenario de peor caso para el almacenamiento en caché en línea monomórfico:
var valores = [ 1 , "a" , 2 , "b" , 3 , "c" , 4 , "d" ]; for ( var i in valores ) { documento . write ( valores [ i ]. toString ()); } Nuevamente, el método toString se invoca en un objeto cuyo tipo no se conoce de antemano. Sin embargo, lo que es más importante, el tipo del objeto cambia con cada iteración del bucle circundante. Por lo tanto, una implementación ingenua de almacenamiento en caché en línea monomórfico pasaría constantemente por los estados "sin inicializar" y "monomórfico". Para evitar que esto suceda, la mayoría de las implementaciones de almacenamiento en caché en línea monomórfico admiten un tercer estado, a menudo denominado estado "megamórfico". Se ingresa a este estado cuando un sitio de llamada en particular ha visto una cantidad predeterminada de tipos diferentes. Una vez que un sitio de llamada ha ingresado al estado "megamórfico", se comportará tal como lo hizo en el estado "sin inicializar", con la excepción de que nunca más ingresará al estado "monomórfico" (algunas implementaciones de almacenamiento en caché en línea monomórfico cambiarán los sitios de llamada "megamórficos" a "sin inicializar" después de que haya transcurrido una cierta cantidad de tiempo o una vez que se realice un ciclo completo de recolección de basura ).
Para manejar mejor los sitios de llamada que frecuentemente ven un número limitado de tipos diferentes, algunos entornos de ejecución de lenguaje emplean una técnica llamada almacenamiento en caché en línea polimórfico. [2] Con el almacenamiento en caché en línea polimórfico, una vez que un sitio de llamada que está 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 sitio 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 actualmente. 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 sitio de llamada. Debido a que cada sitio de llamada en un programa puede ver potencialmente todos los tipos en el sistema, generalmente hay un límite superior para la cantidad de resultados de búsqueda que se registran en cada sitio de llamada. Una vez que se alcanza ese límite superior, los sitios 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 típicamente para 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 "caerá" al final y entrará en el tiempo de ejecución, típicamente 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, los cachés en línea monomórficos y polimórficos recopilan información sobre el 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 calientes" en el programa utilizando la información de tipo en los cachés en línea para guiar las decisiones de incrustación especulativa.
Si un entorno de ejecución utiliza tanto caché en línea monomórfica como polimórfica, entonces, en el estado estable, los únicos envíos no vinculados que se producirán serán los de los envíos que caen en los extremos de las cachés en línea polimórficas. Dado que estos 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 en particular. En este esquema, una vez que un envío cae en el 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 vincular para llamarlo. 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 envío se ejecuta sin llamar al entorno de ejecución y el envío puede beneficiarse de la predicción de bifurcación .
Las mediciones empíricas [3] muestran que en programas Smalltalk grandes, aproximadamente 1/3 de todos los sitios de envío en métodos activos permanecen sin vincular, y de los 2/3 restantes, el 90% son monomórficos, el 9% polimórficos y el 1% (0,9%) son megamórficos.