¿Qué estrategias de despacho de código de operación se usan en intérpretes eficientes?

¿Qué técnicas promueven el despacho eficiente de código de operación para hacer un intérprete rápido? ¿Hay algunas técnicas que solo funcionan bien en el hardware moderno y otras que ya no funcionan bien debido a los avances del hardware? ¿Qué compensaciones se deben hacer entre facilidad de implementación, velocidad y portabilidad?¿Qué estrategias de despacho de código de operación se usan en intérpretes eficientes?

Me complace que la implementación C de Python finalmente vaya más allá de una simple implementación switch (opcode) {...} para el envío de código de operación a subprocesamiento indirecto como una opción de tiempo de compilación, pero estoy menos contento de que hayan tardado 20 años en llegar. Quizás si documentamos estas estrategias en stackoverflow, el siguiente idioma se acelerará más rápido.

Fuente

2009-02-04 joeforker

Realmente editas preguntas tan drásticamente después de que hay respuestas. Las buenas respuestas para su pregunta en su primera forma no son buenas respuestas ahora. – Darron

Lamento decepcionar, pero la pregunta original era demasiado vaga. Si te hace sentir mejor, mi idea de la pregunta fue la misma durante todo el proceso, y siéntete libre de editar tu respuesta, por la que he votado. – joeforker

Hay una serie de documentos sobre diferentes tipos de expedición:

M. Antón Ertl y David Gregg, Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters, en Actas de la Conferencia ACM SIGPLAN 2003 sobre Diseño Lenguaje de Programación y Ejecución (PLDI 03), pp 278-288, San Diego, California, junio de 2003.

M. Anton Ertl y David Gregg, The behaviour of efficient virtual machine interpreters on modern architectures, en Procedimientos de la 7ma Conferencia Europea de Computación en Paralelo (Europar 2001), pp. 403-412, LNCS 2150 , Manchester, agosto de 2001.

Un excelente resumen es proporcionado por Yunhe Shi in his PhD thesis. Hace

Además, someone discovered a new technique unos años que es válido ANSI C

Fuente

2009-07-29 16:10:59

Just-in-time compilation es uno.

Fuente

2009-02-04 14:28:30

Estoy intrigado por esta compilación "JIT", pero ¿qué me compra? ¿El programa comenzará a ejecutarse tan rápido como un intérprete que no hace JIT? ¿Utilizará más memoria? ¿Debería JIT el programa completo, o solo los puntos calientes? ¿Tengo que trabajar más para ejecutar ARM y x86? – joeforker

Pude malinterpretar tu pregunta ... No sé nada sobre cómo hacer JIT en realidad, solo que ahora se usa mucho en bytecode y otros intérpretes (Java y Javascript y MATLAB lo usan todos). –

Estoy buscando el nombre de la técnica, una breve explicación y una razón por la que puede elegir esa técnica en particular. JIT usa más memoria, probablemente demore más en iniciarse, pero puede ser muy rápido. El mayor inconveniente es que el JIT depende de la plataforma. – joeforker

Antes de comenzar, marque Lua.

Es pequeño (150Kb), puro ANSI C, funciona en cualquier cosa que tenga el compilador C. Muy rapido.

Y lo más importante: el código fuente es limpio y legible. Vale la pena echarle un vistazo.

Fuente

2009-02-04 14:36:51 dmajkic

lua es maravilloso. Disfruté especialmente el artículo sobre su implementación de matrices indexadas en número y hash en la misma estructura de datos. Poner matrices basadas en cero en la siguiente y estoy a bordo :-) – joeforker

Benchmarking es una buena técnica para hacer cualquier cosa rápida en plataforma (s) determinada (s). Pruebe, refine, pruebe de nuevo, mejore.

No creo que pueda obtener una respuesta mejor. Hay muchas técnicas para hacer intérpretes. Pero te doy un consejo, no hagas concesiones, solo elige lo que realmente necesitas y persigue esos objetivos.

Fuente

2009-02-04 14:58:34 Cheery

Las compensaciones son inevitables. C es rápido, pero solo puedes ejecutar el binario en una plataforma. Java se ejecuta en muchas plataformas, pero necesita un gran tiempo de ejecución inteligente. – joeforker

Una gran victoria es almacenar el código fuente en una forma intermedia, en lugar de rehacer el análisis léxico y el análisis durante la ejecución.

Esto puede abarcar desde el simple almacenamiento de los tokens, pasando por el código de estilo Forth y la compilación JIT.

Fuente

2009-02-04 15:05:15 Darron

La pregunta es un poco vaga. Pero, parece que estás preguntando por escribir un intérprete.

Los intérpretes suelen utilizar componentes de análisis tradicionales: lexer, analizador sintáctico y árbol de sintaxis abstracta (AST). Esto le permite al diseñador leer e interpretar la sintaxis válida y construir una estructura en árbol de comandos con operadores asociados, parámetros, etc.

Una vez en formato AST, toda la entrada se tokeniza y el intérprete puede comenzar a ejecutar atravesando el árbol.

Hay muchas opciones, pero recientemente utilicé ANTLR como un generador de analizadores que puede construir analizadores en varios idiomas de destino, incluyendo C/C++ y C#.

Fuente

2009-02-04 15:14:28 spoulson

¿No es el AST el resultado de haber tokenizado primero el código fuente y luego haberlo analizado? – Trap

Me parece una pregunta bastante específica. La interpretación directa de un AST tiene que ser una de las formas más ineficientes de escribir un intérprete, por lo que su respuesta realmente no funciona para esta pregunta. –

El subproceso indirecto es una estrategia donde cada implementación de código de operación tiene su propia JMP en el siguiente código de operación. El parche para el intérprete de Python es como la siguiente:

add: 
    result = a + b; 
    goto *opcode_targets[*next_instruction++];

opcode_targets mapas de la instrucción en el código de bytes de la lengua a la ubicación en la memoria de la ejecución de código de operación. Esto es más rápido porque el predictor de bifurcación del procesador puede hacer una predicción diferente para cada bytecode, en contraste con una declaración switch que tiene solo una instrucción de bifurcación.

El compilador debe ser compatible con goto computarizado para que esto funcione, lo que principalmente significa gcc.

enhebrado directo es similar, pero en el roscado directo el conjunto de códigos de operación se sustituye con punteros a los implentations código de operación de este modo:

goto *next_opcode_target++;

Estas técnicas sólo son útiles porque los procesadores modernos se pipeline y deben limpiar sus tuberías (lento) en una rama mal predicha. Los diseñadores de procesadores introdujeron la predicción de bifurcación para evitar tener que borrar la canalización con tanta frecuencia, pero la predicción de bifurcación solo funciona para las sucursales que tienen más probabilidades de tomar una ruta particular.

Fuente

2009-02-04 16:01:06 joeforker

true para procesadores que realizan predicción de bifurcación, incluidos x86, x86_64, etc. – Cheery

@Cheery no es la arquitectura sino el modelo de procesador específico que incluye la predicción de bifurcación, pero sería difícil leer el stackoverflow con un procesador que no lo implemente. – joeforker

me encontré con una entrada de blog sobre la aplicación intérprete roscado que era útil.

El autor describe el enhebrado basado en etiquetas de GCC y también cómo hacerlo en Visual Studio utilizando el ensamblador en línea.

http://abepralle.wordpress.com/2009/01/25/how-not-to-make-a-virtual-machine-label-based-threading/

Los resultados son interesantes. Informa que mejora el rendimiento al 33% cuando usa GCC, pero sorprendentemente la implementación de ensamblaje en línea de Visual Studio es 3 veces más lenta.

Fuente

2010-11-11 17:33:01

¿Qué estrategias de despacho de código de operación se usan en intérpretes eficientes?

Respuesta

Cuestiones relacionadas