Tabla de ramificación

Una tabla de ramificación consiste en una lista serial de instrucciones de ramificación incondicionales a la que se accede mediante un desplazamiento creado al multiplicar un índice secuencial por la longitud de la instrucción (el número de bytes en memoria que ocupa cada instrucción de ramificación). Se basa en el hecho de que las instrucciones de código máquina para ramificación tienen una longitud fija y pueden ser ejecutadas de forma extremadamente eficiente por la mayoría del hardware, y resulta especialmente útil al trabajar con valores de datos sin procesar que pueden convertirse fácilmente en valores de índice secuencial . Con este tipo de datos, una tabla de ramificación puede ser extremadamente eficiente. Generalmente consta de los siguientes tres pasos:

1. Opcionalmente , se puede validar el dato de entrada para asegurar que sea aceptable. Asimismo, si no hay dudas sobre los valores de entrada, este paso puede omitirse.
2. Transformar el dato en un desplazamiento dentro de la tabla de bifurcaciones. Esto generalmente implica multiplicarlo o desplazarlo (es decir, multiplicarlo por una potencia de 2) para tener en cuenta la longitud de la instrucción. Si los datos son constantes, esta multiplicación puede realizarse manualmente o mediante el compilador, sin ningún costo en tiempo de ejecución.
3. La instrucción de salto apunta a una dirección compuesta por la dirección base de la tabla de saltos más el desplazamiento generado. Esto a veces implica añadir el desplazamiento al registro del contador de programa (a menos que, en algunos conjuntos de instrucciones , la instrucción de salto permita un registro de índice adicional ). Esta dirección final suele apuntar a una de las instrucciones de salto incondicional o a la instrucción inmediatamente posterior (ahorrando una entrada en la tabla).

El siguiente pseudocódigo ilustra el concepto:

... validar x /* transformar x a 0 (inválido) o 1,2,3, según el valor..) */ y = x * 4 ; /* multiplicar por la longitud de la instrucción de salto (por ejemplo, 4 ) */ ir a next + y ; /* saltar a la 'tabla' de instrucciones de salto */ /* inicio de la tabla de saltos */ next : ir a codebad ; /* x= 0 (inválido) */ ir a codeone ; /* x= 1 */ ir a codetwo ; /* x= 2 */ ... resto de la tabla de saltos codebad : /* manejar la entrada inválida */

Otro método para implementar una tabla de bifurcaciones consiste en utilizar un array de punteros desde el cual se obtiene la dirección de la función requerida. Originalmente conocido como vector de transferencia , este método también se conoce más recientemente con nombres como " tabla de despacho " o " tabla de métodos virtuales ", pero esencialmente cumple la misma función. Este método de función de puntero puede ahorrar una instrucción de máquina y evita el salto indirecto (a una de las instrucciones de bifurcación).

La lista resultante de punteros a funciones es casi idéntica al código de subprocesos directos y es conceptualmente similar a una tabla de control .

El método real utilizado para implementar una tabla de ramificación generalmente se basa en:

• la arquitectura del procesador en el que se va a ejecutar el código,
• ya sea un lenguaje compilado o interpretado y
• independientemente de si interviene o no la vinculación tardía .

Los programadores suelen dejar la decisión de crear o no una tabla de ramificación al compilador, creyendo que este es perfectamente capaz de elegir correctamente entre las claves de búsqueda conocidas. Esto puede ser cierto para los compiladores optimizadores en casos relativamente sencillos donde el rango de claves de búsqueda es limitado. Sin embargo, los compiladores no son tan inteligentes como los humanos y no pueden tener un conocimiento profundo del "contexto", creyendo que un rango de posibles valores enteros para las claves de búsqueda, como 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 y 1000, generaría una tabla de ramificación con un número excesivamente grande de entradas vacías (más de 900) con muy poca ventaja. Un buen compilador optimizador podría entonces preordenar los valores y generar código para una búsqueda binaria por corte , como una "segunda mejor" opción. De hecho, la aplicación puede ser muy "crítica en tiempo" y el requisito de memoria puede no ser realmente un problema en absoluto. ^{[ 2 ]}

Sin embargo, un poco de "sentido común" puede transformar este caso en particular, y muchos otros casos similares, en un proceso simple de dos pasos con un gran potencial de ahorro, dejando finalmente la decisión final en manos del compilador, pero "ayudándolo" considerablemente en su decisión:

• Primero, compruebe la clave de búsqueda = 1000 y ejecute la bifurcación correspondiente.
• Permitir que el compilador "elija" generar una tabla de ramificación en las claves de búsqueda restantes (1-50).

Se pueden utilizar variaciones similares en casos donde existan dos conjuntos de rangos cortos con una gran diferencia entre ellos.

Cuando no hay un valor entero obvio disponible para una tabla de ramificación, se puede crear a partir de una clave de búsqueda (o parte de una clave de búsqueda) mediante algún tipo de transformación aritmética, o simplemente podría ser el número de fila de una base de datos o el número de entrada en una matriz que contiene la clave de búsqueda encontrada durante una validación anterior de la clave.

En algunos casos, puede ser necesario utilizar una tabla hash para generar el índice. Sin embargo, para valores de entrada de un solo byte, como AZ (o el primer byte de una clave más larga), el contenido del byte en sí ( datos sin procesar ) puede utilizarse en un proceso de dos pasos, denominado " función hash trivial ", para obtener un índice final para una tabla de ramificación sin huecos.

1. Convierta el carácter de datos sin procesar a su equivalente numérico (ejemplo: ASCII 'A' ==> 65 decimal, 0x41 hexadecimal).
2. Utilice el valor numérico entero como índice en una matriz de 256 entradas de 2 bytes para obtener un segundo índice (las entradas no válidas son 0, que representan huecos; de lo contrario, son 1, 2, 3, etc.).

El array no debería ser mayor de (256 × 2) bytes para almacenar enteros sin signo (cortos) de 16 bits para todos los posibles bytes de 8 bits. Si no se requiere validación y solo se utilizan mayúsculas, el tamaño del array puede ser tan pequeño como (26 × 2) = 52 bytes.

Aunque la técnica de ramificación mediante una tabla de ramificación se utiliza con mayor frecuencia únicamente para modificar el flujo del programa  (para saltar a una etiqueta de programa que corresponde a una ramificación incondicional  ), la misma técnica puede emplearse para otros fines. Por ejemplo, puede utilizarse para seleccionar un punto de inicio en una secuencia de instrucciones repetidas donde la omisión de instrucciones es la norma y es intencional. Esto puede ser útil, por ejemplo, para los compiladores optimizadores o los compiladores JIT en el desenrollado de bucles .

Un ejemplo sencillo del uso de tablas de ramificación en el lenguaje ensamblador del microcontrolador PIC de 8 bits es:

movf ÍNDICE , W ; Mueve el valor del índice al registro W (de trabajo) desde la memoria addwf PCL , F ; lo suma al contador de programa. Suponga que la instrucción PIC es una ; palabra de instrucción, por lo que no es necesario realizar ninguna multiplicación. ; La mayoría de las arquitecturas transformarán el índice de alguna manera antes de ; agregarlo al contador de programa.tabla ; La tabla de bifurcaciones comienza aquí con esta etiqueta goto index_zero ; cada una de estas instrucciones goto es una bifurcación incondicional goto index_one ; de código. goto index_two goto index_threeindex_zero ; Aquí se agrega código para realizar la acción necesaria cuando INDEX = cero .índice_uno ...

Nota: este código solo funcionará si PCL < (tabla + índice_último). Para garantizar esta condición, podemos usar la directiva "org". Si GOTO consta de dos palabras de instrucción (PIC18F, por ejemplo), esto limita el número de entradas de la tabla a menos de 128. Los bits superiores a PCL los proporciona la parte correspondiente de PCLATH.

Otro ejemplo sencillo, que muestra una tabla de saltos en lugar de una simple tabla de bifurcaciones. Esto permite llamar a bloques de programa fuera del procedimiento/función actualmente activo:

#include <stdio.h> #include <stdlib.h>typedef void ( * Handler )( void ); /* Un puntero a una función manejadora *//* Las funciones */ void func3 ( void ) { printf ( "3 \n " ); } void func2 ( void ) { printf ( "2 \n " ); } void func1 ( void ) { printf ( "1 \n " ); } void func0 ( void ) { printf ( "0 \n " ); }Tabla de saltos del manejador [ 4 ] = { func0 , func1 , func2 , func3 };int main ( int argc , char ** argv ) { int value ;/* Convierte el primer argumento a un entero de 0 a 3 (módulo) */ valor = atoi ( argv [ 1 ]) % 4 ;/* Llamar a la función apropiada (func0 a func3) */ jump_table [ valor ]();devolver 0 ; }

PL/I implementa una tabla de saltos como una matriz de variables de etiqueta . Estas pueden inicializarse de forma inusual mediante una etiqueta de instrucción indexada. Las variables de etiqueta de PL/I no son simplemente la dirección de la instrucción, sino que suelen contener información adicional sobre el estado del bloque de código al que pertenecen. Sin esta inicialización inusual, esto también podría codificarse con llamadas y una matriz de variables de entrada.

 declarar etiqueta de laboratorio (10); declarar x binario fijo; ir a laboratorio(x); lab(1): /* código para la opción 1 */ ; ... lab(2): /* código para la opción 2 */ ; ...