performance - Diseño de VM: ¿Más códigos de operación o menos códigos de operación? ¿Qué es mejor?

interpreter opcode (3)

No se sorprenda Este es un montón de texto, pero me temo que sin dar información detallada no puedo mostrar de qué se trata todo esto (y podría obtener muchas respuestas que no responden a mi pregunta). Y esto definitivamente no es una tarea (como alguien ridículamente afirmó en su comentario).

Prerrequisitos

Como es probable que esta pregunta no se pueda responder en absoluto a menos que se establezcan al menos algunos requisitos previos, estos son los requisitos previos:

Se interpretará el código de la Máquina Virtual. No está prohibido que haya un compilador JIT, pero el diseño debe apuntar a un intérprete.
La máquina virtual debe estar basada en el registro, no en la pila.
La respuesta no puede asumir que hay un conjunto fijo de registros ni que hay un número ilimitado de ellos, cualquiera de los dos puede ser el caso.

Además necesitamos una mejor definición de "mejor". Hay un par de propiedades que deben ser consideradas:

El espacio de almacenamiento para el código VM en el disco. Por supuesto, siempre podría eliminar todas las optimizaciones aquí y simplemente comprimir el código, pero esto tiene un efecto negativo en (2).
Velocidad de decodificación. La mejor manera de almacenar el código es inútil si toma demasiado tiempo transformarlo en algo que pueda ejecutarse directamente.
El espacio de almacenamiento en memoria. Este código debe ser ejecutable directamente con o sin decodificación adicional, pero si se trata de una decodificación adicional, esta codificación se realiza durante la ejecución y cada vez que se ejecuta la instrucción (la decodificación se realiza solo una vez al cargar los recuentos de códigos en el elemento 2).
La velocidad de ejecución del código (teniendo en cuenta las técnicas comunes de interpretación).
La complejidad de la máquina virtual y lo difícil que es escribir un intérprete para ella.
La cantidad de recursos que la VM necesita para sí misma. (No es un buen diseño si el código que ejecuta la VM tiene un tamaño de 2 KB y se ejecuta más rápido que un abrir y cerrar de ojos, sin embargo, se necesitan 150 MB para hacer esto y su tiempo de inicio es muy superior al tiempo de ejecución del código se ejecuta)

Ahora ejemplos de lo que realmente quiero decir con más o menos códigos de operación. Puede parecer que la cantidad de códigos de operación está establecida, ya que necesita un código de operación por operación. Sin embargo, no es tan fácil.

Opcodes múltiples para la misma operación

Puedes tener una operación como

ADD R1, R2, R3

sumando los valores de R1 y R2, escribiendo el resultado a R3. Ahora considere los siguientes casos especiales:

ADD R1, R2, R2 ADD R1, 1, R1

Estas son operaciones comunes que encontrarás en muchas aplicaciones. Puede expresarlos con el código de operación ya existente (a menos que necesite uno diferente porque el último tiene un valor int en lugar de un registro). Sin embargo, también puede crear códigos de operación especiales para estos:

ADD2 R1, R2 INC R1

Igual que antes. ¿Dónde está la ventaja? ADD2 solo necesita dos argumentos, en lugar de 3, INC incluso solo necesita uno. Así que esto podría ser codificado más compacto en disco y / o en memoria. Dado que también es fácil transformar cualquiera de las dos formas, la etapa de decodificación podría transformarse entre ambas formas de expresar estas declaraciones. Sin embargo, no estoy seguro de cuánto influirá cualquiera de las formas en la velocidad de ejecución.

Combinando dos códigos de operación en uno solo

Ahora supongamos que tiene un ADD_RRR (R para el registro) y un LOAD para cargar datos en un registro.

LOAD value, R2 ADD_RRR R1, R2, R3

Puede tener estos dos códigos de operación y siempre usar construcciones como esta en todo su código ... o puede combinarlas en un nuevo código de operación nuevo, llamado ADD_RMR (M para memoria)

ADD_RMR R1, value, R3

Tipos de datos vs Opcodes

Suponga que tiene un entero de 16 bits y un entero de 32 bits como tipos nativos. Los registros son de 32 bits, por lo que se ajusta el tipo de datos. Ahora, cuando agrega dos registros, puede hacer que el tipo de datos sea un parámetro:

ADD int16, R1, R2, R3 ADD int32, R1, R2, R3

Lo mismo es cierto para un entero con signo y sin signo, por ejemplo. De esa manera, ADD puede ser un código de operación corto, un byte, y luego tiene otro byte (o quizás solo 4 Bit) que le dice a la VM cómo interpretar los registros (si tienen valores de 16 Bit o 32 Bit). O puede desechar la codificación de tipo y, en su lugar, tener dos códigos de operación:

ADD16 R1, R2, R3 ADD32 R1, R2, R3

Algunos pueden decir que ambos son exactamente iguales, simplemente interpretar de la primera manera que funcionaría el código de operación de 16 bits. Sí, pero un intérprete muy ingenuo puede parecer bastante diferente. Por ejemplo, si tiene una función por código de operación y se envía usando una instrucción de cambio (no es la mejor manera de hacerlo, la sobrecarga de llamadas de funciones, la instrucción de cambio tampoco es óptima, lo sé), los dos códigos de operación podrían tener este aspecto:

case ADD16: add16(p1, p2, p3); break; // pX pointer to register case ADD32: add32(p1, p2, p3); break;

y cada función se centra en un cierto tipo de complemento. El segundo, aunque puede verse así:

case ADD: add(type, p1, p2, p3); break; // ... // and the function void add (enum Type type, Register p1, Register p2, Register p3) { switch (type) { case INT16: //... case INT32: // ... } }

Agregar un conmutador secundario a un interruptor principal o una tabla de despacho secundaria a una tabla de despacho principal. Por supuesto, un intérprete puede hacerlo de cualquier manera sin importar si los tipos son explícitos o no, pero de cualquier manera se sentirá más nativo para los desarrolladores dependiendo del diseño del código de operación.

Meta Opcodes

A falta de un nombre mejor los llamaré así. Estos opcodes no tienen ningún significado en absoluto por sí mismos, solo cambian el significado del opcode siguiente. Como el famoso operador WIDE:

ADD R1, R2, R3 WIDE ADD R1, R2, R3

Por ejemplo, en el segundo caso, los registros son de 16 bits (por lo que puede agregar más de ellos), en el primero solo 8. Alternativamente, no puede tener un código de operación de metadatos de este tipo y tener un código de operación ADD y ADD_WIDE. Los metodos de acción como WIDE evitan tener un SUB_WIDE, MUL_WIDE, etc., ya que siempre puede anteponer todos los demás códigos de operación normales con WIDE (siempre solo un código de operación). La desventaja es que un código de operación por sí solo deja de tener sentido, siempre debe verificar el código de operación antes de que se trate de un código de operación de metadatos o no. Además, la VM debe almacenar un estado adicional por hilo (por ejemplo, si estamos ahora en modo ancho o no) y eliminar el estado nuevamente después de la siguiente instrucción. Incluso las CPU tienen tales códigos de operación (por ejemplo, código de operación LOCK x86).

¿Cómo encontrar una buena compensación?

Por supuesto, cuantos más códigos de operación tenga, más grandes se convertirán los conmutadores / tablas de despacho y más bits necesitará para expresar estos códigos en el disco o en la memoria (aunque puede almacenarlos de manera más eficiente en el disco donde no hay datos). tiene que ser directamente ejecutable por una máquina virtual); también la máquina virtual se volverá más complicada y tendrá más líneas de código; por otra parte, cuanto más poderosos sean los códigos de operación: se está acercando al punto en que cada expresión, incluso una compleja, terminará en un código de operación.

Elegir pequeños códigos de operación facilita la codificación de la VM y dará lugar a códigos de operación muy compactos, supongo. Por otra parte, significa que es posible que necesite un número muy alto de códigos de operación para realizar una tarea simple y que cada expresión que no se use muy a menudo tendrá que convertirse en una llamada de función (nativa) de algún tipo, ya que no se puede utilizar ningún código de operación para ello.

Leí mucho sobre todo tipo de máquinas virtuales en Internet, pero ninguna fuente estaba haciendo una buena y justa compensación de ninguna manera. Diseñar una máquina virtual es como diseñar una CPU, hay CPU con pequeños códigos de operación, son rápidos, pero también necesitas muchos de estos. Y hay CPU con muchos códigos de operación, algunos son muy lentos, pero necesitarás mucho menos para expresar el mismo código. Parece que los "más opcodes son mejores" Las CPU han ganado totalmente el mercado de consumo y los "menos opcodes son mejores" los que solo pueden sobrevivir en algunas partes del mercado de servidores o en el negocio de supercomputadoras. ¿Qué pasa con las máquinas virtuales?

Para el rendimiento del software, es más fácil si todos los códigos de operación tienen la misma longitud, por lo que puede tener una instrucción de cambio gigantesca y no tener que examinar varios bits de opciones que podrían haber sido establecidos por códigos de operación de modificadores anteriores.

Dos cuestiones que creo que no cuestionó son la facilidad de escritura de los compiladores que traducen los lenguajes de programación a su código de máquina virtual y la facilidad de escritura de los intérpretes que ejecutan su código de máquina virtual. Ambos son más fáciles con menos códigos de operación. (Pero no muy pocos. Por ejemplo, si omite un código de operación de división, tendrá la oportunidad de aprender cómo codificar buenas funciones de división. Las buenas son mucho más difíciles que las simples).

Para ser honesto, creo que es en gran medida una cuestión del propósito de la VM, similar a cómo el diseño del procesador está determinado en gran medida por la forma en que el procesador está destinado a ser utilizado principalmente.

En otras palabras, preferiblemente podrá determinar escenarios de casos de uso comunes para su máquina virtual, de modo que pueda establecer las características que probablemente serán necesarias, y también establecer aquellas que es poco probable que se requieran con mucha frecuencia.

Por supuesto, entiendo que probablemente esté imaginando una Máquina Virtual abstracta y muy genérica, que puede usarse como la implementación interna / backend para otros lenguajes de programación.

Sin embargo, creo que es importante darse cuenta y enfatizar que realmente no existe tal cosa como una implementación "ideal ideal" de cualquier cosa, es decir, una vez que mantenga las cosas genéricas y abstractas, inevitablemente enfrentará una situación en la que debe hacer concesiones.

Idealmente, estos compromisos se basarán en los escenarios de uso de la vida real de su código, de modo que estos compromisos se basen realmente en suposiciones y simplificaciones bien informadas que puede realizar sin tener que arriesgarse.

En otras palabras, me gustaría pensar en cuáles son los objetivos para su máquina virtual. ¿Cómo se utilizará principalmente en su visión? ¿Cuáles son los objetivos que quieres lograr?

Esto lo ayudará a establecer los requisitos y lo ayudará a realizar simplificaciones, de modo que pueda diseñar su conjunto de instrucciones basándose en suposiciones razonables.

Si espera que su máquina virtual sea utilizada principalmente por lenguajes de programación para el procesamiento de números, probablemente querrá buscar una base bastante poderosa con operaciones matemáticas, al proporcionar gran cantidad de primitivas de bajo nivel, con soporte para tipos de datos amplios.

Si, por otro lado, usted servirá como servidor para los idiomas de OO, querrá considerar la optimización de las instrucciones de bajo nivel correspondientes (es decir, hashes / diccionarios).

En general, recomendaría mantener el conjunto de instrucciones tan simple e intuitivo como sea posible al principio, y solo agregar instrucciones especiales una vez que haya probado que tenerlas en su lugar es realmente útil (es decir, volcados de perfil y código de operación) y causa un rendimiento ganancia. Por lo tanto, esto será determinado en gran medida por los primeros "clientes" que tendrá su máquina virtual.

Si está realmente ansioso por investigar enfoques más complejos, incluso podría considerar la optimización dinámica del conjunto de instrucciones en el tiempo de ejecución, utilizando la coincidencia de patrones para encontrar ocurrencias comunes de códigos de operación en su código de bytes, a fin de derivar implementaciones más abstractas, para que pueda transformarse. su bytecode dinámicamente con opcodes personalizados, generados en tiempo de ejecución.

Prefiero conjuntos de instrucciones minimalistas porque se pueden combinar en un código de operación. Por ejemplo, un código de operación que consta de dos campos de instrucción de 4 bits se puede enviar con una tabla de salto de 256 entradas. Como la sobrecarga de despacho es el principal cuello de botella en la interpretación, el rendimiento se incrementó en un factor ~ dos porque solo es necesario enviar cada segunda instrucción. Una forma de implementar un conjunto de instrucciones minimalistas pero efectivas sería un diseño de acumulador / tienda.