Código enhebrado

En informática, el código de subprocesos es una técnica de programación en la que el código tiene una forma que consiste esencialmente en llamadas a subrutinas. A menudo se usa en compiladores, que pueden generar código en esa forma o implementarse en esa forma ellos mismos. El código puede ser procesado por un intérprete o puede ser simplemente una secuencia de instrucciones de llamada de código de máquina.

El código subproceso tiene mejor densidad que el código generado por técnicas de generación alternativas y por convenciones de llamadas alternativas. En arquitecturas en caché, puede ejecutarse un poco más lento. Sin embargo, un programa que es lo suficientemente pequeño como para caber en el caché del procesador de una computadora puede ejecutarse más rápido que un programa más grande que sufre muchas fallas en el caché. Los programas pequeños también pueden ser más rápidos en el cambio de subprocesos, cuando otros programas han llenado el caché.

El código subproceso es mejor conocido por su uso en muchos compiladores de lenguajes de programación, como Forth, muchas implementaciones de BASIC, algunas implementaciones de COBOL, versiones anteriores de B y otros lenguajes para minicomputadoras pequeñas y satélites de radioaficionados.

Historia

La forma común de hacer programas de computadora es usar un compilador para traducir el código fuente (escrito en algún lenguaje simbólico) a código de máquina. El ejecutable resultante suele ser rápido pero, debido a que es específico de una plataforma de hardware, no es portátil. Un enfoque diferente es generar instrucciones para una máquina virtual y usar un intérprete en cada plataforma de hardware. El intérprete instancia el entorno de la máquina virtual y ejecuta las instrucciones. Por lo tanto, solo se debe compilar el intérprete.

Las primeras computadoras tenían relativamente poca memoria. Por ejemplo, la mayoría de Data General Nova, IBM 1130 y muchas de las primeras microcomputadoras tenían solo 4 kB de RAM instalados. En consecuencia, se dedicó mucho tiempo a tratar de encontrar formas de reducir el tamaño de un programa para que cupiera en la memoria disponible.

Una solución es utilizar un intérprete que lea el lenguaje simbólico poco a poco y llame a funciones para realizar las acciones. Como el código fuente suele ser mucho más denso que el código de máquina resultante, esto puede reducir el uso general de la memoria. Esta fue la razón por la que Microsoft BASIC es un intérprete: su propio código tenía que compartir la memoria de 4 kB de máquinas como la Altair 8800 con el código fuente del usuario. Un compilador traduce de un lenguaje fuente a código de máquina, por lo que el compilador, la fuente y la salida deben estar todos en la memoria al mismo tiempo. En un intérprete, no hay salida.

El código subproceso es un estilo de formato para el código compilado que minimiza el uso de la memoria. En lugar de escribir cada paso de una operación en cada aparición en el programa, como era común en los ensambladores de macros, por ejemplo, el compilador escribe cada bit común de código en una subrutina. Por lo tanto, cada bit existe en un solo lugar en la memoria (consulte "No se repita"). La aplicación de nivel superior en estos programas puede consistir en nada más que llamadas a subrutinas. Muchas de estas subrutinas, a su vez, también consisten en nada más que llamadas a subrutinas de nivel inferior.

Los mainframes y algunos de los primeros microprocesadores, como el RCA 1802, requerían varias instrucciones para llamar a una subrutina. En la aplicación de nivel superior y en muchas subrutinas, esa secuencia se repite constantemente, y solo la dirección de la subrutina cambia de una llamada a la siguiente. Esto significa que un programa que consta de muchas llamadas a funciones también puede tener cantidades considerables de código repetido.

Para abordar esto, los sistemas de código enhebrado usaban pseudocódigo para representar las llamadas a funciones en un solo operador. En tiempo de ejecución, un pequeño "intérprete" escanearía el código de nivel superior, extraería la dirección de la subrutina en la memoria y la llamaría. En otros sistemas, este mismo concepto básico se implementa como una tabla de sucursales, una tabla de despacho o una tabla de métodos virtuales, todas las cuales consisten en una tabla de direcciones de subrutinas.

Durante la década de 1970, los diseñadores de hardware hicieron un esfuerzo considerable para hacer que las llamadas a subrutinas fueran más rápidas y sencillas. En los diseños mejorados, solo se gasta una sola instrucción para llamar a una subrutina, por lo que el uso de una pseudoinstrucción no ahorra espacio. Además, el desempeño de estas llamadas está casi libre de sobrecarga adicional. Hoy en día, aunque casi todos los lenguajes de programación se enfocan en aislar el código en subrutinas, lo hacen por claridad y mantenibilidad del código, no para ahorrar espacio.

Los sistemas de código de subprocesos ahorran espacio al reemplazar esa lista de llamadas a funciones, donde solo la dirección de la subrutina cambia de una llamada a la siguiente, con una lista de tokens de ejecución, que son esencialmente llamadas a funciones con los códigos de operación de llamada eliminados., dejando solo una lista de direcciones.

A lo largo de los años, los programadores han creado muchas variaciones de ese "intérprete" o "selector pequeño". La dirección particular en la lista de direcciones puede extraerse utilizando un índice, un registro de propósito general o un puntero. Las direcciones pueden ser directas o indirectas, contiguas o no contiguas (enlazadas por punteros), relativas o absolutas, resueltas en tiempo de compilación o construidas dinámicamente. Ninguna variación individual es "mejor" para todas las situaciones.

Desarrollo

Para ahorrar espacio, los programadores comprimieron las listas de llamadas de subrutinas en listas simples de direcciones de subrutinas y usaron un pequeño bucle para llamar a cada subrutina por turno. Por ejemplo, el siguiente pseudocódigo usa esta técnica para agregar dos números A y B. En el ejemplo, la lista está etiquetada como thread y una variable ip (Instruction Pointer) rastrea nuestro lugar dentro de la lista. Otra variable sp (Stack Pointer) contiene una dirección en otra parte de la memoria que está disponible para contener un valor temporalmente.

Empieza: ip = "hilo // apunta a la dirección ' PulpohA', no la etiqueta textual 'thread 'arriba: salto *ip++ // seguir ip para abordar en el hilo, siga esa dirección a la subrutina, avance iphilo: "pushA "pushB "añadir ...pushA: *sp++ = A // seguir sp a la memoria disponible, almacenar A allí, avance sp al siguiente  salto arribapushB: *sp++ = B salto arribaañadir: adición1 = *...sp // Apaga el valor superior de la pila addend2 = *...sp // Pop segundo valor de la pila *sp++ = adición1 + addend2 // Agregar los dos valores juntos y almacenar el resultado en la parte superior de la pila salto arriba

El ciclo de llamada en top es tan simple que puede repetirse en línea al final de cada subrutina. El control ahora salta una vez, desde el final de una subrutina hasta el comienzo de otra, en lugar de saltar dos veces a través de top. Por ejemplo:

Empieza: ip = "hilo // ip señala a " PulhA (que apunta a la primera instrucción de pushA) salto *ip++ // enviar control a primera instrucción de empuje A and advance ip to &pushBhilo: "pushA "pushB "añadir ...pushA: *sp++ = A // seguir sp a la memoria disponible, almacenar A allí, avance sp al siguiente  salto *ip++ // enviar control donde ip dice a (es decir, a pushB) y avanzar ippushB: *sp++ = B salto *ip++añadir: adición1 = *...sp // Apaga el valor superior de la pila addend2 = *...sp // Pop segundo valor de la pila *sp++ = adición1 + addend2 // Agregar los dos valores juntos y almacenar el resultado en la parte superior de la pila salto *ip++

Esto se llama código de subprocesos directos (DTC). Aunque la técnica es más antigua, el primer uso ampliamente difundido del término "código de subprocesos" es probablemente el artículo de 1973 de James R. Bell "Código roscado".

En 1970, Charles H. Moore inventó un arreglo más compacto, código de subprocesos indirectos (ITC), para su máquina virtual Forth. Moore llegó a este arreglo porque las minicomputadoras Nova tenían un bit de direccionamiento indirecto en cada dirección, lo que hizo que ITC fuera fácil y rápido. Más tarde, dijo que lo encontró tan conveniente que lo propagó en todos los diseños posteriores de Forth.

Actualmente, algunos compiladores de Forth generan código de subprocesos directos, mientras que otros generan código de subprocesos indirectos. Los ejecutables actúan de la misma manera de cualquier manera.

Modelos de roscado

Prácticamente todo el código ejecutable con subprocesos utiliza uno u otro de estos métodos para invocar subrutinas (cada método se denomina "modelo de subprocesos").

Enhebrado directo

Las direcciones en el hilo son las direcciones del lenguaje de máquina. Este formulario es simple, pero puede tener gastos generales porque el subproceso consta solo de direcciones de máquina, por lo que todos los demás parámetros deben cargarse indirectamente desde la memoria. Algunos sistemas Forth producen código de subprocesamiento directo. En muchas máquinas, el subprocesamiento directo es más rápido que el subprocesamiento de subrutinas (consulte la referencia a continuación).

Un ejemplo de una máquina apiladora podría ejecutar la secuencia "presionar A, presionar B, agregar". Eso podría traducirse al siguiente subproceso y rutinas, donde ip se inicializa en la dirección etiquetada thread (es decir, la dirección donde &pushA está almacenado).

#define PUSH(x) (*sp+ = (x))#define POP() (*--sp)Empieza: ip = "hilo // ip señala a " PulhA (que apunta a la primera instrucción de pushA) salto *ip++ // enviar control a primera instrucción de empuje A and advance ip to &pushBhilo: "pushA "pushB "añadir ...pushA: PUSH()A) salto *ip++ // enviar control donde ip dice a (es decir, a pushB) y avanzar ippushB: PUSH()B) salto *ip++añadir: resultado = POP() + POP() PUSH()resultado) salto *ip++

Alternativamente, se pueden incluir operandos en el hilo. Esto puede eliminar algunas indirectas necesarias anteriormente, pero hace que el hilo sea más grande:

#define PUSH(x) (*sp+ = (x))#define POP() (*--sp)Empieza: ip = "hilo salto *ip++hilo: "empujar "A // dirección donde se almacena A, no literal A "empujar "B "añadir ...empujar: variable_address = *ip++ // debe mover ip dirección pasada, ya que no es una dirección de la subrutina PUSH()*variable_address) // Valor de lectura de variable y empuje en la pila salto *ip++añadir: resultado = POP() + POP() PUSH()resultado) salto *ip++

Enhebrado indirecto

El subprocesamiento indirecto utiliza punteros a ubicaciones que, a su vez, apuntan al código de máquina. El puntero indirecto puede ir seguido de 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 directo. La indirección generalmente lo hace más lento, aunque generalmente aún más rápido que los intérpretes de código de bytes. Cuando los operandos del controlador incluyen tanto valores como tipos, el ahorro de espacio en comparación con el código de subprocesamiento directo puede ser significativo. Los sistemas FORTH más antiguos suelen producir código de subprocesos indirectos.

Por ejemplo, si el objetivo es ejecutar "presionar A, presionar B, agregar", se podría usar lo siguiente. Aquí, ip se inicializa para dirigirse a &thread, cada fragmento de código (push, add) se encuentra mediante doble-indirecting a través de ip y un bloqueo indirecto; y todos los operandos del fragmento se encuentran en el bloque indirecto que sigue a la dirección del fragmento. Esto requiere mantener la subrutina actual en ip, a diferencia de todos los ejemplos anteriores donde contenía la subrutina siguiente a llamar.

Empieza: ip = "hilo // puntos a ' ' salto *()*ip) // seguir punteros a la primera instrucción de 'push', NO avanzar ip todavíahilo: "i_pushA "i_pushB "i_add ...i_pushA: "empujar "Ai_pushB: "empujar "Bi_add: "añadirempujar: *sp++ = *()*ip + 1) // ver 1 inicio anterior del bloque indirecto para la dirección de operación salto *()*++ip) // ip avanzado en hilo, saltar a través del siguiente bloque indirecto a la siguiente subrutinaañadir: adición1 = *...sp addend2 = *...sp *sp++ = adición1 + addend2 salto *()*++ip)

Enhebrado de subrutinas

El llamado "código subproceso de subrutina" (también "código subproceso de llamada") consta de una serie de "llamadas" instrucciones (o direcciones de funciones a "llamar", a diferencia del uso directo de subprocesos de "saltar"). Los primeros compiladores para ALGOL, Fortran, Cobol y algunos sistemas Forth a menudo producían código con hilos de subrutinas. El código en muchos de estos sistemas operaba en una pila de operandos de último en entrar, primero en salir (LIFO), para los cuales la teoría del compilador estaba bien desarrollada. La mayoría de los procesadores modernos tienen soporte de hardware especial para la subrutina 'llamada'. y "regresar" instrucciones, por lo que la sobrecarga de una instrucción de máquina adicional por envío se reduce un poco.

Anton Ertl, el co-creador del compilador Gforth, afirmó que "a diferencia de los mitos populares, el subprocesamiento de subrutinas suele ser más lento que el subproceso directo". Sin embargo, las pruebas más recientes de Ertl muestran que el subprocesamiento de subrutinas es más rápido que el subproceso directo en 15 de los 25 casos de prueba. Más específicamente, descubrió que el subprocesamiento directo es el modelo de subprocesamiento más rápido en los procesadores Xeon, Opteron y Athlon, el subproceso indirecto es el más rápido en los procesadores Pentium M y el subproceso de subrutinas es el más rápido en los procesadores Pentium 4, Pentium III y PPC.

Como ejemplo de subprocesamiento de llamadas para "presione A, presione B, agregue":

hilo: llamada pushA llamada pushB llamada añadir RetpushA: *sp++ = A RetpushB: *sp++ = B Retañadir: adición1 = *...sp addend2 = *...sp *sp++ = adición1 + addend2 Ret

Enhebrado de tokens

El código de subprocesos token implementa el subproceso 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 por 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, según la cantidad de operaciones admitidas. Siempre que el ancho del índice se elija para que sea más angosto que el puntero de una máquina, naturalmente será más compacto que los otros tipos de roscado sin mucho esfuerzo especial por parte del programador. Por lo general, tiene entre la mitad y las tres cuartas partes del tamaño de otros subprocesos, que a su vez tienen entre un cuarto y un octavo del tamaño del código sin subprocesos. Los punteros de la tabla pueden ser indirectos o directos. Algunos compiladores de Forth producen código de token. Algunos programadores consideran que el "p-code" generados por algunos compiladores de Pascal, así como los bytecodes utilizados por.NET, Java, BASIC y algunos compiladores de C, para token-threading.

Un enfoque común, históricamente, es el código de bytes, que generalmente usa 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 envío" y sigue la forma:

Empieza: vpc = "hiloDespacho: addr = decodificación()"vpc) // Convertir la siguiente operación bytecode en un puntero en código de máquina que lo implementa // Cualquier operación de interinstrucción se realiza aquí (por ejemplo, actualización del estado global, procesamiento de eventos, etc) salto addrCODE_PTR decodificación()BYTE_CODE #p) {} // En una codificación más compleja, puede haber varias tablas para elegir entre o controlar/mode flags retorno cuadro[*()*p)++];}hilo: /* Contiene código bytecode, no direcciones de máquina. Por lo tanto es más compacto. */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/cuadro: "añadir /* tabla[0] = dirección del código de máquina que implementa bytecode 0 */ "pushA /* mesa[1]... */ "pushB /* mesa[2]... */pushA: *sp++ = A salto DespachopushB: *sp++ = B salto Despachoañadir: adición1 = *...sp addend2 = *...sp *sp++ = adición1 + addend2 salto Despacho

Si la máquina virtual usa solo instrucciones de tamaño de byte, decode() es simplemente una búsqueda de thread, pero a menudo hay instrucciones de uso común de 1 byte más algunas instrucciones multibyte menos comunes (ver computadora con conjunto de instrucciones complejo), en cuyo caso decode() es más complejo. La decodificación de códigos de operación de un solo byte se puede manejar de manera muy simple y eficiente mediante una tabla de sucursales que utiliza el código de operación directamente como índice.

Para instrucciones donde las operaciones individuales son simples, como "empujar" y "agregar", la sobrecarga involucrada en decidir qué ejecutar es mayor que el costo de ejecutarlo realmente, por lo que estos intérpretes suelen ser mucho más lentos que el código de máquina. Sin embargo, para instrucciones más complejas ('compuestas'), el porcentaje de sobrecarga es proporcionalmente menos significativo.

Hay ocasiones en las que el código token-thread puede ejecutarse más rápido que el código de máquina equivalente cuando ese código de máquina termina siendo demasiado grande para caber en la memoria caché de instrucciones L1 de la CPU física. La mayor densidad de código del código de subprocesos, especialmente el código de subprocesos de token, puede permitir que encaje completamente en la memoria caché L1 cuando de otro modo no lo habría hecho, evitando así la hipertrofia de la memoria caché. Sin embargo, el código enhebrado consume tanto caché de instrucciones (para la implementación de cada operación) como caché de datos (para el código de bytes y las tablas) a diferencia del código de máquina que solo consume caché de instrucciones; esto significa que el código subproceso consumirá el presupuesto de la cantidad de datos que la CPU puede retener para su procesamiento en un momento dado. En cualquier caso, si el problema que se está calculando implica la aplicación de una gran cantidad de operaciones a una pequeña cantidad de datos, entonces el uso de código subproceso puede ser una optimización ideal.

Enhebrado Huffman

El código subproceso Huffman consiste en listas de tokens almacenados como códigos Huffman. Un código Huffman es una cadena de bits de longitud variable que identifica un token único. Un intérprete con subprocesos de Huffman localiza las subrutinas mediante una tabla de índice o un árbol de punteros por los que se puede navegar mediante el código de Huffman. El código Huffman-threaded es una de las representaciones más compactas conocidas para un programa de computadora. El índice y los códigos se eligen midiendo la frecuencia de llamadas a cada subrutina en el código. Las llamadas frecuentes reciben los códigos más cortos. Las operaciones con frecuencias aproximadamente iguales reciben códigos con longitudes de bits casi iguales. La mayoría de los sistemas con subprocesos de Huffman se han implementado como sistemas Forth de subprocesos directos y se utilizan 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 han sido en tarjetas inteligentes, juguetes, calculadoras y relojes. El código tokenizado orientado a bits que se usa en PBASIC puede verse como una especie de código con subprocesos de Huffman.

Subprocesos menos utilizados

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

RPL

El RPL de HP, introducido por primera vez en la calculadora HP-18C en 1986, es un tipo de lenguaje patentado híbrido de subprocesos directos e indirectos interpretados por subprocesos que, a diferencia de otros TIL, permite incorporar RPL &# 34;objetos" en el "runstream" es decir. El flujo de direcciones a través del cual avanza el puntero del intérprete. Un "objeto" RPL se puede considerar como un tipo de datos especial cuya estructura en memoria contiene una dirección a un "prólogo de objeto" al comienzo del objeto, y luego siguen los datos o el código ejecutable. El prólogo del objeto determina cómo se debe ejecutar o procesar el cuerpo del objeto. Usando el "bucle interno RPL", que fue inventado y publicado (y patentado) por William C. Wickes en 1986 y publicado en "Programming Environments", Institute for Applied Forth Research, Inc., 1988, la ejecución sigue así:

1. Dereferir la IP (puntero de instrucciones) y almacenarla en O (puntero de objeto actual)
2. Incremento de la IP por la longitud de un puntero de dirección
3. Dereferencia O y almacena su dirección en O_1 (este es el segundo nivel de indirectidad)
4. Control de transferencia al siguiente puntero o objeto incrustado mediante el ajuste del PC (contador de programa) a O_1 más un puntero de dirección
5. Vuelve al paso 1

Esto se puede representar de manera más precisa 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 "desreferencia".

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

PROLOG - título PROLOGO (La dirección prolog al inicio del código prolog se apunta a sí misma)
IF O + Δ =/= PC
Entonces GOTO INDIRECTO (Test for direct execution)
O = I - Δ (Correct O to point to start of embedded object)
I = I + α (Correcto I a punto después del objeto embebido donde α es la longitud del objeto)
INDIRECT (rest of prolog)

En los microprocesadores Saturn de HP que utilizan RPL, existe un tercer nivel de direccionamiento indirecto que es posible gracias a un truco de arquitectura/programación que permite una ejecución más rápida.

Sucursales

En todos los intérpretes, una rama simplemente cambia el puntero del hilo (ip) a una dirección diferente en el hilo. Una rama condicional de salto si es cero que salta solo si el valor de la parte superior de la pila es cero podría implementarse como se muestra a continuación. Este ejemplo utiliza la versión de parámetros incrustados de subprocesos directos, por lo que la línea &thread[123] es el destino de dónde saltar si la condición es verdadera, por lo que debe omitirse (ip++) si no se toma la rama.

hilo: ... "brz "hilo[123] ...brz: cuando_true_ip = *ip++ // Obtener la dirección de destino para rama si ()*...sp == 0) // Pop/Consume top de la pila y comprobar si es cero ip = cuando_true_ip salto *ip++

Servicios comunes

Separar las pilas de datos y retorno en una máquina elimina una gran cantidad de código de administración de pilas, lo que reduce sustancialmente el tamaño del código enhebrado. El principio de doble pila se originó tres veces de forma independiente: para los grandes sistemas de Burroughs, Forth y PostScript. Se utiliza en algunas máquinas virtuales Java.

A menudo hay tres registros presentes en una máquina virtual con subprocesos. Existe otro para pasar datos entre subrutinas ('palabras'). Estos son:

• ip o i (punto de instrucciones) de la máquina virtual (para no confundirse con el contador del programa del hardware subyacente que implementa el VM)
• w (puntero de trabajo)
• rp o r (punto de la pila de retorno)
• sp o s (parameter stack pointer for passing parameters between words)

A menudo, las máquinas virtuales con subprocesos, como las implementaciones de Forth, tienen una máquina virtual simple en el centro, que consta de tres primitivas. Esos son:

1. nido, también llamado docol
2. unnest, o semi_ s)
3. siguiente

En una máquina virtual de subprocesos indirectos, la que se proporciona aquí, las operaciones son:

 siguiente: *ip++ - w salto #w++ nido: ip - *rp++ w - ip siguiente unnest: *...rp - ip siguiente

Este es quizás el intérprete o máquina virtual más simple y rápido.