En programación de computadoras , una tabla de bifurcación o tabla de salto es un método para transferir el control de un programa ( bifurcación ) a otra parte de un programa (o a un programa diferente que puede haber sido cargado dinámicamente) usando una tabla de instrucciones de bifurcación o salto . Es una forma de sucursal de múltiples vías . La construcción de la tabla de ramas se usa comúnmente cuando se programa en lenguaje ensamblador , pero también puede ser generada por compiladores , especialmente cuando se implementan declaraciones de cambio optimizadas cuyos valores están densamente empaquetados. [1]
Una tabla de bifurcación consta de una lista en serie de instrucciones de bifurcación incondicionales que se bifurcan utilizando un desplazamiento creado multiplicando un índice secuencial por la longitud de la instrucción (el número de bytes en la memoria ocupados por cada instrucción de bifurcación). Se basa en el hecho de que las instrucciones de código de máquina para bifurcaciones 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 trata de valores de datos sin procesar que pueden convertirse fácilmente en valores de índice secuenciales . Con tales datos, una tabla de sucursales puede ser extremadamente eficiente. Generalmente consta de los siguientes 3 pasos:
El siguiente pseudocódigo ilustra el concepto.
... validar x /* transformar x a 0 (no válido) o 1,2,3, según valor..) */ y = x * 4 ; /* multiplicar por la longitud de la instrucción de bifurcación (por ejemplo, 4) */ goto next + y ; /* bifurcar a la 'tabla' de instrucciones de bifurcación */ /* inicio de la tabla de bifurcaciones */ next : goto codebad ; /* x= 0 (no válido) */ ir a codeone ; /* x= 1 */ ir a código dos ; /* x= 2 */ ... resto de la tabla de rama codebad : /* tratar con entrada no válida */ Otro método para implementar una tabla de rama es con una matriz de punteros desde los cuales 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 tan 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 dar como resultado guardar una instrucción de máquina y evita el salto indirecto (a una de las instrucciones de rama).
La lista resultante de punteros a funciones es casi idéntica al código de subproceso directo y es conceptualmente similar a una tabla de control .
El método real utilizado para implementar una tabla de sucursales generalmente se basa en:
El uso de tablas de rama y otras codificaciones de datos sin procesar era común en los primeros días de la informática, cuando la memoria era costosa, 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 se siguen utilizando habitualmente 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 en la tabla) a veces puede resultar útil en algunos casos en la programación de aplicaciones normales.
Un ejemplo sencillo del uso de una tabla de ramas en el lenguaje ensamblador PIC de Microchip de 8 bits es:
movfÍNDICE , W ; Mueva el valor del índice al registro W (de trabajo) desde la memoria addwf PCL , F ; agréguelo al contador del programa. Cada instrucción PIC es de 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 ; agregándolo al contador del programa. mesa ; La tabla de ramas comienza aquí con esta etiqueta goto index_zero ; cada una de estas instrucciones goto es una rama incondicional goto index_one ; de código. ir a index_two ir a index_tres índice_cero ; Aquí se agrega código para realizar cualquier acción necesaria cuando ÍNDICE = retorno cero índice_uno ... Nota: este código funcionará solo si PCL < (tabla + índice_último). Para garantizar esta condición podemos utilizar una directiva "org". Y si GOTO (PIC18F por ejemplo) tiene 2 bytes, esto limita el número de entradas de la tabla a menos de 128.
Otro ejemplo simple, esta vez que muestra una tabla de salto en lugar de una simple tabla de rama. Esto permite llamar a bloques de programa fuera del procedimiento/función actualmente activo:
#incluir <stdio.h> #incluir <stdlib.h> typedef vacío ( * controlador ) ( vacío ); /* Un puntero a una función de controlador */ /* Las funciones */ void func3 ( void ) { printf ( "3 \n " ); } función vacía2 ( vacío ) { printf ( "2 \n " ); } función vacía1 ( vacío ) { printf ( "1 \n " ); } función vacía0 ( vacío ) { printf ( "0 \n " ); } Controlador jump_table [ 4 ] = { func0 , func1 , func2 , func3 }; int principal ( 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 ](); devolver 0 ; } PL/I implementa una tabla de salto como una matriz de variables de etiqueta . Estos pueden inicializarse de una manera inusual mediante el uso de una etiqueta de declaración con subíndice. Las variables de etiqueta PL/I no son simplemente la dirección de la declaración, sino que normalmente 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 serie de variables de entrada.
declarar etiqueta de laboratorio (10); declarar x binario fijo; ir al laboratorio(x); lab(1): /* código para la opción 1 */ ; ... lab(2): /* código para la opción 2 */ ; ...
Los programadores frecuentemente dejan la decisión de crear o no una tabla de rama en manos del compilador, creyendo que es perfectamente capaz de tomar la decisión correcta a partir de las claves de búsqueda conocidas. Esto puede ser cierto para optimizar compiladores en 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", ya que creen que existe 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ían una tabla de ramas con una cantidad excesivamente grande de entradas vacías (900+) para obtener muy poca ventaja. Un buen compilador de optimización puede ordenar previamente los valores y generar código para una búsqueda binaria , como una "segunda mejor" opción. De hecho, la aplicación puede ser muy "crítica en términos de tiempo" y los requisitos de memoria pueden no ser 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 proceso simple de dos pasos con un potencial de ahorro muy grande, y al mismo tiempo dejar finalmente la elección final al compilador, pero "ayudando a su decisión". importantemente:
Se pueden utilizar variaciones en líneas similares en los casos en que hay dos conjuntos de rangos cortos con una gran brecha entre ellos.
Si bien la técnica ahora se conoce como "tablas de ramas", los primeros usuarios del compilador llamaron a la implementación " GoTo calculado ", en referencia a las instrucciones que se encuentran en la serie de compiladores Fortran. [3] [4] La instrucción finalmente quedó obsoleta en Fortran 90 (a favor de las declaraciones SELECT & CASE en el nivel fuente). [5]
Cuando no hay un valor entero obvio disponible para una tabla de rama, se puede crear 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 la validación anterior de la clave.
En algunos casos, es posible que se requiera 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, " función hash trivial ", para obtener una índice final para una tabla de sucursales con cero espacios.
La matriz no tendría más de (256 x 2) bytes, para contener todos los enteros (cortos) sin signo posibles de 16 bits. 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 x 2) = 52 bytes.
Aunque la técnica de bifurcar utilizando una tabla de bifurcaciones se utiliza con mayor frecuencia únicamente con el fin de alterar el flujo del programa (para saltar a una etiqueta de programa que es una bifurcación incondicional), la misma técnica se puede utilizar para otros fines. Por ejemplo, se puede utilizar para seleccionar un punto de partida en una secuencia de instrucciones repetidas donde el abandono es la norma y es intencional. Esto se puede utilizar, por ejemplo, optimizando compiladores o compiladores JIT en el desarrollo de bucles .
