Código enhebrado

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.^[1] 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.^[2]

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". [3] 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

El código enhebrado de token usa listas de índices de 8 o 12 bits a una tabla de punteros. El código enhebrado de token es notablemente compacto, sin mucho esfuerzo especial por un programador. Tiene usualmente entre la mitad y tres cuartas partes el tamaño de otros códigos enhebrados, los cuales a su vez tienen entre la cuarta y la octava parte del tamaño del código compilado. Los punteros de la tabla pueden ser tanto indirectos como directos. Algunos compiladores Forth producen código enhebrado de token. Algunos programadores consideran al "p-code" generado por algunos compiladores de Pascal, al igual que los bytecodes usados por .NET, Java, BASIC, y algunos compiladores C, como enhebrado de token.

Históricamente, un acercamiento común es el bytecode, que utiliza opcodes de 8 bits y, a menudo, una máquina virtual basada en pila. Un interpretador típico es conocido como "decode and dispatch interpreter" y sigue la forma:

bytecode:         top:                   pushA:         pushB:          add:
  0 /*pushA*/       i = decode(vpc++)      *sp++ = A      *sp++ = B       *sp++ = *--sp + *--sp
  1 /*pushB*/       addr = table[i]        jump top       jump top        jump top
  2 /*add*/         jump *addr

Si la máquina virtual usa solamente instrucciones del tamaño de un byte, el decode() es simplemente un ferch desde el bytecode, pero a menudo hay instrucciones comunes de 1 byte más instrucciones menos comunes de múltiples bytes (ver CISC), en este caso, decode() es más complejo. La decodificación de opcodes de un solo byte puede ser muy simple y eficientemente manejado por una tabla de saltos usando el opcode directamente como un índice.

Para, en las instrucciones donde las operaciones individuales son simples, por ejemplo "push" y "add", la sobrecarga implicada en decidir lo que se debe ejecutar es más grande que el costo real de la ejecución, tales intérpretes son a menudo mucho más lentos que el código de máquina. Sin embargo para instrucciones ("compuestas") más complejas, el porcentaje de sobrecarga es proporcionalmente menos significativo. ^[3]

Enhebrado de Huffman

El código enhebrado de Huffman consiste en listas de códigos Huffman. Un código de Huffman es una cadena de bits de longitud variable usada para identificar un elemento único. Un intérprete de enhebrado de Huffman localiza las subrutinas usando una tabla de índice o un árbol de punteros que pueden ser navagados por el código Huffman. El código enhebrado de Huffman es una de las más compactas representaciones conocidas para un programa de computadora. Básicamente el índice y los códigos están organizados midiendo la frecuencia en que cada subrutina ocurre en el código. A las llamadas frecuentes se le dan los códigos más cortos. Las operaciones con frecuencias aproximadamente iguales se le dan códigos con longitudes de bits casi iguales. La mayoría de los sistemas enhebrados de Huffman han sido implementados como sistemas Forth de enhebrado directo, y son usados para grandes cantidades de paquetes de código corriendo lentamente dentro de pequeños y baratos microcontroladores. La mayoría de las aplicaciones publicadas han estado en juguetes, calculadoras o relojes.

Enhebrados menos usados

Enhebrado de cadena, donde las operaciones son identificadas por cadenas, usualmente buscados en una tabla hash. Esto fue usado por Charles H. Moore en las implementaciones más tempranas de Forth y en el lenguaje de computadora experimental interpretado por hardware de la Universidad Illinois. También se utiliza en Bashforth.

Bifurcaciones

Los ejemplos de arriba no muestran bifurcaciones. Para todos los intérpretes, una bifurcación cambia el puntero del enhebrado (arriba indicado como tp). Como ejemplo, una bifurcación condicional cuando el valor tope de la pila es cero puede ser codificada como sigue. Observe que el &thread[123] es la localización a saltar (jump), no la dirección de un handler, y así que debe ser saltada (tp++) independientemente de si la bifurcación es tomada.

thread:              brz:
  ...                  tmp = *tp++
  &brz                 if (*sp++ == 0)
  &thread[123]           tp = tmp
  ...                  jump *tp++

Amenidades comunes

En una máquina, la separación de las pilas de datos y de retorno elimina mucho del código para el manejo de la pila, reduciendo substancialmente el tamaño del código enhebrado. El principio de la doble pila fue originado tres veces independientemente: para los grandes sistemas de Burroughs, el Forth y el PostScript, y es usado en algunas máquinas virtuales de Java.

Tres registros están a menudo presentes en una máquina virtual enhebrada. Otro existe para pasar datos entre las subrutinas ("palabras"). Estos son:

IP o i (puntero de instrucción); llamado tp en los ejemplos de arriba
w (puntero de trabajo)
rp o r (puntero de pila de retorno)
SP o s (puntero de pila de parámetros, usado para pasar parámetros entre las palabras)

A menudo, las máquinas virtuales enhebradas tales como las implementaciones de Forth tienen una máquina virtual simple en su corazón, consistiendo en tres primitivas. Esas son:

nest, también llamado docol
unnest, o semi_s (; s)
next

En una máquina virtual de enhebrado indirecto, la que está dada aquí, las operaciones es:

next:   (ip)+ ->   w    ;  jmp (w)+
nest:    ip   -> -(rp)  ;  w -> ip  ;  next
unnest: (rp)+ ->   ip   ;  next

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

Referencias

↑ Speed of various interpreter dispatch techniques V2
↑ James R. Bell, "Threaded Code", CACM, 1973, 16, 6, pp 370–372
↑ Enciclopedia detallada de todos los tipos de códigos DTC

Lectura adicional

Anton Ertl's explanatory page What is Threaded Code? describes different threading techniques and provides further references.
The Development of the C Language Archivado el 28 de marzo de 2015 en Wayback Machine. by Dennis M. Ritchie describes B (a precursor of C) as implemented using "threaded code".
Thinking Forth Project includes the seminal (but out of print) book Thinking Forth by Leo Brodie published in 1984.
Starting FORTH online version of the book Starting FORTH by Leo Brodie published in 1981.
Brad Rodriguez's Moving FORTH: Part 1: Design Decisions in the Forth Kernel covers threading techniques in depth.
Historia de los CPU de propósito general
GCC extensions. Labels as Values

Véase también

Datos: Q2491860

[1] Speed of various interpreter dispatch techniques V2

[2] James R. Bell, "Threaded Code", CACM, 1973, 16, 6, pp 370–372

[3] Enciclopedia detallada de todos los tipos de códigos DTC

[1]

[2]

[3]