En informática , el código subproceso es una técnica de programación en la que el código tiene una forma que esencialmente consiste enteramente en llamadas a subrutinas . A menudo se utiliza en compiladores , que pueden generar código en esa forma o implementarlo ellos mismos en esa forma. 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 enhebrado tiene mejor densidad que el código generado mediante técnicas de generación alternativas y convenciones de llamada alternativas . En arquitecturas en caché , es posible que se ejecute un poco más lento. [ cita necesaria ] 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 muchos errores de caché . [1] 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 roscado es mejor conocido por su uso en muchos compiladores de lenguajes de programación , como Forth , muchas implementaciones de BASIC , algunas implementaciones de COBOL , primeras versiones de B , [2] y otros lenguajes para pequeñas minicomputadoras y satélites de radioaficionados . [ cita necesaria ]
La forma común de crear programas de computadora es utilizar 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, como es específico de una plataforma de hardware , no es portátil. Un enfoque diferente consiste en generar instrucciones para una máquina virtual y utilizar un intérprete en cada plataforma de hardware. El intérprete crea una instancia del entorno de la máquina virtual y ejecuta las instrucciones. Por lo tanto, sólo se debe compilar el intérprete.
Las primeras computadoras tenían relativamente poca memoria. Por ejemplo, la mayoría de los Data General Nova , IBM 1130 y muchos de los primeros microordenadores tenían sólo 4 kB de RAM instalados. En consecuencia, se dedicó mucho tiempo a intentar encontrar formas de reducir el tamaño de un programa para que quepa 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 memoria. Ésta fue la razón por la que Microsoft BASIC es un intérprete: [a] 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 máquina, por lo que el compilador, el código fuente y la salida deben estar en la memoria al mismo tiempo. En un intérprete, no hay salida.
El código con subprocesos es un estilo de formato para código compilado que minimiza el uso de memoria. En lugar de escribir cada paso de una operación en cada aparición del 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 de la memoria (consulte " No te repitas "). La aplicación de nivel superior en estos programas puede consistir únicamente en llamadas a subrutinas. Muchas de estas subrutinas, a su vez, constan únicamente de llamadas a subrutinas de nivel inferior.
Las computadoras centrales 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 sólo 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 solucionar este problema, los sistemas de código subprocesos utilizaban pseudocódigo para representar 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 tabla de sucursales , tabla de despacho o tabla de métodos virtuales , todas las cuales constan de una tabla de direcciones de subrutinas.
Durante la década de 1970, los diseñadores de hardware dedicaron un esfuerzo considerable a hacer que las llamadas a subrutinas fueran más rápidas y sencillas. En los diseños mejorados, sólo se utiliza una única instrucción para llamar a una subrutina, por lo que el uso de una pseudoinstrucción no ahorra espacio. [ cita necesaria ] Además, la realización de estas llamadas está casi libre de gastos generales adicionales. Hoy en día, aunque casi todos los lenguajes de programación se centran en aislar el código en subrutinas, lo hacen por claridad y facilidad de mantenimiento del código, no para ahorrar espacio.
Los sistemas de código subproceso ahorran espacio al reemplazar esa lista de llamadas a funciones, donde solo la dirección de 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 atrás sólo una lista de direcciones. [3] [4] [5] [6] [7]
A lo largo de los años, los programadores han creado muchas variaciones de ese "intérprete" o "pequeño selector". La dirección particular en la lista de direcciones se puede extraer usando un índice, un registro de propósito general o un puntero . Las direcciones pueden ser directas o indirectas, contiguas o no contiguas (unidas por punteros), relativas o absolutas, resueltas en tiempo de compilación o construidas dinámicamente. Ninguna variación es la "mejor" para todas las situaciones.
Para ahorrar espacio, los programadores comprimieron las listas de llamadas de subrutinas en listas simples de direcciones de subrutinas y utilizaron un pequeño bucle para llamar a cada subrutina por turno. Por ejemplo, el siguiente pseudocódigo utiliza esta técnica para sumar dos números A y B. En el ejemplo, la lista está etiquetada como hilo y una variable ip (puntero de instrucción) rastrea nuestro lugar dentro de la lista. Otra variable sp (puntero de pila) contiene una dirección en otra parte de la memoria que está disponible para contener un valor temporalmente.
inicio : ip = & hilo // apunta a la dirección '&pushA', no a la etiqueta textual 'hilo' arriba : salto * ip ++ // sigue ip a la dirección en el hilo, sigue esa dirección a la subrutina, avanza el hilo ip : & pushA & pushB & add ... pushA : * sp ++ = A // sigue sp hasta la memoria disponible, almacena A allí, avanza sp al siguiente salto superior pushB : * sp ++ = B jump top add : addend1 = *- - sp // Saca el valor superior de la pila addend2 = *-- sp // Saca el segundo valor de la pila * sp ++ = addend1 + addend2 // Suma los dos valores y almacena el resultado en la parte superior de la pila saltar arriba
El bucle de llamada topes tan simple que se puede repetir en línea al final de cada subrutina. El control ahora salta una vez, desde el final de una subrutina hasta el inicio de otra, en lugar de saltar dos veces mediante top. Por ejemplo:
inicio : ip = & thread // ip apunta a &pushA (que apunta a la primera instrucción de pushA) jump * ip ++ // envía control a la primera instrucción de pushA y avanza ip a &pushB thread : & pushA & pushB & add . .. pushA : * sp ++ = A // sigue sp hasta la memoria disponible, almacena A allí, avanza sp al siguiente salto * ip ++ // envía el control donde ip dice (es decir, pushB) y avanza ip pushB : * sp ++ = B jump * ip ++ add : addend1 = *-- sp // Extrae el valor superior de la pila addend2 = *-- sp // Extrae el segundo valor de la pila * sp ++ = addend1 + addend2 / / Suma los dos valores y almacena el resultado en la parte superior de la pila jump * ip ++ Esto se llama código de subproceso directo (DTC). Aunque la técnica es más antigua, el primer uso ampliamente difundido del término "código subproceso" es probablemente el artículo de 1973 de James R. Bell "Código subproceso". [8]
En 1970, Charles H. Moore inventó una disposición más compacta, el código de subprocesos indirectos (ITC), para su máquina virtual Forth. Moore llegó a este acuerdo porque las minicomputadoras Nova tenían un bit de dirección indirecta en cada dirección, lo que hacía que ITC fuera fácil y rápido. Más tarde, dijo que lo encontró tan conveniente que lo propagó a todos los diseños posteriores de Forth. [9]
Hoy en día, algunos compiladores de Forth generan código de subproceso directo mientras que otros generan código de subproceso indirecto. Los ejecutables actúan igual en ambos sentidos.
Prácticamente todo el código de subprocesos ejecutable utiliza uno u otro de estos métodos para invocar subrutinas (cada método se denomina "modelo de subprocesos").
Las direcciones en el hilo son las direcciones del lenguaje de máquina. Esta forma es simple, pero puede tener gastos generales porque el subproceso consta solo de direcciones de máquina, por lo que todos los parámetros adicionales deben cargarse indirectamente desde la memoria. Algunos sistemas Forth producen código de subproceso directo. En muchas máquinas, el enhebrado directo es más rápido que el enhebrado por subrutina (consulte la referencia a continuación).
Un ejemplo de una máquina apiladora podría ejecutar la secuencia "empujar A, empujar B, agregar". Eso podría traducirse al siguiente hilo y rutinas, donde ipse inicializa en la dirección etiquetada thread(es decir, la dirección donde &pushAestá almacenada).
#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 control a la primera instrucción de pushA y avanza ip al hilo &pushB : & pushA & pushB & agrega ... pushA : PUSH ( A ) jump * ip ++ // envía control donde ip dice (es decir, a pushB ) y avanzar ip pushB : PUSH ( B ) saltar * ip ++ agregar : resultado = POP () + POP () PUSH ( resultado ) saltar * ip ++ Alternativamente, se pueden incluir operandos en el hilo. Esto puede eliminar algunas indirecciones necesarias arriba, pero hace que el hilo sea más grande:
#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) inicio : ip = & salto de hilo * ip ++ hilo : & push & A // dirección donde se almacena A, no literal A & 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 ) // Leer el valor de la variable y presionar salto de pila * ip ++ agregar : resultado = POP () + POP () PUSH ( resultado ) salto * ip ++ El subproceso 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 tanto, el código indirecto suele ser más compacto que el código de subproceso directo. La dirección indirecta normalmente 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 subproceso directo puede ser significativo. Los sistemas FORTH más antiguos suelen producir código de subprocesos indirectos.
Por ejemplo, si el objetivo es ejecutar "empujar A, empujar B, agregar", se podría utilizar lo siguiente. Aquí, ipse inicializa en la dirección &thread, cada fragmento de código ( push, add) se encuentra mediante una doble dirección 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 actual en ip, a diferencia de todos los ejemplos anteriores donde contenía la siguiente subrutina a llamar.
inicio : ip = & thread // apunta a '&i_pushA' jump * ( * ip ) // sigue los punteros a la primera instrucción de 'push', NO avance la ip todavía thread : & 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 el salto de dirección del operando * ( *++ 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 jump * ( *++ ip ) El llamado "código de subproceso de subrutina" (también "código de subproceso de llamada") consiste en una serie de instrucciones de "llamada" en lenguaje de máquina (o direcciones de funciones a "llamar", a diferencia del uso de "saltar" del subproceso directo ). Los primeros compiladores de ALGOL , Fortran, Cobol y algunos sistemas Forth a menudo producían código con subprocesos de subrutina. El código de muchos de estos sistemas funcionaba con una pila de operandos de último en entrar, primero en salir (LIFO), para la cual la teoría del compilador estaba bien desarrollada. La mayoría de los procesadores modernos tienen soporte de hardware especial para instrucciones de "llamada" y "retorno" de subrutinas, por lo que la sobrecarga de una instrucción de máquina adicional por envío es algo menor.
Anton Ertl, cocreador del compilador Gforth , afirmó que "a diferencia de los mitos populares, el subprocesamiento de subrutinas suele ser más lento que el subprocesamiento directo". [10] Sin embargo, las pruebas más recientes de Ertl [1] muestran que el subproceso de subrutina es más rápido que el subproceso directo en 15 de 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 subprocesamiento indirecto es más rápido en los procesadores Pentium M y el subproceso de subrutina es más rápido en los procesadores Pentium 4, Pentium III y PPC.
Como ejemplo de subprocesamiento de llamadas para "presionar A, presionar B, agregar":
hilo : llamar a pushA llamar a pushB llamar a agregar ret pushA : * sp ++ = A ret pushB : * sp ++ = B ret agregar : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 ret El código de subprocesos de token implementa el subproceso como una lista de índices en una tabla de operaciones; Naturalmente, el ancho del índice se elige para que sea lo más pequeño posible para lograr 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 se elija que el ancho del índice sea más estrecho 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 indicadores de la tabla pueden ser indirectos o directos. Algunos compiladores de Forth producen código con subprocesos de token. Algunos programadores consideran que el " código p " generado por algunos compiladores Pascal , así como los códigos de bytes utilizados por .NET , Java , BASIC y algunos compiladores de C , son subprocesamiento de tokens.
Históricamente, un enfoque común es el código de bytes , que normalmente utiliza códigos de operación de 8 bits con una máquina virtual basada en pila. El intérprete de código de bytes arquetípico se conoce como "intérprete de decodificación y envío" y tiene la siguiente forma:
inicio : vpc = & envío de subprocesos : addr = decodificar ( & vpc ) // Convertir la siguiente operación de código de bytes en un puntero al código de máquina que lo implementa // Cualquier operación entre instrucciones se realiza aquí (por ejemplo, actualización del estado global, procesamiento de eventos, etc) jump addr CODE_PTR decode ( BYTE_CODE ** p ) { // En una codificación más compleja, puede haber varias tablas para elegir o indicadores de control/modo return table [ * ( * p ) ++ ]; } hilo : /* Contiene código de bytes, no direcciones de máquina. Por tanto es más compacto. */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/ table : & add /* table[0] = dirección del código de máquina que implementa el código de bytes 0 */ & pushA /* table[1] . .. */ & pushB /* table[2] ... */ pushA : * sp ++ = A envío de salto pushB : * sp ++ = B envío de salto add : addend1 = *-- sp addend2 = *-- sp * sp ++ = sumando1 + despacho de salto sumando2 Si la máquina virtual usa solo instrucciones de tamaño de bytes, decode()es simplemente una búsqueda de thread, pero a menudo hay instrucciones de 1 byte de uso común más algunas instrucciones multibyte menos comunes (consulte el conjunto de instrucciones complejas de computadora ), 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 rama usando 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 dichos 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 gastos generales 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 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 quepa completamente en la caché L1 cuando de otro modo no lo habría hecho, evitando así la destrucción de la caché. Sin embargo, el código con subprocesos consume tanto el caché de instrucciones (para la implementación de cada operación) como el caché de datos (para el código de bytes y las tablas), a diferencia del código de máquina que solo consume el caché de instrucciones; esto significa que el código de subprocesos consumirá el presupuesto de la cantidad de datos que la CPU puede retener para procesar en un momento dado. En cualquier caso, si el problema que se está calculando implica aplicar una gran cantidad de operaciones a una pequeña cantidad de datos, entonces usar código subproceso puede ser una optimización ideal.[4]
El código de subprocesos de Huffman consta de listas de tokens almacenados como códigos de Huffman . Un código Huffman es una cadena de bits de longitud variable que identifica un token único. Un intérprete de subprocesos de Huffman localiza subrutinas utilizando una tabla de índice o un árbol de punteros por los que se puede navegar mediante el código de Huffman. El código de subprocesos de Huffman es una de las representaciones más compactas conocidas de 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 Huffman se han implementado como sistemas Forth con subprocesos directos y se utilizan para empaquetar grandes cantidades de código de ejecución lenta en microcontroladores pequeños y económicos . Los usos más publicados [11] se han producido en tarjetas inteligentes, juguetes, calculadoras y relojes. El código tokenizado orientado a bits utilizado en PBASIC puede verse como una especie de código con subprocesos de Huffman.
Un ejemplo es el subprocesamiento de cadenas, en el que las operaciones se identifican mediante cadenas, generalmente buscadas en una tabla hash. Esto se utilizó 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.
El RPL de HP , introducido por primera vez en la calculadora HP-18C en 1986, es un tipo de lenguaje interpretativo de subprocesos (TIL ) híbrido (de subproceso directo e indirecto) [12] que, a diferencia de otros TIL, permite la incorporación de RPL. "objetos" en el "runstream", 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 de objeto" al inicio del objeto, y luego le siguen datos o código ejecutable. El prólogo del objeto determina cómo se debe ejecutar o procesar el cuerpo del objeto. Utilizando el "bucle interno RPL", [13] que fue inventado y patentado [14] por William C. Wickes en 1986 y publicado en 1988, la ejecución es la siguiente: [15]
Esto se puede representar más precisamente por:
O = [yo] Yo = Yo + Δ 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 -> PROLOG (La dirección del prólogo al inicio del código del prólogo apunta a sí misma) SI O + Δ =/= PC ENTONCES IR A INDIRECTO (Prueba para ejecución directa) O = I - Δ (Corrija O para que apunte al inicio del objeto incrustado) I = I + α (Corrija 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 direccionamiento indirecto posible gracias a un truco arquitectónico/de programación que permite una ejecución más rápida. [13]
En todos los intérpretes, una rama simplemente cambia el puntero del hilo ( ip) a una dirección diferente en el hilo. Se podría implementar una rama condicional de salto si cero que salta solo si el valor superior de la pila es cero, como se muestra a continuación. Este ejemplo utiliza la versión de parámetro incrustado de subprocesamiento directo, por lo que la &thread[123]línea es el destino al que saltar si la condición es verdadera, por lo que se debe omitir ( ip++) si no se toma la rama.
hilo : ... & brz & hilo [ 123 ] ... brz : when_true_ip = * ip ++ // Obtener la dirección de destino para la rama if ( *-- sp == 0 ) // Pop/Consume la parte superior de la pila y verifica si es cero ip = cuando_true_ip salto * ip ++ Separar las pilas de datos y de 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 subproceso. El principio de doble pila se originó tres veces de forma independiente: para los sistemas grandes 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:
A menudo, las máquinas virtuales con subprocesos , como las implementaciones de Forth, tienen en el fondo una máquina virtual simple, que consta de tres primitivas . Esos son:
En una máquina virtual de subproceso indirecto, la que se muestra aquí, las operaciones son:
siguiente : * ip ++ -> w salto ** w ++ nido : ip -> * rp ++ w -> ip siguiente unnest : *-- rp -> ip siguiente 
ipcon un parámetro de función