Tabulka větví - Branch table

V počítačovém programování je tabulka větví nebo skoková tabulka metodou přenosu řízení programu ( větvení ) do jiné části programu (nebo jiného programu, který může být dynamicky načten) pomocí tabulky pokynů větvení nebo skoků . Je to forma vícecestné větve . Konstrukce větvové tabulky se běžně používá při programování v assembleru, ale může být také generována kompilátory , zejména při implementaci optimalizovaných příkazů přepínačů, jejichž hodnoty jsou hustě zabaleny dohromady.

Typická implementace

Pobočka tabulka se skládá ze sériového seznamu nepodmíněných poboček instrukcí, které se rozvětvuje do za použití offset vytvořené vynásobením se sekvenční index délkou instrukcí (počet bajtů v paměti obsazené každou instrukci větvení). Spoléhá se na skutečnost, že instrukce strojového kódu pro větvení mají pevnou délku a většina hardwaru je může provádět velmi efektivně, a je nejužitečnější při práci s hodnotami nezpracovaných dat, které lze snadno převést na hodnoty sekvenčního indexu. Vzhledem k těmto datům může být tabulka větví extrémně efektivní. Obvykle se skládá z následujících 3 kroků:

  1. volitelně ověření vstupních dat, aby se zajistilo, že jsou přijatelné (k tomu může dojít bez nákladů jako součást dalšího kroku, pokud je vstup jednobajtový a k přímému získání posunu níže je použita tabulka překladu 256 bajtů). Pokud není pochyb o hodnotách vstupu, lze tento krok vynechat.
  2. transformovat data na offset do větvové tabulky. To obvykle zahrnuje znásobení nebo posunutí (efektivní vynásobení silou 2), aby se zohlednila délka instrukce. Pokud se použije tabulka statického překladu, lze toto násobení provést ručně nebo kompilátorem bez nákladů na běh.
  3. větvení na adresu tvořenou základní adresou tabulky větví plus právě vygenerovaný offset. To někdy zahrnuje přidání offsetu do registru čítače programu (pokud v některých sadách instrukcí instrukce pobočky nepovoluje další indexový registr). Tato konečná adresa obvykle ukazuje na jednu z posloupnosti bezpodmínečných větvových instrukcí nebo na instrukci bezprostředně za nimi (uložení jedné položky do tabulky).

Následující pseudokód ilustruje koncept

 ... 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                                       */

Alternativní implementace pomocí adres

Jiný způsob provádění větev stůl je s řadou z ukazatelů z níž bylo požadované funkci je opět nalezena adresa. Tato metoda je také v poslední době známá pod tak odlišnými názvy jako „ tabulka odeslání “ nebo „ tabulka virtuální metody “, ale v zásadě plní přesně stejný účel. Tato metoda funkce ukazatele může vyústit v uložení jedné strojové instrukce a vyhnout se nepřímému skoku (na jednu z instrukcí větve).

Výsledný seznam ukazatelů na funkce je téměř identický s přímým vláknovým kódem a je koncepčně podobný kontrolní tabulce .

Skutečná metoda použitá k implementaci tabulky větví je obvykle založena na:

  • architektura procesoru, na kterém má být kód spuštěn,
  • zda se jedná o kompilovaný nebo interpretovaný jazyk a
  • ať už jde o pozdní vazbu nebo ne.

Dějiny

Používání větvových tabulek a dalšího kódování nezpracovaných dat bylo v počátcích práce s počítačem, kdy byla paměť drahá, běžné , CPU pomalejší a kompaktní reprezentace dat a efektivní výběr alternativ byly důležité. V dnešní době se běžně používají:

Výhody

Mezi výhody pobočkových stolů patří:

  • kompaktní struktura kódu (navzdory opakovaným kódům poboček)
  • snížené zdrojové příkazy (oproti opakujícím se If příkazům)
  • snížený požadavek na individuální testování návratových kódů (je-li použit na místě volání k určení následného toku programu )
  • Algoritmická a kódová účinnost (data je třeba kódovat pouze jednou a kód větvové tabulky je obvykle kompaktní) a potenciál dosáhnout vysokých kompresních poměrů dat . Například při kompresi názvů zemí na kódy zemí lze řetězec jako „Středoafrická republika“ komprimovat do jediného indexu, což má za následek velké úspory - zvláště když se řetězec objeví mnohokrát. Tento stejný index lze navíc použít pro přístup k souvisejícím datům v samostatných tabulkách, což dále snižuje požadavky na úložiště.

Pro funkce knihovny , kde na ně může odkazovat celé číslo :

  • zlepšit kompatibilitu s následnými verzemi softwaru. Pokud se změní kód funkce a adresa jejího vstupního bodu, je třeba upravit pouze instrukci větvení v tabulce větví; aplikační software zkompilovaný proti knihovně nebo pro operační systém nevyžaduje úpravy.

Kromě toho může být volání funkcí podle čísla (index do tabulky) někdy užitečné v některých případech v normálním programování aplikací.

Nevýhody

  • Extra úroveň indirection , která způsobí obvykle malý výkon hit.
  • Omezení v některých programovacích jazycích, i když obvykle existují alternativní způsoby implementace základní koncepce vícecestného větvení.

Příklad

Jednoduchý příklad použití větvové tabulky v 8bitovém montážním jazyce Microchip PIC je:

     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
 ...

Poznámka: tento kód bude fungovat, pouze pokud PCL <(tabulka + index_last). K zajištění této podmínky můžeme použít direktivu „org“. A pokud má GOTO (například PIC18F) 2 bajty, omezuje to počet položek tabulky na méně než 128.

Příklad skokové tabulky v C

Další jednoduchý příklad, tentokrát demonstrace skokové tabulky, nikoli pouhé větvové tabulky. To umožňuje volání programových bloků mimo právě aktivní proceduru / funkci:

#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;
}

Příklad skokové tabulky v PL / I

PL / I implementuje skokovou tabulku jako pole proměnných štítků . Ty mohou být inicializovány neobvyklým způsobem pomocí popisovaného popisku štítku. Proměnné označení PL / I nejsou jen adresou příkazu, ale obvykle obsahují další informace o stavu bloku kódu, ke kterému patří. Bez neobvyklé inicializace by to mohlo být také kódováno voláními a řadou vstupních proměnných.

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

Kompilátorem generované větvové tabulky

Programátoři často nechávají rozhodnutí, zda vytvořit větvící tabulku, na kompilátoru a věří, že je dokonale schopen provést správnou volbu ze známých vyhledávacích kláves. To může být pravda pro optimalizaci překladačů pro relativně jednoduché případy, kdy je rozsah vyhledávacích kláves omezený. Překladače však nejsou tak inteligentní jako lidé a nemohou mít hluboké znalosti o „kontextu“, protože věří, že řada možných celočíselných hodnot pro vyhledávání, například 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 a 1000 by vygenerovalo tabulku větví s nadměrně velkým počtem prázdných záznamů (900+) pro velmi malou výhodu. Dobrý optimalizující kompilátor pak může přednastavit hodnoty a vygenerovat kód pro hledání binárních sekání jako možnost „druhé nejlepší“. Ve skutečnosti může být aplikace vysoce „časově kritická“ a požadavek na paměť nemusí být vůbec problémem.

Trochu „zdravého rozumu“ však může tento konkrétní případ a mnoho dalších podobných případů přeměnit na jednoduchý dvoustupňový proces s velmi velkými potenciálními úsporami, přičemž nakonec ponechá konečnou volbu na kompilátoru, ale „napomáhá jeho rozhodnutí“ značně:

  • Nejprve otestujte vyhledávací klíč = 1000 a proveďte příslušnou větev.
  • Nechte kompilátor 'vybrat' vygenerovat tabulku větví na zbývajících vyhledávacích klávesách (1-50).

Variace podél podobných linií lze použít v případech, kdy existují dvě sady krátkých rozsahů s velkou mezerou mezi rozsahy.

Vypočítané GoTo

Zatímco tato technika je nyní známá jako „větvové tabulky“, první uživatelé kompilátoru nazývali implementaci „ vypočítaný GoTo “, s odkazem na instrukci nalezenou v sérii překladačů Fortran. Pokyn byl nakonec zastaralý ve Fortranu 90 (ve prospěch příkazů SELECT & CASE na úrovni zdroje).

Vytváření indexu pro tabulku větví

Pokud pro tabulku větví není k dispozici žádná zjevná celočíselná hodnota, lze ji přesto vytvořit z vyhledávacího klíče (nebo jeho části vyhledávacího klíče) nějakou formou aritmetické transformace, nebo to může být jednoduše číslo řádku databáze nebo číslo položky v poli obsahujícím vyhledávací klíč nalezený během dřívějšího ověřování klíče.

V některých případech může být pro vytvoření indexu vyžadována hash tabulka . Avšak u vstupních hodnot pro jeden bajt, jako je AZ (nebo první bajt delšího klíče), lze obsah samotného bajtu ( nezpracovaná data ) použít ve dvoustupňovém procesu „ triviální hashovací funkce “ k získání konečný index pro tabulku větví s nulovými mezerami.

  1. Převést znak nezpracovaných dat na jeho číselný ekvivalent (příklad ASCII 'A' ==> 65 desetinných míst, 0x41 šestnáctkový)
  2. Použijte číselnou celočíselnou hodnotu jako index do 256 bajtového pole, abyste získali druhý index (neplatné položky 0; představující mezery, jinak 1, 2, 3 atd.)

Pole by nemělo být větší než (256 x 2) bajtů - pro uložení všech možných 16bitových nepodepsaných (krátkých) celých čísel. Pokud není vyžadováno ověření a používají se pouze velká písmena, velikost pole může být tak malá jako (26 x 2) = 52 bajtů.

Jiná použití techniky

Ačkoli se technika větvení pomocí tabulky větví nejčastěji používá pouze za účelem změny toku programu - přeskočit na označení programu, které je bezpodmínečnou větví -, stejnou techniku ​​lze použít i pro jiné účely. Lze jej například použít k výběru počátečního bodu v posloupnosti opakovaných pokynů, kde propad je normou a záměrem. To lze použít například optimalizací kompilátorů nebo kompilátorů JIT při odvíjení smyčky .

Viz také

Reference

externí odkazy

  • [1] Příklad tabulky větví ve Wikibooks pro IBM S / 360
  • [2] Příklady a argumenty pro skokové tabulky přes pole ukazatelů funkcí v C / C ++
  • [3] Příklad kódu vygenerovaného větvovou tabulkou „přepínače / případu“ v jazyce C oproti IF / ELSE.
  • [4] Příklad kódu generovaného pro indexování pole, pokud je velikost struktury dělitelná mocninami 2 nebo jinak.
  • [5] „Pole ukazatelů na funkce“ Nigel Jones