Mesa de ramificação - Branch table

Em programação de computador , uma tabela de ramificação ou tabela de salto é um método de transferência de controle de programa ( ramificação ) para outra parte de um programa (ou um programa diferente que pode ter sido carregado dinamicamente) usando uma tabela de ramificação ou instruções de salto . É uma forma de ramificação de múltiplas vias . A construção da tabela de ramificação é comumente usada ao programar em linguagem assembly, mas também pode ser gerada por compiladores , especialmente ao implementar instruções de switch otimizadas cujos valores são compactados densamente.

Implementação típica

Uma tabela de ramificação consiste em uma lista serial de instruções de ramificação incondicional que é ramificada usando um deslocamento criado pela multiplicação de um índice sequencial pelo comprimento da instrução (o número de bytes na memória ocupados por cada instrução de ramificação). Ele se baseia no fato de que as instruções de código de máquina para ramificação têm um comprimento fixo e podem ser executadas de forma extremamente eficiente pela maioria do hardware, e é mais útil ao lidar com valores de dados brutos que podem ser facilmente convertidos em valores de índice sequenciais . Com esses dados, uma tabela de ramificação pode ser extremamente eficiente. Geralmente consiste nas seguintes 3 etapas:

opcionalmente, validar os dados de entrada para garantir que sejam aceitáveis (isso pode ocorrer sem custo como parte da próxima etapa, se a entrada for um único byte e uma tabela de conversão de 256 bytes for usada para obter diretamente o deslocamento abaixo). Além disso, se não houver dúvida sobre os valores da entrada, esta etapa pode ser omitida.
transformar os dados em um deslocamento na tabela de ramificação. Isso geralmente envolve a multiplicação ou deslocamento (efetivamente multiplicando por uma potência de 2) para levar em consideração o comprimento da instrução. Se uma tabela de tradução estática for usada, essa multiplicação pode ser realizada manualmente ou pelo compilador, sem nenhum custo de tempo de execução.
ramificação para um endereço composto do endereço base da tabela de ramificação mais o deslocamento recém-gerado. Isso às vezes envolve a adição do deslocamento ao registrador do contador do programa (a menos que, em alguns conjuntos de instruções , a instrução de desvio permita um registrador de índice extra). Esse endereço final geralmente aponta para uma de uma sequência de instruções de desvio incondicional ou para a instrução imediatamente além delas (salvando uma entrada na tabela).

O seguinte pseudocódigo ilustra o conceito

 ... validate x                    /* transform x to 0 (invalid) or 1,2,3, according to value..)    */
       y = x * 4;                  /* multiply by branch instruction length (e.g. 4 )               */
       goto next + y;              /* branch into 'table' of branch instructions                    */
 /* start of branch table */
 next: goto codebad;               /* x= 0  (invalid)                                               */
       goto codeone;               /* x= 1                                                          */
       goto codetwo;               /* x= 2                                                          */
 ... rest of branch table
 codebad:                          /* deal with invalid input                                       */

Implementação alternativa usando endereços

Outro método de implementação de uma tabela de ramificação é com uma matriz de ponteiros dos quais o endereço da função necessária é recuperado. Este método também é mais recentemente conhecido por nomes diferentes como " tabela de despacho " ou " tabela de método virtual ", mas essencialmente desempenhando exatamente o mesmo propósito. Este método de função de ponteiro pode resultar no salvamento de uma instrução de máquina e evita o salto indireto (para uma das instruções de desvio).

A lista resultante de ponteiros para funções é quase idêntica ao código encadeado direto e é conceitualmente semelhante a uma tabela de controle .

O método real usado para implementar uma tabela de ramificação é geralmente baseado em:

a arquitetura do processador no qual o código deve ser executado,
se é uma linguagem compilada ou interpretada e
se a ligação tardia está envolvida ou não.

História

O uso de tabelas de ramificação e outras codificações de dados brutos era comum nos primeiros dias da computação, quando a memória era cara, as CPUs eram mais lentas e a representação compacta de dados e a escolha eficiente de alternativas eram importantes. Hoje em dia, eles ainda são comumente usados em:

programação embutida
desenvolvimento de sistema operacional . Em muitos sistemas operacionais, tanto as chamadas do sistema quanto as funções da biblioteca podem ser referenciadas por um índice inteiro em uma tabela de ramificação.
algumas arquiteturas de computador , como IBM / 360, usam tabelas de ramificação para despachar interrupções

Vantagens

As vantagens das tabelas de ramificação incluem:

estrutura de código compacta (apesar de opcodes de ramificação repetidos)
declarações de origem reduzida (versus If declarações repetitivas )
requisito reduzido para testar códigos de retorno individualmente (se usado no local da chamada para determinar o fluxo do programa subsequente )
Eficiência do algoritmo e do código (os dados precisam ser codificados apenas uma vez e o código da tabela de ramificação é geralmente compacto) e o potencial para atingir altas taxas de compressão de dados . Por exemplo, ao compactar nomes de países em códigos de países, uma string como "República Centro-Africana" pode ser compactada em um único índice, resultando em grande economia - especialmente quando a string aparece muitas vezes. Além disso, esse mesmo índice pode ser usado para acessar dados relacionados em tabelas separadas, reduzindo ainda mais os requisitos de armazenamento.

Para funções de biblioteca , onde podem ser referenciadas por um número inteiro :

melhorar a compatibilidade com versões de software subsequentes. Se o código de uma função e o endereço de seu ponto de entrada forem alterados, apenas a instrução de desvio na tabela de desvio precisa ser ajustada; o software aplicativo compilado com a biblioteca ou para o sistema operacional não precisa de modificação.

Além disso, chamar funções por número (o índice na tabela) às vezes pode ser útil em alguns casos na programação de aplicativo normal.

Desvantagens

Nível extra de indireção , o que resulta em um impacto de desempenho geralmente pequeno.
Restrições em algumas linguagens de programação, embora geralmente haja maneiras alternativas de implementar o conceito básico de ramificação de múltiplas vias.

Exemplo

Um exemplo simples de uso de tabela de ramificação na linguagem assembly Microchip PIC de 8 bits é:

     movf    INDEX,W     ; Move the index value into the W (working) register from memory
     addwf   PCL,F       ; add it to the program counter. Each PIC instruction is one byte
                         ; so there is no need to perform any multiplication. 
                         ; Most architectures will transform the index in some way before 
                         ; adding it to the program counter.

 table                   ; The branch table begins here with this label
     goto    index_zero  ; each of these goto instructions is an unconditional branch
     goto    index_one   ; of code.
     goto    index_two
     goto    index_three

 index_zero
     ; Code is added here to perform whatever action is required when INDEX = zero
     return

 index_one
 ...

Nota: este código funcionará apenas se PCL <(tabela + índice_último). Para garantir essa condição, podemos usar uma diretiva "org". E se GOTO (PIC18F por exemplo) tiver 2 bytes, isso limita o número de entradas da tabela a menos de 128.

Exemplo de tabela de salto em C

Outro exemplo simples, desta vez demonstrando uma tabela de salto em vez de uma mera tabela de ramificação. Isso permite que blocos de programa fora do procedimento / função atualmente ativa sejam chamados:

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
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 value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = atoi(argv[1]) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

Exemplo de tabela de salto em PL / I

PL / I implementa uma tabela de salto como um array de variáveis de rótulo . Eles podem ser inicializados de uma maneira incomum, usando um rótulo de instrução subscrito. As variáveis de rótulo PL / I não são simplesmente o endereço da instrução, mas geralmente contêm informações adicionais sobre o estado do bloco de código ao qual pertencem. Sem a inicialização incomum, isso também poderia ser codificado com chamadas e uma matriz de variáveis de entrada.

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* code for choice 1 */ ;
    ...
  lab(2): /* code for choice 2 */ ;
    ...

Tabelas de ramificação geradas pelo compilador

Os programadores freqüentemente deixam a decisão de criar ou não uma tabela de ramificação para o compilador, acreditando que ele é perfeitamente capaz de fazer a escolha correta a partir das chaves de busca conhecidas. Isso pode ser verdade para otimizar compiladores para casos relativamente simples, onde o intervalo de chaves de pesquisa é limitado. No entanto, os compiladores não são tão inteligentes quanto os humanos e não podem ter um conhecimento profundo do 'contexto', acreditando que uma gama de valores inteiros de chave de pesquisa possíveis, como 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 e 1000 gerariam uma tabela de ramificação com um número excessivamente grande de entradas vazias (900+) para muito pouca vantagem. Um bom compilador de otimização pode então pré-classificar os valores e gerar código para uma pesquisa de divisão binária , como uma 'segunda melhor' opção. Na verdade, o aplicativo pode ser altamente "crítico em termos de tempo" e os requisitos de memória podem não ser um problema.

No entanto, um pouco de 'bom senso' pode transformar este caso particular, e muitos outros casos semelhantes, em um processo simples de duas etapas com grande potencial de economia, embora ainda deixando a escolha final para o compilador, mas 'auxiliando em sua decisão' consideravelmente:

Primeiro, teste a chave de pesquisa = 1000 e execute o desvio apropriado.
Permita que o compilador 'escolha' gerar uma tabela de ramificação nas chaves de pesquisa restantes (1-50).

Variações ao longo de linhas semelhantes podem ser usadas nos casos em que há dois conjuntos de intervalos curtos com uma grande lacuna entre os intervalos.

GoTo Computado

Embora a técnica agora seja conhecida como 'tabelas de ramificação', os primeiros usuários do compilador chamavam a implementação de ' GoTo computado ', referindo-se à instrução encontrada na série de compiladores Fortran. A instrução acabou sendo preterida no Fortran 90 (em favor das instruções SELECT e CASE no nível de origem).

Criação do índice para a tabela de ramos

Onde não há um valor inteiro óbvio disponível para uma tabela de ramificação, ela pode, no entanto, ser criada a partir de uma chave de pesquisa (ou parte de uma chave de pesquisa) por alguma forma de transformação aritmética, ou pode ser simplesmente o número da linha de um banco de dados ou o número da entrada em uma matriz contendo a chave de pesquisa encontrada durante a validação anterior da chave.

Em alguns casos, pode ser necessária uma tabela hash para formar o índice. No entanto, para valores de entrada de byte único, como AZ (ou o primeiro byte de uma chave mais longa), o conteúdo do próprio byte ( dados brutos ) pode ser usado em um processo de duas etapas, " função hash trivial " para obter um índice final para uma tabela de ramificação com zero gaps.

Converta o caractere de dados brutos em seu equivalente numérico (exemplo ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
Use o valor numérico inteiro como índice em uma matriz de 256 bytes, para obter um segundo índice (entradas inválidas 0; representando lacunas, caso contrário, 1, 2, 3 etc.)

A matriz não teria mais do que (256 x 2) bytes - para conter todos os números inteiros não assinados (curtos) de 16 bits possíveis. Se nenhuma validação for necessária e apenas maiúsculas forem usadas, o tamanho da matriz pode ser tão pequeno quanto (26 x 2) = 52 bytes.

Outros usos da técnica

Embora a técnica de ramificação usando uma tabela de ramificação seja mais frequentemente utilizada apenas com o propósito de alterar o fluxo do programa - para saltar para um rótulo de programa que é uma ramificação incondicional - a mesma técnica pode ser usada para outros propósitos. Por exemplo, ele pode ser usado para selecionar um ponto de partida em uma sequência de instruções repetidas em que o descarte é a norma e intencional. Isso pode ser usado, por exemplo, otimizando compiladores ou compiladores JIT no desenrolamento de loop .

Veja também

Dispatch table a branch table por outro nome usado para late binding
Matrizes de ponteiro de função de endereços para funções, conforme usado em tabelas de ramificação
Ramo indireto
Tabela de consulta: uma série de itens a serem correspondidos, às vezes contendo resultados pré-calculados
Instrução switch uma instrução condicional de linguagem de alto nível que pode gerar uma tabela de ramificação
Tabela de método virtual uma tabela de ramificação com outro nome com ponteiros atribuídos dinamicamente para despacho (ver tabela de despacho)

Referências

links externos

[1] Exemplo de tabela de ramificação em Wikibooks para IBM S / 360
[2] Exemplos e argumentos para tabelas de salto por meio de matrizes de ponteiro de função em C / C ++
[3] Exemplo de código gerado pela tabela de ramificação 'Switch / Case' em C, versus IF / ELSE.
[4] Exemplo de código gerado para indexação de array se o tamanho da estrutura for divisível por potências de 2 ou outro.
[5] "Arrays of Pointers to Functions" por Nigel Jones

Languages

In other projects