En programación de computadoras , una tabla de rama o tabla de salto es un método para transferir el control de programa ( ramificación ) a otra parte de un programa (o un programa diferente que puede haber sido cargado dinámicamente) usando una tabla de rama o instrucciones de salto . Es una forma de rama 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 conmutación optimizadas cuyos valores están densamente empaquetados. [1]
Implementación típica
Una tabla de bifurcaciones consta de una lista en serie de instrucciones de bifurcación incondicionales que se bifurcan utilizando un desplazamiento creado al multiplicar 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 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 trata de valores de datos sin procesar que pueden convertirse fácilmente en valores de índice secuenciales . Dados estos datos, una tabla de ramas puede ser extremadamente eficiente. Por lo general, consta de los siguientes 3 pasos:
- 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 de un solo byte y se usa una tabla de traducción de 256 bytes para obtener directamente el desplazamiento a continuación). Además, si no hay duda sobre los valores de la entrada, este paso se puede omitir.
- transformar los datos en un desplazamiento en la tabla de ramas. Esto generalmente implica multiplicarlo o cambiarlo (multiplicarlo efectivamente por una potencia de 2) para tener en cuenta la longitud de la instrucción. Si se usa 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.
- bifurcando a una dirección formada por la dirección base de la tabla de bifurcaciones 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 bifurcación permita un registro de índice adicional). Esta dirección final generalmente apunta a una de una secuencia de instrucciones de bifurcación incondicionales, o la instrucción inmediatamente posterior a ellas (guardando una entrada en la tabla).
El siguiente pseudocódigo ilustra el concepto
... validar x / * transformar x en 0 (inválido) o 1,2,3, según valor ..) * / y = x * 4 ; / * multiplicar por la longitud de la instrucción de rama (por ejemplo, 4) * / ir a siguiente + y ; / * bifurca en 'tabla' de instrucciones de bifurcación * / / * inicio de tabla de bifurcación * / siguiente : goto codebad ; / * x = 0 (inválido) * / ir a codeone ; / * x = 1 * / ir a codetwo ; / * x = 2 * / ... resto de la tabla de rama codebad : / * tratar con entrada inválida * /
Implementación alternativa usando direcciones
Otro método para implementar una tabla de bifurcaciones es con una matriz de punteros de la que se recupera la dirección de la función requerida . Este método también se conoce más recientemente con nombres tan diferentes como " tabla de despacho " o " tabla de método virtual ", pero esencialmente realiza exactamente el mismo propósito. Este método de función de puntero puede resultar en guardar 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 subprocesamiento directo y es conceptualmente similar a una tabla de control .
El método real utilizado para implementar una tabla de ramas generalmente se basa en:
- la arquitectura del procesador en el que se va a ejecutar el código,
- si es un lenguaje compilado o interpretado y
- si la vinculación tardía está involucrada o no.
Historia
El uso de tablas de ramas y otra codificación de datos sin procesar era común en los primeros días de la informática, cuando la memoria era cara, las CPU eran más lentas y la representación de datos compacta y la elección eficiente de alternativas eran importantes. Hoy en día, todavía se utilizan comúnmente en:
- programación embebida
- desarrollo del sistema operativo . En muchos sistemas operativos, tanto las llamadas al sistema como las funciones de biblioteca pueden ser referenciadas por un índice entero en una tabla de ramas.
- Algunas arquitecturas informáticas , como IBM / 360, utilizan tablas de ramas para distribuir interrupciones.
Ventajas
Las ventajas de las tablas de sucursales incluyen:
- estructura de código compacto (a pesar de códigos de operación de rama repetidos)
- declaraciones de fuentes reducidas (versus
If
declaraciones repetitivas ) - requisito reducido para probar los códigos de retorno individualmente (si se usa 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 bifurcaciones suele ser compacto) y el potencial para alcanzar altas tasas de compresión de datos . Por ejemplo, al comprimir nombres de países en códigos de países, una cadena como "República Centroafricana" se puede comprimir en un solo índice, lo que genera grandes ahorros, especialmente cuando la cadena aparece muchas veces. Además, este mismo índice se puede utilizar para acceder a datos relacionados en tablas independientes, lo que reduce aún más los requisitos de almacenamiento.
Para funciones de biblioteca , donde pueden ser referenciadas por un número entero :
- mejorar la compatibilidad con versiones de software posteriores. Si se cambia 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 contra la biblioteca o para el sistema operativo no necesita modificación.
Además, llamar a funciones por número (el índice en la tabla) a veces puede ser útil en algunos casos en la programación de aplicaciones normal.
Desventajas
- Nivel adicional de direccionamiento indirecto , que suele generar un pequeño impacto en el rendimiento.
- Restricciones en algunos lenguajes de programación, aunque suele haber formas alternativas de implementar el concepto básico de ramificación de múltiples vías.
Ejemplo
Un ejemplo simple del uso de la tabla de ramas en el lenguaje ensamblador de Microchip PIC de 8 bits es:
movf INDEX , W ; Mueva el valor del índice al registro W (de trabajo) de 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 bifurcaciones 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_three index_zero ; El código se agrega aquí para realizar cualquier acción que se requiera cuando INDICE = retorno cero index_one ...
Nota: este código solo funcionará 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 el número de entradas de la tabla a menos de 128.
Ejemplo de tabla de salto en C
Otro ejemplo simple, esta vez demostrando una mesa de salto en lugar de una mera mesa de rama. Esto permite llamar a bloques de programa fuera del procedimiento / función actualmente activo:
#include #include 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 " ); }Handler jump_table [ 4 ] = { func0 , func1 , func2 , func3 };int main ( int argc , char ** argv ) { int valor ; / * Convertir el primer argumento a entero 0-3 (módulo) * / valor = atoi ( argv [ 1 ]) % 4 ; / * Llamar a la función apropiada (func0 a func3) * / jump_table [ valor ] (); return 0 ; }
Ejemplo de tabla de salto en PL / I
PL / I implementa una tabla de salto como una matriz de variables de etiqueta . Estos pueden inicializarse de una manera inusual utilizando una etiqueta de instrucción con subíndice. Las variables de etiqueta 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 opción 1 * /; ... lab (2): / * código para la opción 2 * /; ...
Tablas de ramas generadas por el compilador
Los programadores con frecuencia dejan la decisión de crear o no una tabla de bifurcaciones 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 la optimización de 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', ya que creen que un rango de posibles valores enteros clave de búsqueda como 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 y 1000 generarían una tabla de sucursales con una cantidad excesivamente grande de entradas vacías (900+) con muy poca ventaja. Un buen compilador optimizador puede entonces clasificar previamente los valores y generar código para una búsqueda de corte binario , como una "segunda mejor opción". De hecho, la aplicación puede ser muy "crítica en cuanto al 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 en particular, y muchos otros casos similares, en un proceso simple de dos pasos con ahorros potenciales muy grandes, mientras que finalmente deja la elección final al compilador, pero 'ayudando en su decisión'. importantemente:
- Primero, pruebe la clave de búsqueda = 1000 y realice la bifurcación adecuada.
- Permita que el compilador 'elija' para generar una tabla de bifurcaciones en las claves de búsqueda restantes (1-50).
Se pueden usar variaciones a lo largo de líneas similares en los casos en que hay dos conjuntos de rangos cortos con una gran brecha entre rangos.
GoTo calculado
Si bien la técnica ahora se conoce como 'tablas de ramas', los primeros usuarios del compilador llamaron a la implementación ' GoTo calculado ', refiriéndose 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 & CASE en el nivel de fuente). [5]
Creando el índice para la tabla de ramas
Cuando no hay un valor entero obvio disponible para una tabla de rama, no obstante, 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.
Es posible que se requiera una tabla hash para formar el índice en algunos casos. 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 propio byte ( datos sin procesar ) se puede utilizar en un proceso de dos pasos, " función hash trivial ", para obtener un índice final para una tabla de rama con cero espacios.
- Convierta el carácter de datos sin procesar en su equivalente numérico (ejemplo ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
- Utilice el valor entero numérico como índice en una matriz de 256 bytes para obtener un segundo índice (entradas no válidas 0; representando espacios, de lo contrario 1, 2, 3, etc.)
La matriz no tendría más de (256 x 2) bytes, para contener todos los números enteros (cortos) sin signo de 16 bits posibles. Si no se requiere validación y solo se usan mayúsculas, el tamaño de la matriz puede ser tan pequeño como (26 x 2) = 52 bytes.
Otros usos de la técnica
Aunque la técnica de bifurcación mediante 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 pasar por alto es la norma y es intencional. Esto se puede utilizar, por ejemplo, optimizando compiladores o compiladores JIT en el desenrollado de bucles .
Ver también
- Despachar tabla una tabla de rama por otro nombre usado para enlace tardío
- Matrices de puntero de función de direcciones a funciones como se usa en tablas de rama
- Rama indirecta
- Tabla de búsqueda: una variedad de elementos que se van a comparar, a veces con resultados precalculados
- Sentencia de cambio una sentencia condicional de lenguaje de alto nivel que puede generar una tabla de rama
- Tabla de método virtual una tabla de rama con otro nombre con punteros asignados dinámicamente para el envío (consulte la tabla de envío)
Referencias
- ^ Página, Daniel (2009). Introducción práctica a la arquitectura informática . Springer Science & Business Media. pag. 479. ISBN 9781848822559.
- ^ Jones, Nigel (1 de mayo de 1999). "Cómo crear tablas de salto a través de matrices de puntero de función en C y C ++" . Archivado desde el original el 12 de febrero de 2012 . Consultado el 12 de julio de 2008 .
- ^ "Puntos de entrada alternativos (ENTRADA)" . Uso y portabilidad de GNU Fortran . Fundación de Software Libre. 2001-06-07 . Consultado el 25 de noviembre de 2016 .
- ^ Thomas, RE (29 de abril de 1976). "Compiladores y cargadores de FORTRAN" . ACD: Documento de ingeniería No 42 . ACD . Consultado el 10 de abril de 2009 .
- ^ "Una breve introducción a Fortran 90" . Funciones decrementales / obsoletas / redundantes . Consultado el 10 de abril de 2009 .
enlaces externos
- [1] Ejemplo de tabla de sucursales 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 rama 'Switch / Case' en C, frente a IF / ELSE.
- [4] Código de ejemplo generado para la indexación de matrices si el tamaño de la estructura es divisible por potencias de 2 o de otro modo.
- [5] "Arrays of Pointers to Functions" de Nigel Jones