"No importa cuánto lo intentes, no puedes hacer un caballo de carreras con un cerdo. Sin embargo, puedes hacer un cerdo más rápido" (comentario en el código fuente de Emax)
Todos saben que los cerdos no vuelan. Igualmente popular es la opinión de que los intérpretes de bytecode como técnica para ejecutar lenguajes de alto nivel no pueden acelerarse sin el uso de una compilación dinámica que consume mucho tiempo.
En la segunda parte de una serie de artículos sobre intérpretes de código de bytes, intentaré mostrar con el ejemplo de una pequeña máquina virtual apilada de la FDA (Máquina virtual de cerdo) que no todo se pierde para los lechones trabajadores con ambiciones y que es muy posible acelerar dentro del marco del estándar (en su mayoría) C El trabajo de tales intérpretes es al menos una vez y media.
Primera parte, introductoria
Segunda parte, optimización (actual)
Tercera parte, aplicada
Cochinillo
Vamos a conocernos.
Piglet VM es una máquina apilada ordinaria basada en un ejemplo de la primera parte de una serie de artículos. Nuestro cerdo solo conoce un tipo de datos: una palabra de máquina de 64 bits, y todos los cálculos (enteros) se realizan en la pila con una profundidad máxima de 256 palabras de máquina. Además de la pila, este lechón tiene una memoria de trabajo de 65.536 palabras de máquina. El resultado de la ejecución del programa, una palabra de máquina, puede colocarse en el registro de resultados o simplemente enviarse a la salida estándar (stdout).
Todo el estado en la máquina Piglet VM se almacena en una sola estructura:
static struct { uint8_t *ip; uint64_t stack[STACK_MAX]; uint64_t *stack_top; uint64_t memory[MEMORY_SIZE]; uint64_t result; } vm;
Lo anterior nos permite atribuir esta máquina a máquinas virtuales de bajo nivel, casi toda la sobrecarga en la que recae el mantenimiento del ciclo principal del programa:
interpret_result vm_interpret(uint8_t *bytecode) { vm_reset(bytecode); for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { case OP_PUSHI: { uint16_t arg = NEXT_ARG(); PUSH(arg); break; } case OP_ADD: { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; break; } case OP_DONE: { return SUCCESS; } default: return ERROR_UNKNOWN_OPCODE; } } return ERROR_END_OF_STREAM; }
El código muestra que para cada código de operación, el piggy debe:
- Recupere el código de operación del flujo de instrucciones.
- Asegúrese de que el código de operación esté en el rango válido de valores de código de operación (esta lógica es agregada por el compilador de C al generar el código del interruptor).
- Ir a las instrucciones del cuerpo.
- Extraiga argumentos de instrucciones de la pila o decodifique un argumento de instrucciones ubicado directamente en el código de bytes.
- Realizar una operación
- Si hay un resultado del cálculo, colóquelo en la pila.
- Mueva el puntero de la instrucción actual a la siguiente.
La carga útil aquí solo se encuentra en el quinto párrafo, el resto está sobrecargado: decodificando o recuperando instrucciones de la pila (cláusula 4), verificando el valor del código de operación (cláusula 2), volviendo repetidamente al comienzo del bucle principal y al siguiente salto condicional difícilmente predicho (cláusula 3).
En resumen, el cerdo ha superado claramente el índice de masa corporal recomendado, y si queremos ponerlo en forma, tendremos que lidiar con todos estos excesos.
Lenguaje ensamblador de cerdos y tamiz de Eratóstenes
Primero, decidamos las reglas del juego.
Escribir programas para una máquina virtual directamente en C es una mala idea, pero crear un lenguaje de programación es mucho tiempo, por lo que decidimos limitarnos a un lenguaje ensamblador guarro.
Un programa que calcula la suma de números del 1 al 65,536 en este ensamblador se parece a esto:
# sum numbers from 1 to 65535 # init the current sum and the index PUSHI 1 PUSHI 1 # stack s=1, i=1 STOREI 0 # stack: s=1 # routine: increment the counter, add it to the current sum incrementandadd: # check if index is too big LOADI 0 # stack: s, i ADDI 1 # stack: s, i+1 DUP # stack: s, i+1, i+1 GREATER_OR_EQUALI 65535 # stack: s, i+1, 1 or 0 JUMP_IF_TRUE done # stack: s, i+1 DUP # stack: s, i+1, i+1 STOREI 0 # stack: s, i+1 ADD # stack: s+i+1 JUMP incrementandadd done: DISCARD PRINT DONE
No Python, por supuesto, pero hay todo lo que necesitas para la felicidad del cerdo: comentarios, etiquetas, saltos condicionales e incondicionales, mnemotécnicos para obtener instrucciones y la capacidad de especificar argumentos directos a las instrucciones.
Completo con la máquina "Piglet VM" hay ensamblador y desensamblador, que son valientes en espíritu y tienen mucho tiempo libre, los lectores pueden probar de forma independiente en la batalla.
Los números se suman muy rápidamente, así que para probar el rendimiento escribí otro programa: una implementación ingenua del tamiz de Eratóstenes .
De hecho, el lechón se ejecuta bastante rápido de todos modos (sus instrucciones son similares a las de la máquina), por lo tanto, para obtener resultados claros, haré cada medición durante cien inicios del programa.
La primera versión de nuestro cerdo no optimizado funciona así:
> ./pigletvm runtimes test/sieve-unoptimized.bin 100 > /dev/null PROFILE: switch code finished took 545ms
¡Medio segundo! La comparación es ciertamente deshonesta, pero el mismo algoritmo de Python hace que cien ejecuciones sean un poco más lentas:
> python test/sieve.py > /dev/null 4.66692185402
4.5 segundos, o nueve veces más lento. Debemos rendir homenaje al lechón: ¡tiene la habilidad! Bueno, ahora veamos si nuestro cerdo puede inflar la prensa.
Ejercicio uno: superinstrucciones estáticas
La primera regla del código rápido es no hacer demasiado trabajo. La segunda regla del código rápido es nunca hacer demasiado trabajo. Entonces, ¿qué tipo de trabajo adicional hace Piglet VM?
Observación uno: el perfil de nuestro programa muestra que hay secuencias de instrucciones que son más comunes que otras. No atormentaremos mucho a nuestro cerdo y nos limitaremos a solo un par de instrucciones:
- LOADI 0, ADD: coloque en la pila un número de la memoria en la dirección 0 y agréguelo al número en la parte superior de la pila.
- PUSHI 65536, GREATER_OR_EQUAL: coloque un número en la pila y compárelo con el número que estaba anteriormente en la parte superior de la pila, colocando el resultado de la comparación (0 o 1) nuevamente en la pila.
- PUSHI 1, ADD: coloque un número en la pila, agréguelo al número que estaba anteriormente en la parte superior de la pila y coloque el resultado de la suma nuevamente en la pila.
Hay un poco más de 20 instrucciones en la máquina Piglet VM, y se utiliza un byte completo para la codificación: 256 valores. Introducir nuevas instrucciones no es un problema. Lo que haremos:
for (;;) { uint8_t instruction = NEXT_OP(); switch (instruction) { case OP_LOADADDI: { uint16_t addr = NEXT_ARG(); uint64_t val = vm.memory[addr]; *TOS_PTR() += val; break; } case OP_GREATER_OR_EQUALI:{ uint64_t arg_right = NEXT_ARG(); *TOS_PTR() = PEEK() >= arg_right; break; } case OP_ADDI: { uint16_t arg_right = NEXT_ARG(); *TOS_PTR() += arg_right; break; } }
Nada complicado Veamos que salió de eso:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 410ms
Wow! ¡El código es solo para tres nuevas instrucciones, y ganamos cien milisegundos!
La ganancia aquí se logra debido al hecho de que nuestro piggy no realiza movimientos innecesarios al ejecutar tales instrucciones: el hilo de ejecución no cae en el bucle principal, no se decodifica nada, y los argumentos de las instrucciones no vuelven a pasar por la pila.
Esto se denomina superinstrucciones estáticas, ya que el programador de máquina virtual define las instrucciones adicionales de forma estática en la etapa de desarrollo. Esta es una técnica simple y efectiva que todas las máquinas virtuales de lenguajes de programación usan de una forma u otra.
El principal problema con las superinstrucciones estáticas es que sin un programa específico es imposible determinar qué instrucciones se deben combinar. Los diferentes programas utilizan diferentes secuencias de instrucciones, y puede encontrar estas secuencias solo en la etapa de lanzamiento de un código específico.
El siguiente paso podría ser la compilación dinámica de superinstrucciones en el contexto de un programa en particular, es decir, superinstrucciones dinámicas (en los años 90 y principios de 2000, esta técnica desempeñó el papel de una compilación JIT primitiva).
Es imposible crear instrucciones sobre la marcha en el marco de la C ordinaria, y nuestro lechón con toda razón no lo considera una competencia honesta. Afortunadamente, tengo un par de mejores ejercicios para él.
Ejercicio dos: verificar el rango de valores del código de operación
Siguiendo nuestras reglas de código rápido, una vez más nos hacemos la eterna pregunta: ¿qué no puedes hacer?
Cuando nos familiarizamos con el dispositivo de la máquina Piglet VM, enumeré todas las acciones que realiza la máquina virtual para cada código de operación. Y el punto 2 (comprobar el valor del código de operación para que se ajuste al rango válido de valores de cambio) es el más sospechoso.
Echemos un vistazo a cómo GCC compila la construcción del interruptor:
- Se construye una tabla de transición, es decir, una tabla que muestra el valor del código de operación en la dirección del código que ejecuta el cuerpo de la instrucción.
- Se inserta un código que verifica si el código de operación recibido se encuentra dentro del rango de todos los valores de cambio posibles y lo envía a la etiqueta predeterminada si no hay un controlador para el código de operación.
- Se inserta el código que va al controlador.
Pero, ¿por qué verificar el intervalo de valores para cada instrucción? Creemos que el código de operación es correcto - terminando la ejecución por la instrucción OP_DONE, o incorrecto - yendo más allá del código de bytes. La cola de la secuencia de códigos de operación está marcada con cero, y cero es el código de operación de la instrucción OP_ABORT, que completa la ejecución del código de bytes con un error.
¡Resulta que esta verificación no es necesaria en absoluto! Y el lechón debería poder transmitir esta idea al compilador. Intentemos arreglar un poco el interruptor principal:
uint8_t instruction = NEXT_OP(); switch (instruction & 0x1f) { case 26 ... 0x1f: { return ERROR_UNKNOWN_OPCODE; } }
Sabiendo que solo tenemos 26 instrucciones, imponemos una máscara de bits (el valor octal 0x1f es un 0b11111 binario que cubre el rango de valores de 0 a 31) en el código de operación y agregamos controladores a valores no utilizados en el rango de 26 a 31.
Las instrucciones de bit son algunas de las más baratas en la arquitectura x86, y ciertamente son más baratas que las ramas condicionales problemáticas como la que usa la comprobación de intervalos. Teóricamente, deberíamos ganar varios ciclos en cada instrucción ejecutable si el compilador comprende nuestra sugerencia.
Por cierto, la forma de especificar el rango de valores en caso de que no sea C estándar, sino una extensión GCC. Pero para nuestro propósito, este código es adecuado, especialmente porque no es difícil rehacerlo en varios controladores para cada uno de los valores innecesarios.
Intentamos:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 437ms PROFILE: switch code (no range check) finished took 383ms
¡Otros 50 milisegundos! Piglet, ¡es como si te hubieras escuchado en tus hombros! ..
Ejercicio tres: senderos
¿Qué otros ejercicios pueden ayudar a nuestro lechón? El mayor ahorro de tiempo que obtuvimos gracias a las súper instrucciones. Y reducen el número de salidas al ciclo principal y le permiten deshacerse de los costos generales correspondientes.
El interruptor central es el principal problema para cualquier procesador con una ejecución extraordinaria de instrucciones. Los predictores de ramificación modernos han aprendido a predecir incluso transiciones indirectas tan complejas, pero los puntos de ramificación "borrosos" a lo largo del código pueden ayudar al procesador a cambiar rápidamente de una instrucción a otra.
Otro problema es la lectura byte por byte de códigos de operación y argumentos directos de bytecode. Las máquinas físicas funcionan con una palabra de máquina de 64 bits y realmente no les gusta cuando el código funciona con valores más bajos.
Los compiladores a menudo operan con bloques básicos , es decir, secuencias de instrucciones sin ramas y etiquetas dentro. El bloque base comienza desde el comienzo del programa o desde la etiqueta, y termina con el final del programa, la ramificación condicional o un salto directo a la etiqueta que inicia el siguiente bloque base.
Trabajar con unidades base tiene muchas ventajas, pero nuestro cerdo está interesado en su característica clave: las instrucciones dentro de la unidad base se ejecutan secuencialmente. Sería genial aislar de alguna manera estos bloques base y seguir las instrucciones en ellos sin perder tiempo entrando en el bucle principal.
En nuestro caso, incluso puede extender la definición de la unidad base a la pista. La pista en términos de la máquina Piglet VM incluirá todos los bloques base conectados secuencialmente (es decir, utilizando saltos incondicionales).
Además de la ejecución secuencial de instrucciones, sería bueno decodificar los argumentos directos de las instrucciones de antemano.
Todo suena bastante aterrador y se asemeja a una compilación dinámica, que decidimos no usar. El cerdo incluso dudó un poco de su fuerza, pero en la práctica no resultó tan malo.
Primero pensemos en cómo puedes imaginar la instrucción incluida en la pista:
struct scode { uint64_t arg; trace_op_handler *handler; };
Aquí arg es el argumento predescodificado de la instrucción, y handler es un puntero a una función que ejecuta la lógica de la instrucción.
Ahora la vista de cada rastro se ve así:
typedef scode trace[MAX_TRACE_LEN];
Es decir, una traza es una secuencia de códigos s de longitud limitada. El caché de seguimiento en sí dentro de la máquina virtual se ve así:
trace trace_cache[MAX_CODE_LEN];
Esto es solo un conjunto de trazas con una longitud que no excede la longitud posible del código de bytes. La solución es perezosa, para ahorrar memoria tiene sentido usar una tabla hash.
Al comienzo del intérprete, el primer controlador de cada rastreo se compilará:
for (size_t trace_i = 0; trace_i < MAX_CODE_LEN; trace_i++ ) vm_trace.trace_cache[trace_i][0].handler = trace_compile_handler;
El bucle principal de intérprete ahora se ve así:
while(vm_trace.is_running) { scode *code = &vm_trace.trace_cache[vm_trace.pc][0]; code->handler(code); }
Un compilador de rastreo es un poco más complicado, y además de construir un rastreo a partir de la instrucción actual, hace lo siguiente:
static void trace_compile_handler(scode *trace_head) { scode *trace_tail = trace_head; trace_head->handler(trace_head); }
Instructor de instrucciones normales:
static void op_add_handler(scode *code) { uint64_t arg_right = POP(); *TOS_PTR() += arg_right; code++; code->handler(code); }
Un controlador que no realiza ninguna llamada en la cola de la función termina cada rastreo:
static void op_done_handler(scode *code) { (void) code; vm_trace.is_running = false; vm_trace.error = SUCCESS; }
Todo esto, por supuesto, es más complicado que agregar superinstrucciones, pero veamos si nos dio algo:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 427ms PROFILE: switch code (no range check) finished took 395ms PROFILE: trace code finished took 367ms
¡Hurra, otros 30 milisegundos!
¿Cómo es eso? En lugar de simplemente navegar por las etiquetas, hacemos cadenas de llamadas de controladores de instrucciones, dedicamos tiempo a las llamadas y a pasar argumentos, pero nuestro cerdito sigue corriendo por los senderos más rápido que un simple interruptor con sus etiquetas.
Esta ganancia en el rendimiento de la pista se logra debido a tres factores:
- Predecir ramas dispersas en diferentes lugares del código es fácil.
- Los argumentos de los controladores siempre se codifican previamente en una palabra de máquina completa, y esto se hace solo una vez, durante la compilación de la traza.
- El compilador convierte las cadenas de funciones en una sola llamada a la primera función del controlador, lo cual es posible debido a la optimización de la llamada de cola .
Antes de resumir los resultados de nuestro entrenamiento, el lechón y yo decidimos probar otra técnica antigua para interpretar programas: el código cosido.
Ejercicio cuatro: código "cosido"
Cualquier cerdo interesado en la historia de los intérpretes escuchó un código roscado. Hay muchas opciones para esta técnica, pero todas se reducen a, en lugar de seguir una matriz de códigos de operación, siguiendo una matriz de, por ejemplo, punteros a funciones o etiquetas, siguiéndolas directamente sin un código de operación intermedio.
Llamar a funciones es un negocio costoso y sin sentido en estos días; la mayoría de las otras versiones de código cosido no se pueden realizar dentro del marco del estándar C. Incluso la técnica, que se discutirá a continuación, utiliza los extensos, pero no estándar, punteros en C para las etiquetas.
En la versión del código cosido (código enroscado de token en inglés) que elegí para lograr nuestros objetivos de cerdo, guardamos el código de bytes, pero antes de comenzar la interpretación, creamos una tabla que muestra los códigos de operación de las instrucciones en la dirección de las etiquetas del manejador de instrucciones:
const void *labels[] = { [OP_PUSHI] = &&op_pushi, [OP_LOADI] = &&op_loadi, [OP_LOADADDI] = &&op_loadaddi, [OP_STORE] = &&op_store, [OP_STOREI] = &&op_storei, [OP_LOAD] = &&op_load, [OP_DUP] = &&op_dup, [OP_DISCARD] = &&op_discard, [OP_ADD] = &&op_add, [OP_ADDI] = &&op_addi, [OP_SUB] = &&op_sub, [OP_DIV] = &&op_div, [OP_MUL] = &&op_mul, [OP_JUMP] = &&op_jump, [OP_JUMP_IF_TRUE] = &&op_jump_if_true, [OP_JUMP_IF_FALSE] = &&op_jump_if_false, [OP_EQUAL] = &&op_equal, [OP_LESS] = &&op_less, [OP_LESS_OR_EQUAL] = &&op_less_or_equal, [OP_GREATER] = &&op_greater, [OP_GREATER_OR_EQUAL] = &&op_greater_or_equal, [OP_GREATER_OR_EQUALI] = &&op_greater_or_equali, [OP_POP_RES] = &&op_pop_res, [OP_DONE] = &&op_done, [OP_PRINT] = &&op_print, [OP_ABORT] = &&op_abort, };
Preste atención a los símbolos &&: estos son punteros a las etiquetas con los cuerpos de las instrucciones, la extensión más no estándar de GCC.
Para comenzar a ejecutar el código, simplemente haga clic en el puntero correspondiente al primer código de operación del programa:
goto *labels[NEXT_OP()];
No hay ciclo aquí y no lo habrá, cada una de las instrucciones en sí da un salto al siguiente controlador:
op_pushi: { uint16_t arg = NEXT_ARG(); PUSH(arg); goto *labels[NEXT_OP()]; }
La ausencia de un interruptor "extiende" puntos de ramificación a lo largo de los cuerpos de instrucciones, lo que en teoría debería ayudar al predictor de ramificaciones en caso de ejecución extraordinaria de instrucciones. Es como si construyéramos el conmutador directamente en las instrucciones y formamos manualmente una tabla de transición.
Esa es toda la técnica. Le gustaba el lechón por su simplicidad. Veamos qué pasa en la práctica:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 443ms PROFILE: switch code (no range check) finished took 389ms PROFILE: threaded code finished took 477ms PROFILE: trace code finished took 364ms
¡Uy! ¡Esta es la más lenta de todas nuestras técnicas! Que paso Ejecutemos las mismas pruebas, desactivando todas las optimizaciones de GCC:
> ./pigletvm runtimes test/sieve.bin 100 > /dev/null PROFILE: switch code finished took 969ms PROFILE: switch code (no range check) finished took 940ms PROFILE: threaded code finished took 824ms PROFILE: trace code finished took 1169ms
Aquí, el código cosido funciona mejor.
Tres factores juegan un papel aquí:
- El compilador de optimización mismo creará una tabla de conversión no peor que nuestra placa de etiquetas manual.
- Los compiladores modernos eliminan notablemente las llamadas a funciones adicionales.
- Comenzando alrededor de la generación Haswell de procesadores Intel, los predictores de ramificación han aprendido a predecir con precisión las transiciones a través de un único punto de ramificación.
Según la memoria anterior, esta técnica todavía se usa en el código de, por ejemplo, el intérprete de Python VM, pero, francamente, en estos días ya es arcaísmo.
Permítanos resumir y evaluar finalmente los éxitos logrados por nuestro cerdo.
Debriefing
No estoy seguro de cómo se puede llamar un vuelo, pero seamos sinceros, nuestro cerdito ha recorrido un largo camino desde 550 milisegundos durante cien carreras en el "tamiz" hasta los 370 milisegundos finales. Utilizamos diferentes técnicas: superinstrucciones, eliminación de intervalos de comprobación de valores, mecánica complicada de trazas y, finalmente, incluso código cosido. Al mismo tiempo, nosotros, en general, actuamos dentro del marco de las cosas implementadas en todos los compiladores populares de C. La aceleración en un factor de 1.5, como me parece, es un buen resultado, y el lechón merece una porción adicional de salvado en el comedero.
Una de las condiciones implícitas que establecemos para nosotros con el pig es preservar la arquitectura de la pila de la máquina Piglet VM. La transición a la arquitectura de registro, como regla, reduce el número de instrucciones necesarias para la lógica de los programas y, en consecuencia, puede ayudar a eliminar las salidas innecesarias al administrador de instrucciones. Creo que otro 10-20% del tiempo en esto podría cortarse.
Nuestra condición principal, la falta de compilación dinámica, tampoco es una ley de la naturaleza. Bombear a un cerdo con esteroides en forma de una compilación JIT es muy fácil en estos días: en bibliotecas como GNU Lightning o LibJIT, todo el trabajo sucio ya se ha hecho. Pero el tiempo de desarrollo y la cantidad total de código, incluso utilizando bibliotecas, están creciendo enormemente.
Hay, por supuesto, otros trucos a los que nuestro cerdito no ha llegado al casco. , — - — - . , .
PS , , , , ( https://www.instagram.com/vovazomb/ ), .
PPS , . true-grue - — PigletC . !
PPPS iliazeus : . ; . .