Est "switch" plus vite que les "si"?

Question

Est un switch déclaration en fait plus vite que l' if déclaration?

J'ai couru le code ci-dessous sur Visual Studio 2010 x64 compilateur C++ avec l' /Ox drapeau:

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

#define MAX_COUNT (1 << 29)
size_t counter = 0;

size_t testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        switch (counter % 4 + 1)
        {
            case 1: counter += 4; break;
            case 2: counter += 3; break;
            case 3: counter += 2; break;
            case 4: counter += 1; break;
        }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

size_t testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = counter % 4 + 1;
        if (c == 1) { counter += 4; }
        else if (c == 2) { counter += 3; }
        else if (c == 3) { counter += 2; }
        else if (c == 4) { counter += 1; }
    }
    return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    printf("Starting...\n");
    printf("Switch statement: %u ms\n", testSwitch());
    printf("If     statement: %u ms\n", testIf());
}

et a obtenu ces résultats:

Instruction Switch: 5261 ms
Si la déclaration: 5196 ms

De ce que j'ai appris, switch des déclarations apparemment utilisation sauter tables pour optimiser la ramification.

Questions:

1. Que serait un base jump de la table ressembler, en x86 ou x64?

2. Est ce code à l'aide d'un saut de la table?

3. Pourquoi il n'y a pas de différence de performances dans cet exemple? Est-il de la situation dans laquelle il n'y est une différence de performances significative?

---

Désassemblage du code:

testIf:

13FE81B10 sub  rsp,48h 
13FE81B14 call qword ptr [__imp_clock (13FE81128h)] 
13FE81B1A mov  dword ptr [start],eax 
13FE81B1E mov  qword ptr [i],0 
13FE81B27 jmp  testIf+26h (13FE81B36h) 
13FE81B29 mov  rax,qword ptr [i] 
13FE81B2E inc  rax  
13FE81B31 mov  qword ptr [i],rax 
13FE81B36 cmp  qword ptr [i],20000000h 
13FE81B3F jae  testIf+0C3h (13FE81BD3h) 
13FE81B45 xor  edx,edx 
13FE81B47 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B4E mov  ecx,4 
13FE81B53 div  rax,rcx 
13FE81B56 mov  rax,rdx 
13FE81B59 inc  rax  
13FE81B5C mov  qword ptr [c],rax 
13FE81B61 cmp  qword ptr [c],1 
13FE81B67 jne  testIf+6Dh (13FE81B7Dh) 
13FE81B69 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B70 add  rax,4 
13FE81B74 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B7B jmp  testIf+0BEh (13FE81BCEh) 
13FE81B7D cmp  qword ptr [c],2 
13FE81B83 jne  testIf+89h (13FE81B99h) 
13FE81B85 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81B8C add  rax,3 
13FE81B90 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81B97 jmp  testIf+0BEh (13FE81BCEh) 
13FE81B99 cmp  qword ptr [c],3 
13FE81B9F jne  testIf+0A5h (13FE81BB5h) 
13FE81BA1 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BA8 add  rax,2 
13FE81BAC mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BB3 jmp  testIf+0BEh (13FE81BCEh) 
13FE81BB5 cmp  qword ptr [c],4 
13FE81BBB jne  testIf+0BEh (13FE81BCEh) 
13FE81BBD mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81BC4 inc  rax  
13FE81BC7 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81BCE jmp  testIf+19h (13FE81B29h) 
13FE81BD3 call qword ptr [__imp_clock (13FE81128h)] 
13FE81BD9 sub  eax,dword ptr [start] 
13FE81BDD imul eax,eax,3E8h 
13FE81BE3 cdq       
13FE81BE4 mov  ecx,3E8h 
13FE81BE9 idiv eax,ecx 
13FE81BEB cdqe      
13FE81BED add  rsp,48h 
13FE81BF1 ret       

---

testSwitch:

13FE81C00 sub  rsp,48h 
13FE81C04 call qword ptr [__imp_clock (13FE81128h)] 
13FE81C0A mov  dword ptr [start],eax 
13FE81C0E mov  qword ptr [i],0 
13FE81C17 jmp  testSwitch+26h (13FE81C26h) 
13FE81C19 mov  rax,qword ptr [i] 
13FE81C1E inc  rax  
13FE81C21 mov  qword ptr [i],rax 
13FE81C26 cmp  qword ptr [i],20000000h 
13FE81C2F jae  testSwitch+0C5h (13FE81CC5h) 
13FE81C35 xor  edx,edx 
13FE81C37 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C3E mov  ecx,4 
13FE81C43 div  rax,rcx 
13FE81C46 mov  rax,rdx 
13FE81C49 inc  rax  
13FE81C4C mov  qword ptr [rsp+30h],rax 
13FE81C51 cmp  qword ptr [rsp+30h],1 
13FE81C57 je   testSwitch+73h (13FE81C73h) 
13FE81C59 cmp  qword ptr [rsp+30h],2 
13FE81C5F je   testSwitch+87h (13FE81C87h) 
13FE81C61 cmp  qword ptr [rsp+30h],3 
13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
13FE81C69 cmp  qword ptr [rsp+30h],4 
13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
13FE81C71 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C73 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C7A add  rax,4 
13FE81C7E mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C85 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C87 mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81C8E add  rax,3 
13FE81C92 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81C99 jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81C9B mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CA2 add  rax,2 
13FE81CA6 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CAD jmp  testSwitch+0C0h (13FE81CC0h) 
13FE81CAF mov  rax,qword ptr [counter (13FE835D0h)] 
13FE81CB6 inc  rax  
13FE81CB9 mov  qword ptr [counter (13FE835D0h)],rax 
13FE81CC0 jmp  testSwitch+19h (13FE81C19h) 
13FE81CC5 call qword ptr [__imp_clock (13FE81128h)] 
13FE81CCB sub  eax,dword ptr [start] 
13FE81CCF imul eax,eax,3E8h 
13FE81CD5 cdq       
13FE81CD6 mov  ecx,3E8h 
13FE81CDB idiv eax,ecx 
13FE81CDD cdqe      
13FE81CDF add  rsp,48h 
13FE81CE3 ret       

---

Mise à jour:

Des résultats intéressants ici et ici. Je ne sais pas pourquoi l'un est plus rapide et on est plus lente, bien que.

Answer 1

Il y a plusieurs optimisations du compilateur peut faire sur un interrupteur. Je ne pense pas que le mentionne souvent "sauter-table" est très utile même si, comme il ne fonctionne que quand le signal d'entrée peut être bordée d'une certaine façon.

C Pseudocode pour un "saut de la table" serait quelque chose comme ceci : à noter que le compilateur, dans la pratique, aurait besoin d'insérer une certaine forme de test si autour de la table pour s'assurer que l'entrée était valide dans la table. Notez également qu'il ne fonctionne que dans le cas précis que l'entrée est une série de nombres consécutifs.

En outre, sur les Processeurs modernes, la localité de cache coût de stockage de la table jump peut souvent être plus grande que la élidés SI les tests.

Si le nombre de branches dans un switch est très grand, un compilateur peut faire des choses comme l'utilisation de la recherche binaire sur les valeurs de l'interrupteur, ce qui (dans mon esprit) serait beaucoup plus utile d'optimisation, comme il le fait considérablement augmenter les performances dans certains scénarios, aussi général que d'un interrupteur, et ne conduit pas à une plus grande taille du code généré. Mais de voir que, votre code de test aurait besoin de BEAUCOUP plus de branches de voir la différence.

Pour répondre à vos questions:

1. Je ne sais pas l'assembleur x86, désolé. :(

2. Je peux dire que c'est pas à l'aide d'un saut de la table -- 4 comparaison des instructions sont clairement visibles:

   13FE81C51 cmp  qword ptr [rsp+30h],1 
   13FE81C57 je   testSwitch+73h (13FE81C73h) 
   13FE81C59 cmp  qword ptr [rsp+30h],2 
   13FE81C5F je   testSwitch+87h (13FE81C87h) 
   13FE81C61 cmp  qword ptr [rsp+30h],3 
   13FE81C67 je   testSwitch+9Bh (13FE81C9Bh) 
   13FE81C69 cmp  qword ptr [rsp+30h],4 
   13FE81C6F je   testSwitch+0AFh (13FE81CAFh) 
   

   Un saut de la table de base de la solution de ne pas utiliser de comparaison.

3. Soit pas assez de branches pour cause, le compilateur de générer un saut de table ou de votre compilateur n'a tout simplement pas les générer. Je ne suis pas sûr.

EDIT 2014: Il y a eu un débat d'ailleurs de personnes familières avec le LLVM optimiseur de dire que le saut de la table d'optimisation peut être important dans de nombreux scénarios; par exemple, dans les cas où il y a une énumération avec beaucoup de valeurs et de nombreux cas, contre des valeurs en dit énumération. Cela dit, je maintiens ce que j'ai dit ci-dessus, en 2011 -- trop souvent, je vois des gens qui pensent "si je fais un switch, ça va être le même temps, n'importe comment beaucoup de cas, j'ai" -- et c'est complètement faux. Même avec un saut de table, vous obtenez le saut indirect coût et vous payez pour les entrées dans la table pour chaque cas; et de la bande passante mémoire est une Grosse Affaire sur le matériel moderne.

Écrire du code pour plus de lisibilité. Un compilateur qui vaut son sel est d'aller voir un if / else if échelle et de la transformer en équivalent commutateur ou vice versa, si il serait plus rapide de le faire.

Answer 2

À votre question:

1.Que serait un base jump de la table ressembler, en x86 ou x64?

Sauter de la table est l'adresse mémoire qui contient le pointeur à l'aide d'étiquettes dans quelque chose comme une structure en tableau. l'exemple suivant vous aidera à comprendre comment sauter de la table ressemble

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

Où 00B14538 est le pointeur vers la table de Saut , et de la valeur comme D8 09 AB 00 représente étiquette pointeur.

2.Est ce code à l'aide d'un saut de la table? Non dans ce cas.

3.Pourquoi il n'y a pas de différence de performances dans cet exemple?

Il n'y a pas de différence de performances en raison d'instruction pour les deux cas l'air même, pas de saut de la table.

4.Est-il de la situation dans laquelle il existe une importante différence de performance?

Si vous avez de très longue déclaration de si chèque, dans ce cas, à l'aide de sauter de la table réduit les performances mais cela vient avec le coût de la mémoire.

Devise: le Compilateur est assez intelligent pour gérer de tels cas :)

Answer 3

Le compilateur est libre de compiler l'instruction switch comme un code qui est équivalent à if, ou pour créer un saut de la table. Il sera probablement choisi l'un sur l'autre en fonction de ce qui va exécuter le plus rapide ou de générer le plus petit code un peu en fonction de ce que vous avez spécifié dans vous des options de compilation -- pire des cas, ce sera la même vitesse que si les relevés

Je ferais confiance au compilateur de faire le meilleur choix et se concentrer sur ce qui rend le code plus lisible.

Si le nombre de cas devient très grand saut de la table sera beaucoup plus rapide que celle d'une série de cas. Toutefois, si les étapes entre les valeurs est très grand, alors le saut de la table peut devenir grand, et le compilateur peut choisir de ne pas en générer un.

Answer 4

Comment savez-vous que votre ordinateur n'a pas l'exécution de certaines tâches sans rapport avec le test au cours de l'interrupteur de la boucle de test et d'effectuer moins de tâches au cours de la si la boucle de test? Les résultats ne montrent pas quelque chose comme:

1. la différence est très petite
2. il n'est qu'un résultat, pas une série de résultats
3. il y a trop peu de cas

Mes résultats:

J'ai ajoutées dans:

printf("counter: %u\n", counter);

à la fin de sorte qu'il ne serait pas optimiser loin de la boucle tant que le compteur n'a jamais été utilisé dans votre exemple, alors pourquoi le compilateur d'effectuer la boucle? Immédiatement, l'interrupteur était toujours gagner, même avec un tel micro-benchmark.

L'autre problème avec votre code est:

switch (counter % 4 + 1)

dans votre commutateur de boucle, par rapport à

const size_t c = counter % 4 + 1; 

dans votre cas de la boucle. Très grande différence si vous résoudre ce problème. Je crois que le fait de mettre l'instruction à l'intérieur de l'instruction switch provoque le compilateur à l'envoi de la valeur directement dans les registres du CPU plutôt que de le mettre sur la pile en premier. C'est donc en faveur de l'instruction switch et pas l'équilibre de test.

Oh, et je pense que vous devriez aussi de réinitialisation du compteur entre les tests. En fait, vous devriez être en utilisant une sorte de nombre aléatoire, au lieu de +1, +2, +3, etc, comme il sera probablement optimiser quelque chose. Par nombre aléatoire, je veux dire un certain nombre en fonction de l'heure, par exemple. Sinon, le compilateur pourrait tourner à la fois de vos fonctions dans une longue opération mathématique et même pas la peine avec les boucles.

J'ai modifié Ryan code juste assez pour assurez-vous que le compilateur ne pouvais pas comprendre les choses avant de le code a exécuter:

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

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
} 

commutateur: 3740
si: 3980

(des résultats similaires sur plusieurs tentatives)

J'ai aussi réduit le nombre de cas/fi à 5 et la fonction de commutation encore gagné.

Answer 5

Je vais répondre à 2) et de faire quelques observations générales. 2) Non, il n'y a pas de sauter de la table de l'assemblée dans le code que vous avez posté. Un saut de table est une table de saut destinations, et une ou deux instructions pour accéder directement à un emplacement indexé à partir de la table. Un saut de table aurait plus de sens quand il y a beaucoup de possibilité de passage de destinations. Peut-être que l'optimiseur sait que le plus simple si d'autre logique est plus rapide, sauf si le nombre de destinations est supérieure à un certain seuil. Tentez votre exemple de nouveau à dire 20 les possibilités au lieu de 4.