Verzweigungstabelle - Branch table

In der Computerprogrammierung , eine Verzweigungstabelle oder Sprungtabelle ist eine Methode , die Programmsteuerung der Übertragung ( Verzweigung ) auf einen anderen Teil eines Programms (oder einem anderen Programm , das dynamisch geladen worden sein kann) , eine Tabelle des Zweiges oder springen unter Verwendung Anweisungen . Es ist eine Form der Mehrwegezweig . Die Verzweigungstabellenkonstruktion wird häufig beim Programmieren in Assemblersprache verwendet , kann jedoch auch von Compilern generiert werden , insbesondere bei der Implementierung optimierter switch-Anweisungen, deren Werte dicht zusammengepackt sind.

Typische Implementierung

Eine Verzweigungstabelle besteht aus einer seriellen Liste von bedingungslosen Verzweigungsbefehlen , in die unter Verwendung eines Versatzes verzweigt wird, der durch Multiplizieren eines sequentiellen Index mit der Befehlslänge (der Anzahl der von jedem Verzweigungsbefehl belegten Bytes im Speicher) erzeugt wird. Es beruht auf der Tatsache, dass Maschinencode- Anweisungen zum Verzweigen eine feste Länge haben und von der meisten Hardware äußerst effizient ausgeführt werden können. Dies ist am nützlichsten, wenn Rohdatenwerte verarbeitet werden, die leicht in sequentielle Indexwerte konvertiert werden können. Angesichts solcher Daten kann eine Verzweigungstabelle äußerst effizient sein. Es besteht normalerweise aus den folgenden 3 Schritten:

  1. Optionales Überprüfen der Eingabedaten, um sicherzustellen, dass sie akzeptabel sind (dies kann im Rahmen des nächsten Schritts kostenlos erfolgen, wenn die Eingabe ein einzelnes Byte ist und eine 256-Byte-Übersetzungstabelle verwendet wird, um den folgenden Offset direkt zu erhalten). Wenn kein Zweifel an den Werten der Eingabe besteht, kann dieser Schritt weggelassen werden.
  2. Transformieren Sie die Daten in einen Offset in die Verzweigungstabelle. Dies beinhaltet normalerweise das Multiplizieren oder Verschieben (effektiv das Multiplizieren mit einer Potenz von 2), um die Befehlslänge zu berücksichtigen. Wenn eine statische Übersetzungstabelle verwendet wird, kann diese Multiplikation manuell oder vom Compiler ohne Laufzeitkosten durchgeführt werden.
  3. Verzweigung zu einer Adresse, die aus der Basisadresse der Verzweigungstabelle plus dem gerade generierten Offset besteht. Dies beinhaltet manchmal eine Addition des Offsets auf das Programmzählerregister (es sei denn, in einigen Befehlssätzen erlaubt der Verzweigungsbefehl ein zusätzliches Indexregister). Diese endgültige Adresse verweist normalerweise auf eine Folge von bedingungslosen Verzweigungsbefehlen oder auf den Befehl unmittelbar dahinter (Speichern eines Eintrags in der Tabelle).

Der folgende Pseudocode veranschaulicht das Konzept

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

Alternative Implementierung mit Adressen

Eine andere Methode zum Implementieren einer Verzweigungstabelle besteht aus einem Array von Zeigern, von denen die Adresse der erforderlichen Funktion abgerufen wird. Diese Methode ist in jüngerer Zeit auch unter so unterschiedlichen Namen wie " Versandtabelle " oder " virtuelle Methodentabelle " bekannt, erfüllt jedoch im Wesentlichen genau den gleichen Zweck. Diese Zeigerfunktionsmethode kann zum Speichern eines Maschinenbefehls führen und vermeidet den indirekten Sprung (zu einem der Verzweigungsbefehle).

Die resultierende Liste von Zeigern auf Funktionen ist fast identisch mit Code mit direktem Thread und ähnelt konzeptionell einer Steuertabelle .

Die tatsächliche Methode zum Implementieren einer Verzweigungstabelle basiert normalerweise auf:

  • die Architektur des Prozessors, auf dem der Code ausgeführt werden soll,
  • ob es sich um eine kompilierte oder interpretierte Sprache handelt und
  • ob es sich um eine späte Bindung handelt oder nicht.

Geschichte

Die Verwendung von Verzweigungstabellen und anderer Rohdatencodierung war in den frühen Tagen des Rechnens üblich, als Speicher teuer war, CPUs langsamer waren und eine kompakte Datendarstellung und eine effiziente Auswahl von Alternativen wichtig waren. Heutzutage werden sie häufig noch verwendet in:

Vorteile

Zu den Vorteilen von Verzweigungstabellen gehören:

  • kompakte Codestruktur (trotz wiederholter Verzweigungs-Opcodes)
  • reduzierte Quellanweisungen (gegenüber sich wiederholenden If Anweisungen)
  • Reduzierte Anforderung, Rückkehrcodes einzeln zu testen (falls am Anrufort verwendet , um den nachfolgenden Programmablauf zu bestimmen )
  • Algorithmus- und Codeeffizienz (Daten müssen nur einmal codiert werden und Verzweigungstabellencode ist normalerweise kompakt) und das Potenzial, hohe Datenkomprimierungsraten zu erzielen. Wenn Sie beispielsweise Ländernamen in Ländercodes komprimieren, kann eine Zeichenfolge wie "Zentralafrikanische Republik" auf einen einzigen Index komprimiert werden, was zu erheblichen Einsparungen führt - insbesondere, wenn die Zeichenfolge häufig vorkommt. Darüber hinaus kann derselbe Index verwendet werden, um auf verwandte Daten in separaten Tabellen zuzugreifen, wodurch der Speicherbedarf weiter reduziert wird.

Für Bibliotheksfunktionen , auf die durch eine Ganzzahl verwiesen werden kann :

  • Verbesserung der Kompatibilität mit nachfolgenden Softwareversionen. Wenn der Code einer Funktion und die Adresse ihres Einstiegspunkts geändert werden, muss nur der Verzweigungsbefehl in der Verzweigungstabelle angepasst werden. Anwendungssoftware, die für die Bibliothek oder für das Betriebssystem kompiliert wurde, muss nicht geändert werden.

Darüber hinaus kann das Aufrufen von Funktionen nach Nummer (dem Index in der Tabelle) in einigen Fällen bei der normalen Anwendungsprogrammierung manchmal hilfreich sein.

Nachteile

  • Zusätzliche Indirektionsebene , die normalerweise einen kleinen Leistungstreffer verursacht.
  • Einschränkungen in einigen Programmiersprachen, obwohl es normalerweise alternative Möglichkeiten gibt, das Grundkonzept der Mehrwegverzweigung zu implementieren.

Beispiel

Ein einfaches Beispiel für die Verwendung von Verzweigungstabellen in der 8-Bit- PIC- Assemblersprache Microchip ist:

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

Hinweis: Dieser Code funktioniert nur, wenn PCL <(table + index_last). Um diesen Zustand sicherzustellen, können wir eine "org" -Richtlinie verwenden. Wenn GOTO (z. B. PIC18F) 2 Byte beträgt, wird die Anzahl der Tabelleneinträge auf weniger als 128 begrenzt.

Beispiel für eine Sprungtabelle in C.

Ein weiteres einfaches Beispiel, das diesmal eher eine Sprungtabelle als eine bloße Verzweigungstabelle zeigt. Dadurch können Programmbausteine ​​außerhalb der aktuell aktiven Prozedur / Funktion aufgerufen werden:

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

Beispiel für eine Sprungtabelle in PL / I.

PL / I implementiert eine Sprungtabelle als Array von Beschriftungsvariablen . Diese können auf ungewöhnliche Weise mithilfe eines tiefgestellten Anweisungsetiketts initialisiert werden. PL / I-Beschriftungsvariablen sind nicht einfach die Adresse der Anweisung, sondern enthalten normalerweise zusätzliche Informationen zum Status des Codeblocks, zu dem sie gehören. Ohne die ungewöhnliche Initialisierung könnte dies auch mit Aufrufen und einem Array von Eingabevariablen codiert werden.

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

Vom Compiler generierte Verzweigungstabellen

Programmierer überlassen häufig die Entscheidung, ob eine Verzweigungstabelle erstellt werden soll oder nicht, dem Compiler und glauben, dass er in der Lage ist, aus den bekannten Suchschlüsseln die richtige Auswahl zu treffen. Dies gilt möglicherweise für die Optimierung von Compilern für relativ einfache Fälle, in denen der Bereich der Suchschlüssel begrenzt ist. Compiler sind jedoch nicht so intelligent wie Menschen und können kein tiefes Wissen über den Kontext haben, da sie glauben, dass eine Reihe möglicher ganzzahliger Suchschlüsselwerte wie 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 würden eine Verzweigungstabelle mit einer übermäßig großen Anzahl leerer Einträge (900+) für sehr geringen Vorteil erzeugen. Ein guter Optimierungs-Compiler kann dann die Werte vorsortieren und Code für eine binäre Chop- Suche als zweitbeste Option generieren . Tatsächlich kann die Anwendung sehr "zeitkritisch" sein und der Speicherbedarf ist möglicherweise überhaupt kein Problem.

Ein wenig „gesunder Menschenverstand“ kann diesen speziellen Fall und viele andere ähnliche Fälle jedoch in einen einfachen zweistufigen Prozess mit sehr großen Einsparpotenzialen umwandeln, während die endgültige Wahl letztendlich dem Compiler überlassen bleibt, aber „seine Entscheidung unterstützt“. wesentlich:

  • Testen Sie zunächst den Suchschlüssel = 1000 und führen Sie die entsprechende Verzweigung durch.
  • Lassen Sie den Compiler 'auswählen', um eine Verzweigungstabelle für die verbleibenden Suchschlüssel (1-50) zu generieren.

Variationen entlang ähnlicher Linien können in Fällen verwendet werden, in denen zwei Sätze von kurzen Bereichen mit einer großen Lücke zwischen den Bereichen vorhanden sind.

Berechnete GoTo

Während die Technik jetzt als "Verzweigungstabellen" bekannt ist, nannten frühe Compiler-Benutzer die Implementierung " Computed GoTo " und verwiesen dabei auf die Anweisungen in der Fortran-Compilerserie. Die Anweisung wurde schließlich in Fortran 90 veraltet (zugunsten von SELECT & CASE-Anweisungen auf Quellenebene).

Erstellen des Index für die Verzweigungstabelle

Wenn für eine Verzweigungstabelle kein offensichtlicher ganzzahliger Wert verfügbar ist, kann er dennoch durch eine arithmetische Transformation aus einem Suchschlüssel (oder einem Teil eines Suchschlüssels) erstellt werden oder kann einfach die Zeilennummer einer Datenbank oder die Eintragsnummer sein in einem Array, das den Suchschlüssel enthält, der während der früheren Validierung des Schlüssels gefunden wurde.

In einigen Fällen kann eine Hash-Tabelle erforderlich sein, um den Index zu bilden. Für Einzelbyte-Eingabewerte wie AZ (oder das erste Byte eines längeren Schlüssels) kann der Inhalt des Bytes selbst ( Rohdaten ) jedoch in einem zweistufigen " Trivial-Hash-Funktion " -Prozess verwendet werden, um a zu erhalten Endindex für eine Verzweigungstabelle mit null Lücken.

  1. Konvertieren Sie das Rohdatenzeichen in sein numerisches Äquivalent (Beispiel ASCII 'A' ==> 65 Dezimal, 0x41 Hexadezimal)
  2. Verwenden Sie den numerischen Ganzzahlwert als Index für ein 256-Byte-Array, um einen zweiten Index zu erhalten (ungültige Einträge 0; stellen Lücken dar, andernfalls 1, 2, 3 usw.).

Das Array wäre nicht größer als (256 x 2) Bytes - um alle möglichen 16-Bit-Ganzzahlen ohne Vorzeichen (kurz) aufzunehmen. Wenn keine Validierung erforderlich ist und nur Großbuchstaben verwendet werden, kann die Größe des Arrays so klein wie (26 x 2) = 52 Byte sein.

Andere Anwendungen der Technik

Obwohl die Technik der Verzweigung unter Verwendung einer Verzweigungstabelle am häufigsten nur zum Ändern des Programmflusses verwendet wird - um zu einer Programmbezeichnung zu springen, die eine bedingungslose Verzweigung ist - kann dieselbe Technik für andere Zwecke verwendet werden. Zum Beispiel kann es verwendet werden, um einen Startpunkt in einer Folge von wiederholten Anweisungen auszuwählen, bei denen das Durchfallen die Norm und Absicht ist. Dies kann beispielsweise durch Optimieren von Compilern oder JIT- Compilern beim Abrollen von Schleifen verwendet werden .

Siehe auch

Verweise

Externe Links

  • [1] Beispiel einer Verzweigungstabelle in Wikibooks für IBM S / 360
  • [2] Beispiele und Argumente für Sprungtabellen über Funktionszeiger-Arrays in C / C ++
  • [3] Beispielcode, der von der Verzweigungstabelle 'Switch / Case' in C im Vergleich zu IF / ELSE generiert wurde.
  • [4] Beispielcode für die Array-Indizierung, wenn die Strukturgröße durch Potenzen von 2 oder auf andere Weise teilbar ist.
  • [5] "Arrays of Pointers to Functions" von Nigel Jones