En programación informática , una tabla de ramificación o tabla de salto es un método para transferir el control del programa ( ramificación ) a otra parte de un programa (o a un programa diferente que puede haberse cargado dinámicamente) utilizando una tabla de instrucciones de ramificación o salto . Es una forma de ramificación multidireccional . La construcción de la tabla de ramificación se utiliza comúnmente cuando se programa en lenguaje ensamblador , pero también puede ser generada por compiladores , especialmente cuando se implementan sentencias switch optimizadas cuyos valores están densamente empaquetados. [1]
Una tabla de ramificación consiste en una lista en serie de instrucciones de ramificación incondicionales que se ramifican utilizando un desplazamiento creado al multiplicar un índice secuencial por la longitud de la instrucción (la cantidad de bytes en la memoria que ocupa cada instrucción de ramificación). Se basa en el hecho de que las instrucciones de código de máquina para la ramificación tienen una longitud fija y pueden ser ejecutadas de manera extremadamente eficiente por la mayoría del hardware, y es más útil cuando se trabaja con valores de datos sin procesar que pueden convertirse fácilmente en valores de índice secuencial . Dados dichos datos, una tabla de ramificación puede ser extremadamente eficiente. Por lo general, consta de los siguientes 3 pasos:
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 bifurcación (p. ej. 4 ) */ goto next + y ; /* bifurcar a 'tabla' de instrucciones de bifurcación */ /* inicio de la tabla de bifurcaciones */ next : goto codebad ; /* x= 0 (inválido) */ goto codeone ; /* x= 1 */ goto codetwo ; /* x= 2 */ ... resto de la tabla de bifurcaciones codebad : /* tratar con entrada inválida */ Otro método para implementar una tabla de ramificaciones es con una matriz de punteros de la que se recupera 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 diferentes como " tabla de despacho " o " tabla de métodos virtuales ", pero esencialmente realiza exactamente el mismo propósito. Este método de función de puntero puede resultar en el ahorro de una instrucción de máquina y evita el salto indirecto (a una de las instrucciones de ramificación).
La lista resultante de punteros a funciones es casi idéntica al código enhebrado directo y es conceptualmente similar a una tabla de control .
El método real utilizado para implementar una tabla de rama generalmente se basa en:
El uso de tablas de ramificaciones y otros tipos de codificación de datos sin procesar era común en los primeros tiempos de la informática, cuando la memoria era cara, las CPU eran más lentas y la representación compacta de los datos y la elección eficiente de alternativas eran importantes. Hoy en día, todavía se utilizan comúnmente en:
Las ventajas de las tablas de sucursales incluyen:
Ifdeclaraciones repetitivas)Para funciones de biblioteca , donde se puede hacer referencia a ellas mediante un número entero :
Además, llamar funciones por número (el índice de la tabla) a veces puede ser útil en algunos casos en la programación de aplicaciones normales.
Un ejemplo simple del uso de la tabla de ramas en el lenguaje ensamblador PIC de 8 bits de Microchip es:
movf INDEX , W ; Mueve el valor del índice al registro W (de trabajo) desde la memoria addwf PCL , F ; añádelo al contador del programa. Cada instrucción PIC es un byte ; 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 ; añadirlo al contador del programa. tabla ; La tabla de ramificaciones comienza aquí con esta etiqueta goto index_zero ; cada una de estas instrucciones goto es una ramificación incondicional goto index_one ; de código. goto index_two goto index_three index_zero ; Aquí se agrega código para realizar cualquier acción que se requiera cuando INDEX = retorno cero índice_uno ... Nota: este código funcionará únicamente si PCL < (table + index_last). Para garantizar esta condición, podemos utilizar una directiva "org". Y si GOTO (PIC18F, por ejemplo) tiene 2 bytes, esto limita la cantidad de entradas de la tabla a menos de 128.
Otro ejemplo simple, que esta vez muestra una tabla de saltos en lugar de una simple tabla de ramificaciones. Esto permite llamar a bloques de programa fuera del procedimiento o función actualmente activo:
#include <stdio.h> #include <stdlib.h> typedef void ( * Handler )( void ); /* Un puntero a una función de controlador */ /* 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 " ); } Controlador jump_table [ 4 ] = { func0 , func1 , func2 , func3 }; int main ( int argc , char ** argv ) { int valor ; /* Convertir el primer argumento a un entero 0-3 (módulo) */ valor = atoi ( argv [ 1 ]) % 4 ; /* Llamar a la función apropiada (func0 a func3) */ jump_table [ valor ](); devuelve 0 ; } PL/I implementa una tabla de saltos como una matriz de variables de etiqueta . Estas pueden inicializarse de una manera inusual mediante el uso de una etiqueta de declaración con subíndice. Las variables de etiqueta de PL/I no son simplemente la dirección de la declaración, sino que generalmente contienen información adicional sobre el estado del bloque de código al que pertenecen. Sin la 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 al laboratorio (x); lab(1): /* código para la elección 1 */ ; ... lab(2): /* código para la opción 2 */ ; ...
Los programadores suelen dejar la decisión de crear o no una tabla de ramificaciones al compilador, creyendo que es perfectamente capaz de hacer la elección correcta a partir de las claves de búsqueda conocidas. Esto puede ser cierto para optimizar compiladores para casos relativamente simples 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 de claves de búsqueda como 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 y 1000 generaría una tabla de ramificaciones con una cantidad excesivamente grande de entradas vacías (900+) para muy poca ventaja. Un buen compilador optimizador puede entonces preordenar los valores y generar código para una búsqueda binaria , como una "segunda mejor" opción. De hecho, la aplicación puede ser altamente "crítica en cuanto al 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 particular, y muchos otros casos similares, en un simple proceso de dos pasos con un potencial de ahorro muy grande, aunque al final todavía deja la elección final al compilador, pero "ayudando a su decisión" considerablemente:
Se pueden utilizar variaciones similares en casos en los que hay dos conjuntos de rangos cortos con una gran brecha entre ellos.
Si bien la técnica ahora se conoce como "tablas de ramificación", los primeros usuarios de compiladores llamaron a la implementación " GoTo computado ", en referencia a la instrucción que se encuentra en la serie de compiladores Fortran. [3] [4] La instrucción finalmente quedó obsoleta en Fortran 90 (a favor de las declaraciones SELECT y CASE en el nivel de origen). [5]
Cuando no hay un valor entero obvio disponible para una tabla de rama, se puede crear de todos modos a partir de una clave de búsqueda (o parte de una clave de búsqueda) mediante alguna forma de transformación aritmética, o podría ser simplemente 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 necesaria una tabla hash para formar 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 ) se puede utilizar en un proceso de dos pasos, de " función hash trivial ", para obtener un índice final para una tabla de ramificación con cero espacios vacíos.
La matriz no debería tener más de (256 × 2) bytes para contener enteros sin signo (cortos) de 16 bits para todos los bytes de 8 bits posibles. Si no se requiere validación y solo se utilizan mayúsculas, el tamaño de la matriz puede ser tan pequeño como (26 × 2) = 52 bytes.
Aunque la técnica de ramificación mediante una tabla de ramificaciones se utiliza con mayor frecuencia únicamente con el propósito de alterar el flujo del programa (para saltar a una etiqueta de programa que es una ramificación incondicional), la misma técnica se puede utilizar para otros fines. Por ejemplo, se puede utilizar para seleccionar un punto de inicio en una secuencia de instrucciones repetidas donde la eliminación es la norma y es intencional. Esto se puede utilizar, por ejemplo, optimizando compiladores o compiladores JIT en el desenrollado de bucles .
