Mesa de sucursales

Es posible que este artículo contenga investigaciones originales . Por favor, mejórelo verificando las afirmaciones realizadas y agregando citas en línea . Las afirmaciones que consten únicamente de investigaciones originales deben eliminarse. ( Noviembre de 2016 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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:

1. Validar opcionalmente los datos de entrada para garantizar que sean aceptables (esto puede ocurrir sin costo como parte del siguiente paso, si la entrada es un solo byte y se utiliza una tabla de traducción de 256 bytes para obtener directamente el desplazamiento que se muestra a continuación). Además, si no hay dudas sobre los valores de la entrada, se puede omitir este paso.
2. Transformar los datos en un desplazamiento hacia la tabla de ramificaciones. Esto generalmente implica multiplicarlos o desplazarlos (multiplicarlos efectivamente por una potencia de 2) para tener en cuenta la longitud de la instrucción. Si se utiliza una tabla de traducción estática, esta multiplicación se puede realizar manualmente o por el compilador, sin ningún costo de tiempo de ejecución.
3. ramificación a una dirección formada por la dirección base de la tabla de ramificaciones más el desplazamiento recién generado. Esto a veces implica una adición del desplazamiento al registro del contador del programa (a menos que, en algunos conjuntos de instrucciones , la instrucción de ramificación permita un registro de índice adicional). Esta dirección final generalmente apunta a una de una secuencia de instrucciones de ramificación incondicional, o a la instrucción inmediatamente posterior a ellas (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 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:

• la arquitectura del procesador en el que se ejecutará el código,
• ya sea un lenguaje compilado o interpretado y
• ya sea que haya enlace tardío o no.

El uso de tablas de ramificaciones y otras codificaciones 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:

• programación embebida
• Desarrollo de sistemas operativos . En muchos sistemas operativos, tanto las llamadas del sistema como las funciones de biblioteca pueden ser referenciadas mediante un índice entero en una tabla de ramificación.
• Algunas arquitecturas informáticas, como IBM/360, utilizan tablas de ramificación para despachar interrupciones.

Las ventajas de las tablas de sucursales incluyen:

• Estructura de código compacta (a pesar de los códigos de operación de ramificación repetidos)
• Declaraciones de fuentes reducidas (en comparación con Ifdeclaraciones repetitivas)
• Requisito reducido para probar los códigos de retorno individualmente (si se utilizan en el sitio de la llamada para determinar el flujo del programa posterior )
• Eficiencia algorítmica y de código (los datos solo necesitan codificarse una vez y el código de la tabla de ramificación suele ser compacto) y potencial para alcanzar altos índices de compresión de datos . Por ejemplo, al comprimir nombres de países a códigos de países, una cadena como "República Centroafricana" se puede comprimir en un solo índice, lo que genera un gran ahorro, en particular cuando la cadena aparece muchas veces. Además, este mismo índice se puede utilizar para acceder a datos relacionados en tablas separadas, lo que reduce aún más los requisitos de almacenamiento.

Para funciones de biblioteca , donde se puede hacer referencia a ellas mediante un número entero :

• Mejorar la compatibilidad con versiones posteriores del software. Si se modifica el código de una función y la dirección de su punto de entrada , solo es necesario ajustar la instrucción de bifurcación en la tabla de bifurcaciones; el software de aplicación compilado para la biblioteca o para el sistema operativo no necesita modificaciones.

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.

• Nivel adicional de indirección , que implica una pérdida de rendimiento generalmente pequeña.
• Restricciones en algunos lenguajes de programación, aunque normalmente existen formas alternativas de implementar el concepto básico de ramificación multidireccional.

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:

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

Se pueden utilizar variaciones en líneas 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.

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

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 .

• Tabla de despacho: una tabla de rama con otro nombre utilizada para enlaces tardíos
• Matrices de punteros de función con direcciones a funciones, tal como se utilizan en tablas de ramas
• Rama indirecta
• Tabla de búsqueda: una matriz de elementos que se deben comparar y que a veces contiene resultados precalculados
• Sentencia Switch: una sentencia condicional de lenguaje de alto nivel que puede generar una tabla de ramas.
• Tabla de métodos virtuales: una tabla de rama con otro nombre con punteros asignados dinámicamente para el despacho (ver tabla de despacho)

Wikimedia Commons tiene medios relacionados con Tabla de ramas .

• [1] Ejemplo de tabla de ramas en Wikilibros para IBM S/360
• [2] Ejemplos y argumentos para tablas de salto a través de matrices de punteros de función en C / C++
• [3] Código de ejemplo generado por la tabla de ramificación 'Switch/Case' en C, versus IF/ELSE.
• [4] Código de ejemplo generado para indexar una matriz si el tamaño de la estructura es divisible por potencias de 2 o de otro modo.
• [5] "Matrices de punteros a funciones" de Nigel Jones