En informática , el código enhebrado es una técnica de programación en la que el código tiene una forma que consiste esencialmente en llamadas a subrutinas . Se utiliza a menudo 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 a código de máquina .
El código enhebrado tiene una mejor densidad que el código generado por técnicas de generación alternativas y por convenciones de llamada alternativas . En arquitecturas en caché , puede ejecutarse un poco más lento. [ cita requerida ] Sin embargo, un programa que es lo suficientemente pequeño como para caber en la memoria caché de un procesador de computadora puede ejecutarse más rápido que un programa más grande que sufre muchas fallas 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 la caché.
El código enhebrado es más conocido por su uso en muchos compiladores de lenguajes de programación , como Forth , muchas implementaciones de BASIC , algunas implementaciones de COBOL , versiones tempranas de B , [2] y otros lenguajes para pequeñas minicomputadoras y para satélites de radioaficionados . [ cita requerida ]
La forma habitual de crear programas informáticos 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 es 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 tanto, solo es necesario compilar el intérprete.
Las primeras computadoras tenían relativamente poca memoria. Por ejemplo, la mayoría de las Data General Nova , IBM 1130 y muchas de las primeras microcomputadoras tenían solo 4 kB de RAM instalada. En consecuencia, se dedicó mucho tiempo a intentar 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 memoria. Esta 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 de máquina, por lo que el compilador, el código fuente y la salida deben estar todos en la memoria al mismo tiempo. En un intérprete, no hay salida.
El código enhebrado 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 una de sus apariciones 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. De este modo, cada bit existe en un solo lugar de la memoria (consulte " No se repita "). La aplicación de nivel superior en estos programas puede consistir únicamente en llamadas a subrutinas. Muchas de estas subrutinas, a su vez, también constan únicamente de llamadas a subrutinas de nivel inferior.
Los mainframes y algunos de los primeros microprocesadores, como el RCA 1802, necesitaban 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 cambia la dirección de la subrutina 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 enhebrado utilizaban pseudocódigo para representar llamadas a funciones en un único operador. En tiempo de ejecución, un pequeño "intérprete" escaneaba el código de nivel superior, extraía la dirección de la subrutina en la memoria y la llamaba. En otros sistemas, este mismo concepto básico se implementa como una tabla de ramificaciones , 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 dedicaron un esfuerzo considerable a hacer que las llamadas a subrutinas fueran más rápidas y sencillas. En los diseños mejorados, solo se gasta una única instrucción para llamar a una subrutina, por lo que el uso de una pseudoinstrucción no ahorra espacio. [ cita requerida ] Además, el rendimiento de estas llamadas está casi libre de sobrecarga adicional. Hoy, 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 enhebrado ahorran espacio al reemplazar esa lista de llamadas de función, 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 de función con el código de operación de llamada eliminado, dejando solo 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 utilizando un índice, un registro de propósito general o un puntero . Las direcciones pueden ser directas o indirectas, contiguas o no contiguas (vinculadas por punteros), relativas o absolutas, resueltas en tiempo de compilación o construidas dinámicamente. No existe una única variación que sea "la mejor" para todas las situaciones.
Para ahorrar espacio, los programadores comprimieron las listas de llamadas a 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 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 guardar un valor temporalmente.
start : ip = & thread // apunta a la dirección '&pushA', no a la etiqueta textual 'thread' top : jump * ip ++ // sigue ip hasta la dirección en el hilo, sigue esa dirección hasta la subrutina, avanza ip thread : & pushA & pushB & add ... pushA : * sp ++ = A // sigue sp hasta la memoria disponible, almacena A allí, avanza sp al siguiente jump top pushB : * sp ++ = B jump top 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 top
El bucle de llamada en 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 comienzo de otra, en lugar de saltar dos veces a través de top. Por ejemplo:
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 : * sp ++ = A // sigue a sp hasta la memoria disponible, almacena A allí, avanza sp al siguiente jump * ip ++ // envía el control a donde ip dice (es decir, a 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 denomina código de subproceso directo (DTC). Aunque la técnica es más antigua, el primer uso generalizado del término "código de subproceso" probablemente sea el artículo de James R. Bell de 1973 "Código de subproceso". [8]
En 1970, Charles H. Moore inventó un sistema más compacto, el código indirecto enhebrado (ITC), para su máquina virtual Forth. Moore llegó a este sistema porque las minicomputadoras Nova tenían un bit de indirección en cada dirección, lo que hacía que el ITC fuera fácil y rápido. Más tarde, dijo que lo encontró tan conveniente que lo propagó a todos los diseños Forth posteriores. [9]
En la actualidad, algunos compiladores Forth generan código con subprocesos directos, mientras que otros generan código con subprocesos indirectos. Los ejecutables actúan de la misma manera en ambos casos.
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").
Las direcciones en el hilo son las direcciones del lenguaje de máquina. Esta forma es simple, pero puede tener costos adicionales porque el hilo 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 con subproceso directo. En muchas máquinas, el subproceso directo es más rápido que el subproceso con subrutinas (consulte la referencia a continuación).
Un ejemplo de una máquina de pila podría ejecutar la secuencia "push A, push B, add". Esto podría traducirse al siguiente hilo y rutinas, donde ipse inicializa en la dirección etiquetada thread(es decir, la dirección donde &pushAestá almacenado).
#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 a donde ip dice (es decir, a pushB) y avanza ip pushB : PUSH ( B ) jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++ Como alternativa, se pueden incluir operandos en el hilo. Esto puede eliminar parte de la indirección necesaria anteriormente, pero hace que el hilo sea más grande:
#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 ) // Leer el valor de la variable y empujar en la pila jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++ El subprocesamiento indirecto utiliza punteros a ubicaciones que, a su vez, apuntan al código de la máquina. El puntero indirecto puede ir seguido de operandos que se almacenan en el "bloque" indirecto en lugar de almacenarlos repetidamente en el subproceso. Por lo tanto, el código indirecto suele ser más compacto que el código de subprocesamiento directo. La indirección suele hacerlo más lento, aunque suele ser 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 subprocesamiento indirecto.
Por ejemplo, si el objetivo es ejecutar "push A, push B, add", 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 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 llamaría.
start : ip = & thread // apunta a '&i_pushA' jump * ( * ip ) // sigue los punteros a la 1ra instrucción de 'push', NO avanza 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 ) // busca la dirección del operando 1 después del inicio del bloque indirecto jump * ( *++ ip ) // avanza ip en el hilo, salta a través del siguiente bloque indirecto a la siguiente subrutina add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 jump * ( *++ ip ) El llamado "código de subprocesos de subrutina" (también "código de subprocesos de llamada") consiste en una serie de instrucciones de "llamada" en lenguaje de máquina (o direcciones de funciones a "llamar", en oposición al uso de "saltos" en subprocesos directos). Los primeros compiladores para ALGOL , Fortran, Cobol y algunos sistemas Forth a menudo producían código de subprocesos de subrutina. El código en muchos de estos sistemas operaba en una pila de operandos de tipo ú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 tienen soporte de hardware especial para instrucciones de "llamada" y "retorno" de subrutina, por lo que la sobrecarga de una instrucción de máquina adicional por envío se reduce un poco.
Anton Ertl, cocreador del compilador Gforth , afirmó que "en contraste con 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 subprocesamiento de subrutinas es más rápido que el subprocesamiento 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 subprocesamiento indirecto es más rápido en los procesadores Pentium M y el subprocesamiento de subrutinas es más rápido en los procesadores Pentium 4, Pentium III y PPC.
Como ejemplo de subproceso de llamadas para "push A, push B, add":
hilo : llamar a pushA llamar a pushB llamar a añadir ret pushA : * sp ++ = A ret pushB : * sp ++ = B ret añadir : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 ret El código con subprocesos mediante tokens 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 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 el ancho del índice se elija para que sea más estrecho que un puntero de máquina, naturalmente será más compacto que los otros tipos de subprocesos 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 son a su vez 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 Forth producen código con subprocesos mediante tokens. 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.
Un enfoque común, históricamente, 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 envío" y sigue el formato:
start : vpc = & thread dispatch : addr = decode ( & vpc ) // Convierte la siguiente operación de bytecode en un puntero al código de máquina que lo implementa // Aquí se realizan todas las operaciones entre instrucciones (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 ) ++ ]; } thread : /* 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 de máquina que implementa el bytecode 0 */ & pushA /* table[1] ... */ & pushB /* table[2] ... */ pushA : * sp ++ = A jump dispatch pushB : * sp ++ = B jump dispatch add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 jump dispatch Si la máquina virtual utiliza únicamente instrucciones de tamaño byte, decode()es simplemente una búsqueda desde 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 complejo de la 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 ramificación que utiliza el código de operación directamente como índice.
En el caso de las instrucciones en las que las operaciones individuales son sencillas, como "push" y "add", el gasto adicional que supone 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 de máquina. Sin embargo, en el caso de las instrucciones más complejas ("compuestas"), el porcentaje de gasto adicional es proporcionalmente menos significativo.
Hay ocasiones en las que el código con subprocesos de token puede ejecutarse más rápido que el código de máquina equivalente cuando este 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 con subprocesos, especialmente el código con subprocesos de token, puede permitir que encaje completamente en la caché L1 cuando de otra manera no lo hubiera hecho, evitando así la sobrecarga de la caché. Sin embargo, 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 código de bytes y las tablas), a diferencia del código de máquina que solo consume la caché de instrucciones; esto significa que el código con subprocesos consumirá el presupuesto para la cantidad de datos que la CPU puede mantener para su procesamiento 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 el uso de código con subprocesos puede ser una optimización ideal. [4]
El código de subprocesos 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 de subprocesos de Huffman localiza subrutinas utilizando una tabla de índices o un árbol de punteros que se pueden navegar mediante el código de Huffman. El código de subprocesos de Huffman 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 de subprocesos de Huffman se han implementado como sistemas Forth de subprocesos directos 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] han sido 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 de subprocesos de Huffman.
Un ejemplo es el enhebrado de cadenas, en el que las operaciones se identifican mediante cadenas, que normalmente se buscan mediante 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 (TIL) híbrido (de subproceso directo e indirecto) propietario [12] que, a diferencia de otros TIL, permite la incorporación de "objetos" RPL 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 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. 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 se produce de la siguiente manera: [15]
Esto se puede representar con mayor precisión así:
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:
PRÓLOGO -> PRÓLOGO (La dirección del prólogo al comienzo del código del prólogo apunta a sí misma) SI O + Δ =/= PC LUEGO IR A INDIRECTO (Prueba de ejecución directa) O = I - Δ (O correcto para apuntar al inicio del objeto incrustado) I = I + α (Corrija I al punto 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, hay un tercer nivel de indirección que es 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. Una rama condicional de salto si es cero que salta solo si el valor de la parte superior de la pila es cero se podría implementar como se muestra a continuación. Este ejemplo utiliza la versión de parámetro incorporado de subprocesamiento directo, por lo que la &thread[123]línea es el destino de dónde 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 ) // Extraer/consumir la parte superior de la pila y verificar si es cero ip = when_true_ip jump * ip ++ La separación de las pilas de datos y de retorno en una máquina elimina una gran cantidad de código de gestión de pila, 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 sistemas grandes de Burroughs , Forth y PostScript . Se utiliza en algunas máquinas virtuales de Java .
En una máquina virtual con subprocesos suelen estar presentes tres registros . 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 su núcleo una máquina virtual simple, que consta de tres primitivas :
En una máquina virtual con subprocesos indirectos, como la que se muestra aquí, las operaciones son:
siguiente : * ip ++ -> w jump ** w ++ anidar : ip -> * rp ++ w -> ip next desanidar : *-- rp -> ip next 
ipcon un parámetro de función