En ciencias de la computación, el término código enhebrado se refiere a una técnica de implementación del compilador donde el código generado tiene una forma que esencialmente consiste enteramente en llamadas a subrutinas. El código puede ser procesado por un intérprete, o simplemente puede ser una secuencia de instrucciones de llamadas a código de máquina.

Una de las principales ventajas del código enhebrado es que es muy compacto, comparado al código generado por técnicas alternativas de generación del código y de convención de llamadas. Esta ventaja usualmente viene a expensas de una velocidad de ejecución ligeramente más lenta (usualmente apenas una sola instrucción de máquina). Sin embargo, a veces hay un efecto sinergético - a veces un código más compacto es más pequeño y significativamente más rápido que el código no enhebrado.Speed of various interpreter dispatch techniques V2 Un programa suficientemente pequeño para caber enteramente en la memoria de acceso aleatorio puede correr más rápido que un programa menos compacto en el espacio de intercambio que requiere un constante acceso mecánico de la unidad de disco, aunque sufra de la sobrecarga en la interpretación del código enhebrado. Similarmente, un programa lo suficientemente pequeño para caber enteramente en el caché del procesador de la computadora puede correr más rápido que un programa menos compacto que sufra fallas de caché constantes.

El código enhebrado es bien conocido como la técnica de implementación comúnmente usada en el lenguaje de programación Forth. También fue usado en las versiones tempranas del lenguaje de programación B, así como en muchas implementaciones de BASIC, y algunas implementaciones de COBOL y de otros lenguajes para pequeños microcomputadores.

Historia que llevó al código enhebrado

La manera común de hacer programas de computadora es usando un compilador para "traducir" un programa escrito en una cierto lenguaje simbólico al código de máquina. El código es típicamente rápido pero no es portable puesto que el código binario ejecutable es diseñado para una plataforma de hardware específica. Un acercamiento diferente usa un conjunto de instrucciones de una máquina virtual - que no tiene un destino particular de hardware. Un intérprete lo ejecuta en cada nuevo hardware de destino.

Los computadores tempranos tenían relativamente poca memoria. Por ejemplo, la mayoría de los Data General Nova, IBM 1130, y muchas computadores Apple II tenían solamente 4 k palabras de memoria RAM instalada. Consecuentemente se pasaba mucho tiempo intentando encontrar formas de reducir el tamaño de los programas de tal manera que pudieran caber en la memoria disponible. Al mismo tiempo, los computadores eran relativamente lentos, así que la interpretación simple era perceptiblemente mucho más lenta que ejecutar el código de máquina.

En vez de escribir cada paso de una operación en cada parte del programa donde era necesaria, los programadores ahorraban memoria escribiendo cada paso de tales operaciones una sola vez y poniéndolo en una subrutina (ver "no te repitas").

Este proceso —la refactorización de código— es usado hoy, aunque por diversas razones. En estos programas, la aplicación del nivel superior puede consistir de nada más que llamadas a subrutinas. A su vez, muchas de estas subrutinas, también no consisten nada más que llamadas a subrutinas de nivel inferior.

Los mainframes y algunos microprocesadores tempranos tales 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 es constantemente repetida, sólo cambiando la dirección de la subrutina desde una llamada a la siguiente. Usando la memoria para almacenar las mismas instrucciones repetidamente era un desperdicio.

La respuesta simple fue una tabla de saltos (es decir una tabla consistiendo solo en las direcciones contiguas de las subrutinas - usualmente extraídas usando un índice, un registro de propósitos generales o un puntero). Las direcciones pueden ser directas o indirectas, contiguas o no contiguas (encadenadas por punteros), relativas o absolutas, resueltas en tiempo de compilación o construidas dinámicamente —pero el programa se convierte en una lista de puntos de entrada al código real a ser ejecutado—. Esta técnica "se ha reinventado" con los nombres de "código enhebrado", "tabla de despacho" o "tabla de método virtual" - todas estas técnicas llenan propósitos similares.

Desarrollo del código enhebrado

Para ahorrar espacio, los programadores exprimieron las listas códigos de llamadas a subrutinas y las convirtieron en simples listas con solo las direcciones de las subrutinas, y usaron un pequeño loop para llamar a cada subrutina una por una. Por ejemplo:

start: thread: pushA: *sp++ = A tp = &thread &pushA jump top top: &pushB pushB: *sp++ = B jump *tp++ &add jump top ... add: *sp++ = *--sp + *--sp jump top

En este caso, la decodificación de los bytecodes se realiza una sola vez, durante la compilación o la carga de programa, así que no es repetida cada vez que una instrucción es ejecutada. Esto puede ahorrar mucho tiempo y espacio cuando la sobrecarga por la decodificación (decode) y el enviar (dispath) es grande comparado al costo de la ejecución.

Observe, sin embargo, que las direcciones en thread para &pushA, &pushB, etc., tienen dos o más bytes, comparados a típicamente un byte, para el intérprete de decodificar (decode) y enviar (dispath) descrito arriba. En general las instrucciones para un intérprete de decodificar y enviar pueden ser de cualquier tamaño. Como ejemplo, un intérprete de decodificar y enviar para simular un Intel Pentium decodifica las instrucciones con un rango de 1 a 16 bytes. Sin embargo, los sistemas de bytecode eligen típicamente códigos de 1 byte para las operaciones más comunes. Así, el enhebrado a menudo tiene un costo de espacio más alto que los bytecodes. En la mayoría de los usos, la reducción en costo de decodificar compensa el aumento en costo de espacio.

Observe también que mientras que los bytecodes son nominalmente independientes de la máquina, el formato y el valor de los punteros en el enhebrado generalmente dependen de la máquina destino que está ejecutando al intérprete. Así, un intérprete puede cargar un programa bytecode portable, decodificar los bytecodes para generar código enhebrado independiente de la plataforma, luego ejecutar el código enhebrado sin referencia adicional a los bytecodes.

El loop es simple, así que está duplicado en cada handler, removiendo jump top de la lista de instrucciones de máquina necesarias para ejecutar cada instrucción del intérprete. Como ejemplo:

start: thread: pushA: *sp++ = A tp = thread &pushA jump *tp++ jump *tp++ &pushB pushB: *sp++ = B &add jump *tp++ ... add: *sp++ = *--sp + *--sp jump *tp++

Esto se llama código enhebrado directo (DTC). Aunque la técnica sea más vieja, el primer uso extensamente circulado del término "código enhebrado" es probablemente el artículo "código enhebrado" de Bell de 1973.James R. Bell, "Threaded Code", CACM, 1973, 16, 6, pp 370–372

En 1970, Charles H. Moore inventó una notación más compacta para su máquina virtual Forth: el código enhebrado indirecto (ITC). Originalmente, Moore inventó esto porque era fácil y rápido en los minicomputadores de NOVA, que tenían un bit de indirección en cada dirección. Moore dijo (en comentarios publicados en la edición de la revista Byte sobre Forth) que él encontró esto tan conveniente que lo propagó en todos los diseños Forth posteriores.

Algunos compiladores Forth compilan los programas Forth en código enhebrado directo, mientras que otros hacen código enhebrado indirecto. Los programas actúan igual de cualquier manera.

Modelos de enhebrado

Prácticamente todo el código enhebrado ejecutable usa uno u otro de estos métodos para invocar subrutinas (cada método es llamado un "modelo de enhebrado").

Enhebrado directo

Las direcciones en el enhebrado son las direcciones del lenguaje de máquina. Esta forma es simple, pero puede tener sobrecargas porque el enhebrado consiste solo de direcciones de máquina, así que todos los otros parámetros deben ser cargados indirectamente desde la memoria. Algunos sistemas Forth producen código enhebrado directo. En muchas máquinas el enhebrado directo es más rápido que el enhebrado de subrutina (ver la referencia abajo).

Como ejemplo, una máquina de pila puede ejecutar la secuencia "push A, push B, add". Eso puede ser traducido al enhebrado y rutinas siguientes, donde el tp es inicializado apuntando hacia la dirección de &thread.

thread: pushA: *sp++ = A pushB: *sp++ = B add: *sp++ = *--sp + *--sp &pushA jump *tp++ jump *tp++ jump *tp++ &pushB &add ...

Alternativamente, los operandos pueden estar incluidos en el enhebrado. Esto puede remover alguna indirección necesaria arriba, pero hace el enhebrado más grande:

thread: push: *sp++ = *tp++ add: *sp++ = *--sp + *--sp &push jump *tp++ jump *tp++ &A &push &B &add

Enhebrado indirecto

El enhebrado indirecto usa punteros que apuntan hacia localizaciones que a su vez apuntan al código de máquina. El puntero indirecto puede ser seguido por los operandos que son almacenados en el "bloque" indirecto en vez de estar almacenados repetidamente en el enhebrado. Así, el código indirecto es a menudo más compacto que el código enhebrado directo, pero la indirección típicamente también lo hace más lenta, aunque usualmente todavía más rápida que los intérpretes de bytecode. Donde los operandos del handler incluyen tanto valores como tipos, los ahorros de espacio sobre el código enhebrado directo pueden ser significativos. Los sistemas Forth más antiguos producían típicamente código enhebrado indirecto.

Como ejemplo, si la meta es ejecutar el "push A, push B, add", lo siguiente puede ser usado. Aquí, el tp es inicializado apuntando a la dirección &thread, cada fragmento del código (push, add) es encontrado por doble indirección por medio del tp; y los operandos para cada fragmento de código son encontrados en el primer nivel de indirección siguiendo la dirección del fragmento.

thread: i_pushA: push: add: &i_pushA &push *sp++ = *(*tp + 1) *sp++ = *--sp + *--sp &i_pushB &A jump *(*tp++) jump *(*tp++) &i_add i_pushB: &push &B i_add: &add

Enhebrado de subrutina

El "código enhebrado de subrutina" (también llamado "código enhebrado de llamada") consiste en una serie de instrucciones "call" en lenguaje de máquina (o solo las direcciones de las funciones "call", en oposición el enhebrado directo el cual usa "jump"). Los compiladores tempranos para el ALGOL, FORTRAN, COBOL y algunos sistemas Forth produjeron a menudo código enhebrado de subrutina. El código en muchos de estos sistemas operaba una pila de operandos LIFO (last-in-firs-out), que tenía una bien desarrollada teoría del compilador. La mayoría de los procesadores modernos tienen soporte especial del hardware para las subrutinas con las instrucciones "call" y "return", así que la sobrecarga de una instrucción de máquina adicional por envío es disminuida; pero según mediciones de Antón Ertl, "en contraste con los mitos populares, el enhebrado de subrutina es usualmente más lento que el enhebrado directo". Pruebas más recientes de Ertl demuestran que el enhebrado directo es el modelo de enhebrado más rápido en los procesadores Xeon, Opteron, y Athlon, mientras que el enhebrado indirecto es el modelo de enhebrado más rápido en procesadores Pentium M, y el enhebrado de subrutina es el modelo de enhebrado más rápido en el Pentium 4, el Pentium III, y procesadores PPC.

Como un ejemplo de enhebrado de llamada, el "push A, push B, add":

thread: pushA: pushB: add: call pushA *sp++ = A *sp++ = B *sp++ = *--sp + *--sp call pushB ret ret ret call add

Enhebrado de token