Tabla de saltos


Tabla de saltos

En programación, se denomina tabla de saltos a un método eficiente de transferencia de control de programas saltando a otra parte del código mediante una tabla de instrucciones de salto. Este sistema es utilizado normalmente en la programación en ensamblador aunque estas tablas también pueden ser generadas por un compilador.

Una tabla de saltos consiste en una lista de instrucciones de salto incondicional que se ejecutan utilizando un offset creado mediante la multiplicación de un índice secuencial por la longitud de la instrucción (los bytes que ocupa en memoria cada instrucción). Se basa en el hecho de que las instrucciones de salto en código máquina tienen una longitud fija y pueden ser ejecutadas de forma extremadamente eficiente por la mayoría del hardware, además de ser más útil cuando se trabaja con datos sin formato fácilmente convertibles a valores secuenciales de índice. Dados estos datos, una tabla de saltos suele ser bastante eficiente, siguiendo normalmente estos pasos: validación opcional de los datos de entrada, transformación de los mismos en un offset dentro de la tabla de saltos (esto suele necesitar multiplicarlos o desplazarlos para su longitud coincida con las instrucciones de salto) y salto a una dirección obtenida a partir de la base de la tabla y el offset generado (esta operación suele incluir la suma del offset al registro del contador de programa).

Otro método de implementación de las tablas de saltos consiste en un array de direcciones desde las cuales es capturada la dirección necesaria para saltar. Este método suele implicar un menor tamaño del código y evita los saltos indirectos. Normalmente el método empleado para construir la tabla de saltos suele venir determinada por la arquitectura del procesador en el cual va a ser ejecutado el código.

Las tablas de saltos suelen usarse en el desarrollo de sistemas operativos. Tanto las llamadas al sistema como las funciones de biblioteca pueden ser referenciadas mediante un índice entero de una tabla de saltos. Con esto se consigue una mejora de la compatibilidad con las versiones siguientes: si el código de una función y la dirección de su destino de salto son modificados, solamente hará falta reajustar la instrucción de salto en la tabla, de este modo todas las aplicaciones compiladas utilizando código de la biblioteca y/o sistema operativo en cuestión no necesitan modificación alguna. Además, las llamadas a funciones por su número (el índice en la tabla) pueden ser útiles en ciertos programas.

Ejemplo

Un ejemplo simple del uso de tablas de saltos en ensamblador del microcontrolador PIC de 8 bits es:

    movf    INDEX, W     ; mover el valor de índice al registro W (registro de trabajo) desde la dirección de memoria INDEX
    addwf   PCL, F       ; sumarlo al registro de contador de programa (PCL). Cada instrucción PIC ocupa 1 byte
                        ; de modo que no es necesario realizar ninguna multiplicación. La mayoría de las arquitecturas transformarían
                        ; el índice de alguna manera antes de sumarlo al contador de programa

table                   ; esta etiqueta marca el comienzo de la tabla de salto
    goto    index_zero  ; cada una de estas instrucciones goto es un salto incondicional a diferentes secciones
    goto    index_one   ; del código
    goto    index_two
    goto    index_three

index_zero
    ; en esta parte se añadiría el código necesario para realizar cualquier acción que requiera que el valor de INDEX sea igual a cero
    return

index_one
...

Historia

El uso de las tablas de saltos y de la representación de los datos sin formato mediante índices era común en los inicios de la informática cuando las memorias eran caras y los procesadores lentos, siendo la representación compacta de los datos y la elección eficiente de las alternativas de almacenamiento dos factores importantes. También se ven con frecuencia en los sistemas empotrados modernos, donde suele hacer falta que el código quepa en espacios realmente mínimos y que a la vez opere de manera eficiente. La principal ventaja de tal conversión es que una vez que un valor ha sido convertido a un índice, puede ser utilizado para saltar o para recuperar algún dato de una tabla de búsqueda de forma eficiente y en cualquier momento sin necesidad de ser convertido de nuevo. Por ejemplo, se podría decir que, relativamente, hay pocos países en el mundo; de forma que éstos podrían ser representados de manera sencilla mediante un código de país en lugar de por una cadena de texto. Esto evita almacenamientos masivos de datos y por consiguientes grandes tiempos de procesado. Las comparaciones numéricas son significativamente más rápidas que las de cadenas de texto, y las búsquedas indexadas son también notablemente más rápidas que las de cadenas. Sin embargo, entre las desventajas se incluye la aparición de un nivel más de indirección. Esto es de poca importancia para los ordenadores, pero supone mayor complejidad de código y de datos para el programador. Además, tal y como se pudo ver en el Efecto 2000, esta aproximación al problema puede llevar posteriormente a problemas si los requisitos de espacio para el índice o la representación superan a los reservados para la tarea.

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Tabla hash — Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados …   Wikipedia Español

  • Tabla de Snowboard — Una tabla de snowboard es la pieza principal del equipo utilizado en el snowboard. Es una tabla diseñada pare ir sujeta bajo los pies del rider mediante fijaciones y sobre la cual se desliza por pistas de nieve. Tabla de Snowboard. La mayoría de… …   Wikipedia Español

  • Tabla de Hash Distribuido — Las tablas de hash distribuidas (en inglés, Distributed Hash Tables, DHT) son una clase de sistemas distribuidos descentralizados que proveen un servicio de búsqueda similar al de las tablas de hash, donde pares (clave, valor) son almacenados en… …   Wikipedia Español

  • Predictor de saltos — Saltar a navegación, búsqueda Un predictor de saltos es un mecanismo hardware utilizado en los procesadores que utilizan segmentación de la unidad de proceso para reducir ciclos de parada en el pipeline. Los saltos condicionales introducen… …   Wikipedia Español

  • Anexo:Tabla Histórica Torneo Argentino B / Torneo del Interior — La siguiente tabla consta de la sumatoria de resultados de los anteriores Torneos Argentinos B y del actual Torneo del Interior desde el torneo 95/96 hasta la fecha (Martes, 31 de mayo de 2005). Consta de algunas omisiones por no contar con todos …   Wikipedia Español

  • Código enhebrado — En ciencias de la computación, el término código enhebrado se refiere a una técnica de implementación del compilador donde el código generado tiene una forma que esencialmente consiste enteramente en llamadas a subrutinas. El código puede ser… …   Wikipedia Español

  • Consorcio de Transporte Metropolitano del Campo de Gibraltar — Lugar Ubicación Campo de Gibraltar …   Wikipedia Español

  • Algoritmo Knuth-Morris-Pratt — El algoritmo KMP tiene por objeto buscar la existencia de palabra dentro de una cadena de texto. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se… …   Wikipedia Español

  • Biblioteca (informática) — Saltar a navegación, búsqueda Ilustración de una aplicación que utiliza la biblioteca libvorbisfile.so para reproducir un archivo Ogg Vorbis. En ciencias de la computación, una biblioteca (o librería) es un conjunto de subprogram …   Wikipedia Español

  • Consorcio de Transportes de la Bahía de Cádiz — Lugar Ubicación Área metropolitana de la Bahía de Cádiz Jerez …   Wikipedia Español