Código multihilo

Las direcciones en el hilo son direcciones de lenguaje máquina. Esta forma es sencilla, pero puede generar sobrecarga, ya que el hilo consta únicamente de direcciones de máquina, por lo que todos los parámetros adicionales deben cargarse indirectamente desde la memoria. Algunos sistemas Forth generan código de encadenamiento directo. En muchas máquinas, el encadenamiento directo es más rápido que el encadenamiento mediante subrutinas (véase la referencia a continuación).

Un ejemplo de una máquina de pila podría ejecutar la secuencia "push A, push B, add". Eso podría traducirse al siguiente hilo y rutinas, donde ipse inicializa a la dirección etiquetada thread(es decir, la dirección donde &pushAse almacena).

#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread // ip apunta a &pushA (que apunta a la primera instrucción de pushA) jump * ip ++ // envía el control a la primera instrucción de pushA y avanza ip a &pushB thread : & pushA & pushB & add ... pushA : PUSH ( A ) jump * ip ++ // envía el control adonde dice ip (es decir, a pushB) y avanza ip pushB : PUSH ( B ) jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++

Alternativamente, se pueden incluir operandos en el hilo. Esto puede eliminar parte de la indirección necesaria anteriormente, pero aumenta el tamaño del hilo:

#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread jump * ip ++ thread : & push & A // dirección donde se almacena A, no la A literal & push & B & add ... push : variable_address = * ip ++ // debe mover ip más allá de la dirección del operando, ya que no es una dirección de subrutina PUSH ( * variable_address ) // Lee el valor de la variable y lo inserta en la pila jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++

El encadenamiento indirecto utiliza punteros a ubicaciones que, a su vez, apuntan al código máquina. Al puntero indirecto pueden seguirle operandos que se almacenan en el "bloque" indirecto en lugar de almacenarlos repetidamente en el hilo. Por lo tanto, el código indirecto suele ser más compacto que el código de encadenamiento directo. La indirección generalmente lo hace más lento, aunque suele ser más rápido que los intérpretes de bytecode. Cuando los operandos del manejador incluyen tanto valores como tipos, el ahorro de espacio con respecto al código de encadenamiento directo puede ser significativo. Los sistemas FORTH más antiguos suelen generar código de encadenamiento indirecto.

Por ejemplo, si el objetivo es ejecutar "push A, push B, add", se podría usar lo siguiente. Aquí, ipse inicializa a la dirección &thread, cada fragmento de código ( push, add) se encuentra mediante doble indirección a través de ipy un bloque indirecto; y cualquier operando del fragmento se encuentra en el bloque indirecto que sigue a la dirección del fragmento. Esto requiere mantener la subrutina actualip en , a diferencia de todos los ejemplos anteriores donde contenía la siguiente subrutina que se iba a llamar.

inicio : ip = & hilo // apunta a '&i_pushA' salto ** ip // sigue los punteros a la primera instrucción de 'push', NO avanza ip todavía hilo : & i_pushA & i_pushB & i_add ... i_pushA : & push & A i_pushB : & push & B i_add : & add push : * sp ++ = ** ( * ip + 1 ) // mira 1 más allá del inicio del bloque indirecto para la dirección del operando salto * ( *++ ip ) // avanza ip en el hilo, salta a través del siguiente bloque indirecto a la siguiente subrutina agregar : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 salto * ( *++ ip )

El llamado "código enhebrado de subrutinas" (también llamado "código enhebrado de llamadas") consiste en una serie de instrucciones de "llamada" en lenguaje máquina (o direcciones de funciones a "llamar", a diferencia del uso de "jump" en la programación enhebrada directa). Los primeros compiladores para ALGOL , Fortran, Cobol y algunos sistemas Forth a menudo generaban código enhebrado de subrutinas. El código en muchos de estos sistemas operaba sobre una pila de operandos de último en entrar, primero en salir (LIFO), para la cual la teoría de compiladores estaba bien desarrollada. La mayoría de los procesadores modernos cuentan con soporte de hardware especial para las instrucciones de "llamada" y "retorno" de subrutinas, por lo que la sobrecarga de una instrucción de máquina adicional por despacho se reduce considerablemente.

Anton Ertl, cocreador del compilador Gforth , afirmó que, «contrariamente a los mitos populares, el enhebrado de subrutinas suele ser más lento que el enhebrado directo». ^{[ 10 ]} Sin embargo, las pruebas más recientes de Ertl ^{[ 1 ]} muestran que el enhebrado de subrutinas es más rápido que el enhebrado directo en 15 de 25 casos de prueba. Más concretamente, descubrió que el enhebrado directo es el modelo de enhebrado más rápido en los procesadores Xeon, Opteron y Athlon, el enhebrado indirecto es el más rápido en los procesadores Pentium M, y el enhebrado de subrutinas es el más rápido en los procesadores Pentium 4, Pentium III y PPC.

Como ejemplo de encadenamiento de llamadas para "push A, push B, add":

hilo : llamar a pushA llamar a pushB llamar a add ret pushA : * sp ++ = A ret pushB : * sp ++ = B ret add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 ret

El código con enhebrado por token implementa el hilo como una lista de índices en una tabla de operaciones; el ancho del índice se elige naturalmente para que sea lo más pequeño posible para mayor densidad y eficiencia. 1 byte / 8 bits es la opción natural para facilitar la programación, pero se pueden usar tamaños más pequeños como 4 bits, o más grandes como 12 o 16 bits, dependiendo del número de operaciones admitidas. Siempre que el ancho del índice sea más estrecho que un puntero de máquina, será naturalmente más compacto que otros tipos de enhebrado sin mucho esfuerzo especial por parte del programador. Generalmente es de la mitad a tres cuartos del tamaño de otros enhebrados, que a su vez son de un cuarto a un octavo del tamaño del código sin enhebrado. Los punteros de la tabla pueden ser indirectos o directos. Algunos compiladores de Forth producen código con enhebrado por token. Algunos programadores consideran que el " código p " generado por algunos compiladores de Pascal , así como los códigos de bytes utilizados por .NET , Java , BASIC y algunos compiladores de C , son de tipo token-threading.

Históricamente, un enfoque común es el bytecode , que normalmente utiliza códigos de operación de 8 bits con una máquina virtual basada en pila. El intérprete de bytecode arquetípico se conoce como "intérprete de decodificación y despacho" y sigue la siguiente forma:

inicio : vpc = & hilo despacho : addr = decodificar ( & vpc ) // Convierte la siguiente operación de bytecode en un puntero al código máquina que la implementa // Cualquier operación entre instrucciones se realiza aquí (por ejemplo, actualización del estado global, procesamiento de eventos, etc.) salto addr CODE_PTR decodificar ( BYTE_CODE ** p ) { // En una codificación más compleja, puede haber varias tablas para elegir o indicadores de control/modo devolver tabla [ * ( * p ) ++ ]; } hilo : /* Contiene bytecode, no direcciones de máquina. Por lo tanto, es más compacto. */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/ table : & add /* table[0] = dirección del código máquina que implementa el bytecode 0 */ & pushA /* table[1] ... */ & pushB /* table[2] ... */ pushA : * sp ++ = A salto de despacho pushB : * sp ++ = B salto de despacho add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 salto de despacho

Si la máquina virtual utiliza únicamente instrucciones de un byte, decode()se trata simplemente de una búsqueda desde thread, pero a menudo existen instrucciones de 1 byte de uso común, además de algunas instrucciones multibyte menos comunes (véase el conjunto de instrucciones complejo del ordenador ), en cuyo caso decode()es más complejo. La decodificación de los códigos de operación de un solo byte puede gestionarse de forma muy sencilla y eficiente mediante una tabla de bifurcación que utiliza el código de operación directamente como índice.

Para instrucciones con operaciones individuales sencillas, como "empujar" y "sumar", la sobrecarga que implica decidir qué ejecutar es mayor que el coste de ejecutarlo realmente, por lo que estos intérpretes suelen ser mucho más lentos que el código máquina. Sin embargo, para instrucciones más complejas ("compuestas"), el porcentaje de sobrecarga es proporcionalmente menos significativo.

En ocasiones, el código con subprocesos de token puede ejecutarse más rápido que el código máquina equivalente cuando este último resulta demasiado grande para caber en la caché de instrucciones L1 de la CPU. La mayor densidad de código del código con subprocesos, especialmente el de tokens, permite que quepa completamente en la caché L1, evitando así la saturación de la caché. Sin embargo, a diferencia del código máquina, que solo consume la caché de instrucciones, el código con subprocesos consume tanto la caché de instrucciones (para la implementación de cada operación) como la caché de datos (para el bytecode y las tablas); esto significa que el código con subprocesos reduce la cantidad de datos que la CPU puede procesar en un momento dado. En cualquier caso, si el problema que se está calculando implica aplicar un gran número de operaciones a una pequeña cantidad de datos, el uso de código con subprocesos puede ser una optimización ideal. ^{[ 4 ]}

El código enhebrado de Huffman consiste en listas de tokens almacenados como códigos de Huffman . Un código de Huffman es una cadena de bits de longitud variable que identifica un token único. Un intérprete enhebrado de Huffman localiza subrutinas mediante una tabla de índices o un árbol de punteros que puede ser navegado por el código de Huffman. El código enhebrado de Huffman es una de las representaciones más compactas conocidas para un programa informático. El índice y los códigos se eligen midiendo la frecuencia de las llamadas a cada subrutina en el código. A las llamadas frecuentes se les asignan los códigos más cortos. A las operaciones con frecuencias aproximadamente iguales se les asignan códigos con longitudes de bits casi iguales. La mayoría de los sistemas enhebrados de Huffman se han implementado como sistemas Forth de enhebrado directo y se han utilizado para empaquetar grandes cantidades de código de ejecución lenta en microcontroladores pequeños y económicos . La mayoría de los usos publicados ^{[ 11 ]} se han dado en tarjetas inteligentes, juguetes, calculadoras y relojes. El código tokenizado orientado a bits utilizado en PBASIC puede considerarse un tipo de código enhebrado de Huffman.

Un ejemplo es el encadenamiento de cadenas, en el que las operaciones se identifican mediante cadenas, que normalmente se consultan en una tabla hash. Esto se utilizó en las primeras implementaciones de Forth de Charles H. Moore y en el lenguaje de programación experimental interpretado por hardware de la Universidad de Illinois . También se utiliza en Bashforth .

El RPL de HP , introducido por primera vez en la calculadora HP-18C en 1986, es un tipo de lenguaje interpretativo multihilo (TIL) híbrido (de subprocesos directos e indirectos) propietario ^{[ 12 ]} que, a diferencia de otros TIL, permite la incrustación de "objetos" RPL ^{[ b ]} en el "flujo de ejecución", es decir, el flujo de direcciones a través del cual avanza el puntero del intérprete. Un "objeto" RPL puede considerarse como un tipo de datos especial cuya estructura en memoria contiene una dirección a un "prólogo del objeto" al comienzo del objeto, y luego le siguen datos o código ejecutable. El prólogo del objeto determina cómo debe ejecutarse o procesarse el cuerpo del objeto. Usando el "bucle interno RPL" ^{[ 13 ]} , que fue inventado y patentado ^{[ 14 ]} por William C. Wickes en 1986 y publicado en 1988, la ejecución sigue así: ^{[ 15 ]}

1. Desreferenciar el IP (puntero de instrucción) y almacenarlo en O (puntero de objeto actual).
2. Incrementa la IP en la longitud de un puntero de dirección.
3. Desreferencia O y almacena su dirección en O_1 (este es el segundo nivel de indirección).
4. Transfiera el control al siguiente puntero u objeto incrustado configurando el PC (contador de programa) a O_1 más un puntero de dirección.
5. Vuelve al paso 1

Esto se puede representar con mayor precisión mediante:

 O = [I] I = I + Δ PC = [O] + Δ 

Donde arriba, O es el puntero del objeto actual, I es el puntero del intérprete, Δ es la longitud de una palabra de dirección y el operador "[]" significa "desreferenciación".

Cuando el control se transfiere a un puntero de objeto o a un objeto incrustado, la ejecución continúa de la siguiente manera:

PRÓLOGO -> PRÓLOGO (La dirección del prólogo al inicio del código del prólogo apunta a sí misma) SI O + Δ =/= PC LUEGO IR A INDIRECTO (Prueba de ejecución directa) O = I - Δ (Corrección de O para que apunte al inicio del objeto incrustado) I = I + α (Corrección de I para que apunte después del objeto incrustado, donde α es la longitud del objeto) INDIRECTO (Resto del prólogo) 

En los microprocesadores Saturn de HP que utilizan RPL, existe un tercer nivel de indirección posible gracias a un truco arquitectónico/de programación que permite una ejecución más rápida. ^{[ 13 ]}