Frage zum Jump-Table-Switch-Fall

Ich versuche, einige Dinge über Sprungtabellen und ihre Beziehung zwischen einer switch case-Anweisung zu verstehen.

Mir wurde gesagt, dass eine Sprungtabelle eine O(1)-Struktur ist, die der Compiler generiert, was das Nachschlagen von Werten im Wesentlichen so schnell wie möglich macht. In einigen Fällen kann ein Hashtable/Wörterbuch jedoch schneller sein. Mir wurde auch gesagt, dass dies nur funktioniert, wenn das Switch-Gehäuse enthält ordered Datenwerte.

Kann jemand dies bitte bestätigen oder dementieren und erklären, was eine Sprungtabelle ist, ihre Bedeutung und die Zeitkomplexität im Vergleich zur Verwendung eines Wörterbuchs oder einer Hashtabelle. Vielen Dank.

EIN Tisch springen ist eine abstrakte Struktur gewohnt Kontrolle übertragen an einen anderen Ort. Goto, Continue und Break sind ähnlich, außer dass sie immer zu einer bestimmten Stelle übertragen werden, anstatt zu einer Möglichkeit von vielen. Insbesondere ist dieser Kontrollfluss nicht dasselbe wie ein Funktionsaufruf. (Wikipedia-Artikel über Zweigtische ist verwandt.)

EIN Switch-Anweisung ist, wie man Sprungtabellen in C/C++ schreibt. Es wird nur eine eingeschränkte Form bereitgestellt (kann nur ganzzahlige Typen einschalten), um die Implementierungen in diesem häufigen Fall einfacher und schneller zu machen. (Wie man Sprungtabellen effizient implementiert, wurde viel mehr für ganzzahlige Typen untersucht als für den allgemeinen Fall.) Ein klassisches Beispiel ist Duffs Gerät.

Jedoch, die volle Leistungsfähigkeit einer Sprungtabelle wird oft nicht benötigt, z. B. wenn jeder Fall eine Break-Anweisung hätte. Diese “Limited Jump Tables” sind a anderes Musterdie nur die gut untersuchte Effizienz einer Sprungtabelle ausnutzen, und sind üblich, wenn jede “Aktion” unabhängig von den anderen ist.

Tatsächliche Implementierungen von Sprungtabellen nehmen unterschiedliche Formen an, die sich hauptsächlich darin unterscheiden, wie die Schlüssel-zu-Index-Zuordnung erfolgt. Bei dieser Zuordnung kommen Begriffe wie „Wörterbuch“ und „Hash-Tabelle“ ins Spiel, und diese Techniken können unabhängig von einer Sprungtabelle verwendet werden. Zu sagen, dass ein Code “eine Sprungtabelle verwendet”, bedeutet nicht von selbst, dass Sie eine O (1) -Suche haben.

Der Compiler kann die Lookup-Methode für jede switch-Anweisung frei wählen, und es gibt keine Garantie dafür, dass Sie eine bestimmte Implementierung erhalten. Compiler-Optionen wie „Optimize-for-Speed“ und „Optimize-for-Size“ sollten jedoch berücksichtigt werden.

Du solltest Schauen Sie sich das Studium von Datenstrukturen an die von ihnen gestellten unterschiedlichen Komplexitätsanforderungen in den Griff zu bekommen. Kurz gesagt, wenn Sie mit “Wörterbuch” einen ausgeglichenen Binärbaum meinen, dann ist es O (log n); und eine Hash-Tabelle hängt von ihrer Hash-Funktion und Kollisionsstrategie ab. Im speziellen Fall von switch-Anweisungen kann der Compiler, da er über vollständige Informationen verfügt, a generieren Perfekte Hash-Funktion was O(1)-Lookup bedeutet. Verlieren Sie sich jedoch nicht, indem Sie nur die gesamte algorithmische Komplexität betrachten: Sie verbirgt wichtige Faktoren.

Eine Sprungtabelle ist im Grunde ein Array von Zeigern auf Codeteile, um die verschiedenen Fälle in der switch-Anweisung zu behandeln. Es wird am wahrscheinlichsten generiert, wenn Ihre Fälle dicht sind (dh Sie haben einen Fall für jeden möglichen Wert in einem Bereich). Zum Beispiel bei einer Aussage wie:

switch (i) {
   case 1: printf("case 1"); break;
   case 2: printf("case 2"); break;
   case 3: printf("case 3"); break;
}

Es könnte Code generieren, der ungefähr so ​​​​etwas entspricht:

void case1() { printf("case 1"); }
void case2() { printf("case 2"); }
void case3() { printf("case 3"); }

typedef void (*pfunc)(void);

pfunc functions[3] = {case1, case2, case3};

if ((unsigned)i<3)    
    functions[i]();

Dies hat O(K)-Komplexität. Eine typische Hash-Tabelle hat auch ungefähr O (K) erwartet Komplexität, obwohl der schlimmste Fall typischerweise O(N) ist. Die Sprungtabelle ist normalerweise schneller, wird aber normalerweise nur verwendet, wenn die Tabelle ziemlich dicht ist, während eine Hash-Tabelle/ein Wörterbuch ziemlich gut funktioniert, selbst wenn die Fälle ziemlich spärlich sind.

Angenommen, Sie hätten eine Reihe von Verfahren:

void fa() { 
 printf("a\n");
}

...

void fz() { 
 printf("it's z!\n");
}



typedef void (*F)();
F table[26]={fa,fb,...,fz};

Angenommen, Sie akzeptieren ein Eingabezeichen (von az) vom Benutzer und führen fc aus:

char c;
switch(c) {
   case 'a': fa();break;
   case 'b': fb();break;
   ...
   case 'z': fz();break;       
   default: exit(-1);
}

Idealerweise würde dies durch etwas ersetzt werden wie:

if (c<'a' || c>'z') exit(-1);
else (*table[c-'a'])();

Natürlich könnten Sie die Tabelle vergrößern, damit die Bereichsprüfung nicht erforderlich wäre.

Der Compiler würde dies für beliebigen Code tun, nicht unbedingt nur für Funktionsaufrufe, und er würde dies tun, indem er die Adresse speichert, zu der gesprungen werden soll (im Wesentlichen ein goto). C unterstützt keine Art von berechnetem Goto (Indizieren in eine Tabelle oder auf andere Weise), aber die CPU-Anweisungen dafür sind ziemlich einfach.

Das Kompilieren für eine switch-Anweisung kann je nach Fall viele Formen annehmen. Wenn die Fälle eng beieinander liegen, ist es ein Kinderspiel: Verwenden Sie eine Sprungtabelle. Wenn die Fälle weit voneinander entfernt sind, verwenden Sie if (case == value) oder verwenden Sie eine Karte. Oder ein Compiler kann eine Kombination verwenden: Inseln von Sprungtabellen, die durch if-Prüfungen der Sprungtabellenbereiche bestimmt werden.

Eine Sprungtabelle ist einfach ein Array von Funktionszeigern, man kann sich eine Sprungtabelle ungefähr so ​​vorstellen:

int (*functions[10])(); /* Array of 10 Function Pointers */

Nach meinem Verständnis wird dies mit einer case-Anweisung wie folgt verwendet: Jede Bedingung, case _, wird ein Index in diesem Array sein, also zum Beispiel:

switch( a ) {
    case 1:  // (*functions[1])() // Call function containing actions in case of 1
        ...  
    case 2:  // (*functions[2])() // Call function containing actions in case of 2
        ...

Jeder Fall verwandelt sich in einfache Funktionen[a]. Dies bedeutet, dass auf Funktionen zugegriffen wird[9] ist genauso schnell wie der Zugriff auf Funktionen[1]. Geben Sie die O (1) Zeit, die Sie erwähnt haben.

Wenn Sie Fall 1 und Fall 4907 haben, ist dies offensichtlich keine gute Methode, und die von Ihnen erwähnten Hash-Tabellen- / Wörterbuchmethoden können ins Spiel kommen.

Um Jerrys Antwort und andere weiter auszuführen

Gegeben:

int x=1;
switch (i) {
   case 1: x=6; break;
   case 2: x++;
   // Fall through
   case 3: x+=7; break;
}

du könntest so etwas haben:

int f1() {return 6;}
int f2() {return 1+f3();}
int f3() {return 8;}

Der Compiler könnte eine Sprungtabelle zum Indizieren verwenden {f1, f2, f3}

Der Compiler kann beim Erstellen der Tabelle Inlining durchführen f1, f2, f3 Einstellung x direkt zu 6,9,8

Aber wenn Sie die Funktionen geschrieben und Ihre eigene Sprungtabelle gewürfelt haben, f1,f2,f3 könnte überall sein, aber der Compiler wird wissen, dass er sie in die Nähe von setzen muss switch Erstellen einer viel besseren Codelokalität als Sie könnten.

Beachten Sie, dass der Compiler in vielen Fällen einen Wächter generiert, um dies zu überprüfen i in Reichweite ist (oder um die default) und wenn Sie sicher sind, dass es immer einer der Fälle ist, können Sie das überspringen

Das Interessante ist, dass für unter einer kleinen Anzahl von Fällen und unter verschiedenen Compiler-Flags (Compiler-abhängig) die switch würde keine Tabelle verwenden, sondern nur ifs, ähnlich wie:

if (i==1) x=f1();
else if (i==2) x=f2();
else if (i==3) x=f3();

oder es könnte dies optimieren (wobei einfache Tests eine Anweisung sind):

x=(i==1) ? f1()
: (i==2) ? f2()
: (i==3) ? f3()
: x;

Der beste Rat ist, sich die generierte Assembly anzusehen, um zu sehen, was der Compiler mit Ihrem Code auf Ihrer Architektur gemacht hat. G++ unter Linux/Intel generiert so etwas wie das Folgende, wenn es eine Sprungtabelle gibt

(Beachten Sie, dass ich zu 5 gehen musste case Anweisungen, um die Sprungtabelle zu erzwingen, wurden ifs unterhalb dieser Anzahl von verwendet case Aussagen)

Beachten Sie, dass kleine Löcher in der Sprungtabelle sein werden, um dies zu tun default

int foo(int i)
{
   int x=1;
   switch (i) {
       case 1: x=6; break;
       case 2: x++;
        // Fall through
       case 3: x+=7; break;
       case 4: x+=2; break;
       case 5: x+=9; break;
    }
  return x;
}

würde den folgenden Assemblercode generieren (// Kommentare sind von mir):

        cmp     edi, 5                     //make sure it is not over 5
        ja      .L2                        //jump to default case
        mov     edi, edi
        jmp     [QWORD PTR .L4[0+rdi*8]]   // use the jump table at label L4:
.L4:
        .quad   .L2                        // if i=0, set x=1 (default)
        .quad   .L9                        // f1() see below
        .quad   .L10                       // f2() see below
        .quad   .L6                        // f3() see below
        .quad   .L7                        // f4() see below
        .quad   .L8                        // f5() see below
.L10:
        mov     eax, 9                     // x=9
        ret
.L9:
        mov     eax, 6                     // x=6
        ret
.L8:
        mov     eax, 10                    // x=10
        ret
.L6:
        mov     eax, 8                     // x=8
        ret
.L7:
        mov     eax, 3                     // x=3
        ret
.L2:
        mov     eax, 1                     // default, x was 1, noop is: x=1
        ret