Question sur le boîtier du commutateur de la table de saut

Question

J'essaie de comprendre certaines choses sur les tables de saut et leur relation avec une déclaration de cas de commutation.

On m'a dit qu'une table de saut est une structure O(1) que le compilateur génère et qui rend la recherche de valeurs essentiellement aussi rapide que possible. Cependant, dans certains cas, une table de hachage/dictionnaire peut être plus rapide. On m'a également dit que cela ne fonctionnera que si le switch case contient ordered les valeurs des données.

Quelqu'un peut-il confirmer ou infirmer cette affirmation et expliquer ce qu'est une table de saut, son importance et sa complexité par rapport à l'utilisation d'un dictionnaire ou d'une table de hachage ? Merci.

Answer 1

Pour approfondir la question Réponse de Jerry et autres

Étant donné :

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

vous pourriez avoir quelque chose comme ce qui suit :

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

Le compilateur pourrait utiliser une table de saut pour indexer {f1, f2, f3}

Le compilateur peut faire de l'inlining lors de la création de la table ayant f1, f2, f3 paramètre x directement à 6,9,8

Mais si tu écrivais les fonctions, et que tu créais ta propre table de saut, f1,f2,f3 peuvent être n'importe où, mais le compilateur saura les placer près de la balise switch créant une localité de code bien meilleure que vous ne pourriez le faire.

Notez que dans de nombreux cas, le compilateur générera un garde pour vérifier si i est dans la plage (ou pour gérer le default ) et si vous êtes sûr qu'il s'agit toujours de l'un des cas, vous pouvez sauter l'élément

Ce qui est intéressant, c'est que dans un petit nombre de cas, et sous différents drapeaux de compilateur (dépendant du compilateur), la fonction switch n'utiliserait pas de tableau, mais ferait juste des si, comme :

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

ou il pourrait optimiser cela (où les tests simples sont une instruction) pour :

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

Le meilleur conseil est de regarder l'assemblage généré pour voir ce que le compilateur a fait à votre code sur votre architecture, g++ sur Linux/intel va générer quelque chose comme ce qui suit, s'il y a une table de saut

( note que j'ai dû aller jusqu'à 5 case pour forcer la table de saut, il a utilisé des ifs en dessous de ce nombre de case déclarations )

Notez que de petits trous seront dans la table de saut pour faire le 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;
}

générerait le code d'assemblage suivant ( // les commentaires sont les miens ) :

        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