El almacenamiento en caché en línea es una técnica de optimización empleada por algunos tiempos de ejecución de lenguaje y desarrollada por primera vez para Smalltalk . [1] El objetivo del almacenamiento en caché en línea es acelerar el enlace de métodos en tiempo de ejecución recordando los resultados de una búsqueda de métodos anterior directamente en el sitio de la llamada . El almacenamiento en caché en línea es especialmente útil para lenguajes de tipado dinámico donde la mayoría, si no todos los enlaces de métodos, ocurren en tiempo de ejecución y donde las tablas de métodos virtuales a menudo no se pueden usar.
Enlace de método en tiempo de ejecución
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 . escribir ( obj . toString ()); }
Dado que no se especifica el tipo de objeto y debido a la posible sobrecarga del método , es imposible decidir con anticipación 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 tiempos de ejecución de lenguaje 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 pueden definirse varios pasos hacia abajo en la cadena de herencia , una búsqueda dinámica puede ser una operación costosa.
Para lograr un mejor rendimiento, muchos tiempos de ejecución de lenguaje emplean alguna forma 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, hay un conjunto limitado de métodos que se invocan con frecuencia). Esta estructura de datos se denomina típicamente caché de búsqueda de métodos de primer nivel . [1]
Almacenamiento en caché en línea
El concepto de almacenamiento en caché en línea se basa en la observación empírica de que los objetos que ocurren en un sitio de llamada particular son a menudo del mismo tipo. En esos casos, el rendimiento se puede aumentar considerablemente almacenando el resultado de una búsqueda de método "en línea", es decir, directamente en el sitio de la llamada. Para facilitar este proceso, a los sitios de llamadas se les asignan diferentes estados. Inicialmente, un sitio de llamada se considera "no inicializado". Una vez que el tiempo 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 la llamada y cambia su estado a "monomórfico". Si el tiempo de ejecución del idioma llega al mismo sitio de llamada nuevamente, recupera el destinatario de la llamada y lo invoca directamente sin realizar más búsquedas. Para tener en cuenta la posibilidad de que se produzcan objetos de diferentes tipos en el mismo sitio de llamada, el tiempo de ejecución del lenguaje también debe insertar condiciones de protección en el código. Por lo general, estos se insertan en el preámbulo del destinatario en lugar de en el sitio de la llamada para aprovechar mejor la predicción de rama y ahorrar espacio debido a una copia en el preámbulo frente a varias copias en cada sitio de llamada. Si un sitio de llamada que está en el estado "monomórfico" encuentra un tipo diferente al que espera, debe volver al estado "no inicializado" y realizar una búsqueda dinámica completa nuevamente.
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 llama mejor "desvinculado". 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, usando la caché de búsqueda de métodos de primer nivel anterior . La rutina en tiempo de ejecución luego reescribe las instrucciones, cambiando la instrucción de carga para cargar el registro con el tipo de 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 continúa inmediatamente después del preámbulo. Una ejecución posterior llamará directamente al preámbulo. A continuación, el preámbulo deriva el tipo de receptor actual y lo compara con el del registro; si están de acuerdo, el receptor es del mismo tipo y el método continúa ejecutándose. Si no es así, 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 la caché de búsqueda de métodos de primer nivel, y de usar una llamada directa (que se beneficiará de la captación previa de instrucciones y el revestimiento de tuberías) a diferencia de la llamada indirecta en una búsqueda de método o un envío vtable .
Almacenamiento en caché en línea monomórfico
Si un sitio de llamada en particular ve con frecuencia diferentes tipos de objetos, los beneficios de rendimiento del almacenamiento en caché en línea pueden anularse fácilmente por la sobrecarga inducida por los cambios frecuentes en el estado del sitio de llamada. El siguiente ejemplo constituye el peor de los casos para el almacenamiento en caché en línea monomórfico:
valores var = [ 1 , "a" , 2 , "b" , 3 , "c" , 4 , "d" ]; para ( var i en valores ) { document . escribir ( 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 de objeto cambia con cada iteración del bucle circundante. Por lo tanto, una implementación ingenua del almacenamiento en caché en línea monomórfico pasaría constantemente por los estados "no inicializado" 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". Este estado se ingresa 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á tal como lo hizo en el estado "no inicializado", con la excepción de que no volverá a entrar en el estado "monomórfico" (algunas implementaciones del almacenamiento en caché en línea monomórfico cambiarán " megamórficos "llaman a los sitios para que vuelvan a estar" sin inicializar "después de que haya pasado una cierta cantidad de tiempo o una vez que se haya realizado un ciclo completo de recolección de basura ).
Almacenamiento en caché en línea polimórfico
Para lidiar mejor con los sitios de llamadas que con frecuencia ven un número limitado de tipos diferentes, algunos tiempos 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 varios resultados de búsqueda de métodos en el mismo sitio de llamada. Debido a que cada sitio de llamada en un programa puede potencialmente ver todos los tipos en el sistema, generalmente hay un límite superior en 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 consiste en un preámbulo que deriva el tipo de receptor y una serie de comparaciones constantes y saltos condicionales que saltan al código siguiendo el preámbulo en el método relevante para cada tipo de receptor. La tabla de salto se asigna típicamente para un sitio de llamada particular cuando un sitio de llamada monomórfico encuentra un tipo diferente. La tabla de salto 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 alcance su tamaño máximo, se ejecutará para un nuevo tipo de receptor. se "caerá" al final y entrará en el tiempo de ejecución, normalmente para realizar una búsqueda de métodos 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 del tipo de receptor por sitio de llamada como 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 usando la información de tipo en cachés en línea para guiar decisiones especulativas en línea.
Almacenamiento en caché en línea megamórfico
Si un tiempo de ejecución utiliza almacenamiento en caché en línea tanto monomórfico como polimórfico, 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 los cachés en línea polimórficos. Dado que estos envíos son lentos, ahora puede resultar 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 al final de un caché en línea polimórfico, se crea un caché megamórfico específico para el selector del sitio de llamada (o se comparte si ya existe uno), 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 del registro, el código para la búsqueda y el envío se ejecuta sin llamar al tiempo de ejecución, y el envío puede beneficiarse de la predicción de ramas .
Las mediciones empíricas [3] muestran que en los grandes programas Smalltalk aproximadamente 1/3 de todos los sitios de envío en métodos activos permanecen desvinculados, y de los 2/3 restantes, el 90% son monomórficos, el 9% polimórficos y el 1% (0,9%) son megamórficos. .
Ver también
Referencias
- ^ a b c L. Peter Deutsch, Allan M. Schiffman, "Implementación eficiente del sistema smalltalk-80", POPL '84: Actas del 11 ° simposio ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación, enero de 1984
- ^ a b c Hölzle, U., Chambers, C., Y Ungar, D. 1991. Optimización de lenguajes orientados a objetos de tipo dinámico con cachés en línea polimórficos. En Actas de la Conferencia ECOOP '91. Notas de la conferencia en Ciencias de la Computación, vol. 512. Springer-Verlag, Berlín.
- ^ PIC [fue la primera impresión de la versión 8] en la lista de distribución de Strongtalk