Le «changement» est-il plus rapide que «si»?

242

Une switchdéclaration est-elle réellement plus rapide qu'une ifdéclaration?

J'ai exécuté le code ci-dessous sur le compilateur C ++ x64 de Visual Studio 2010 avec l' /Oxindicateur:

#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 de commutation: 5261 ms Instruction If: 5196 ms

D'après ce que j'ai appris, les switchinstructions utilisent apparemment des tables de saut pour optimiser la ramification.

Des questions:

  1. À quoi ressemblerait une table de saut de base, en x86 ou x64?

  2. Ce code utilise-t-il une table de saut?

  3. Pourquoi n'y a-t-il aucune différence de performances dans cet exemple? Existe-t-il une situation dans laquelle il existe une différence de performances significative?


Démontage 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       

Mettre à jour:

Des résultats intéressants ici . Je ne sais pas pourquoi on est plus rapide et plus lent, cependant.

user541686
la source
47
Que diable les gens votent-ils pour clore cette réflexion? Sont-ils tellement convaincus de la notion de compilateur parfaitement optimisant que toute idée de sa génération de code non idéal est une hérésie? L'idée même d' une optimisation n'importe où les offense-t-elle?
Crashworks
6
Quel est exactement le problème avec cette question?
Tugrul Ates
25
Pour tous ceux qui se demandent ce qui ne va pas avec cette question : Pour commencer, ce n'est pas une question, c'est 3 questions, ce qui signifie que la plupart des réponses abordent maintenant différents problèmes. Cela signifie qu'il sera difficile d'accepter une réponse qui réponde à tout . De plus, la réaction habituelle à la question ci-dessus est de la fermer comme "pas vraiment intéressante", principalement en raison du fait qu'à ce niveau d'optimisation, vous optimisez presque toujours prématurément . Enfin, 5196 contre 5261 ne devrait pas être suffisant pour réellement s'en soucier. Écrivez le code logique qui a du sens.
Lasse V. Karlsen
40
@Lasse: Auriez-vous vraiment préféré que je poste trois questions sur SO à la place? Aussi: 5196 vs. 5261 shouldn't be enough to actually care-> Je ne sais pas si vous avez mal compris la question ou si j'ai mal compris votre commentaire, mais ce n'est pas tout l'intérêt de ma question de demander pourquoi il n'y a pas de différence? (Ai-je jamais prétendu que
c'était
5
@Robert: Eh bien, il ne contient que plus de 20 commentaires, car ce sont des méta-commentaires. Il n'y a que 7 commentaires liés à la question ici. Opinion: Je ne vois pas comment il y a "opinion" ici. Il y a une raison pour laquelle je ne vois pas de différence de performances, non? Est-ce juste du goût? Débat: Peut-être, mais cela ressemble à un genre de débat sain pour moi, comme je l'ai vu à d'autres endroits sur SO (faites-moi savoir s'il y a quelque chose qui s'y oppose). Arguments: Je ne vois rien d'argumentaire ici (sauf si vous le prenez comme synonyme de «débat»?). Discussion approfondie: si vous incluez ces méta-commentaires.
user541686

Réponses:

122

Il existe plusieurs optimisations qu'un compilateur peut effectuer sur un commutateur. Je ne pense pas que la "table de saut" souvent mentionnée soit très utile, car elle ne fonctionne que lorsque l'entrée peut être limitée d'une manière ou d'une autre.

C Le pseudocode pour une "table de sauts" serait quelque chose comme ceci - notez que le compilateur devrait en pratique insérer une forme de test if autour de la table pour s'assurer que l'entrée était valide dans la table. Notez également que cela ne fonctionne que dans le cas spécifique où l'entrée est une série de nombres consécutifs.

Si le nombre de branches dans un commutateur est extrêmement élevé, un compilateur peut faire des choses comme utiliser la recherche binaire sur les valeurs du commutateur, ce qui (dans mon esprit) serait une optimisation beaucoup plus utile, car cela augmente considérablement les performances de certains scénarios, est aussi général qu'un commutateur et n'entraîne pas une plus grande taille de code généré. Mais pour voir cela, votre code de test aurait besoin de beaucoup plus de branches pour voir toute différence.

Pour répondre à vos questions spécifiques:

  1. Clang en génère un qui ressemble à ceci :

    test_switch(char):                       # @test_switch(char)
            movl    %edi, %eax
            cmpl    $19, %edi
            jbe     .LBB0_1
            retq
    .LBB0_1:
            jmpq    *.LJTI0_0(,%rax,8)
            jmp     void call<0u>()         # TAILCALL
            jmp     void call<1u>()         # TAILCALL
            jmp     void call<2u>()         # TAILCALL
            jmp     void call<3u>()         # TAILCALL
            jmp     void call<4u>()         # TAILCALL
            jmp     void call<5u>()         # TAILCALL
            jmp     void call<6u>()         # TAILCALL
            jmp     void call<7u>()         # TAILCALL
            jmp     void call<8u>()         # TAILCALL
            jmp     void call<9u>()         # TAILCALL
            jmp     void call<10u>()        # TAILCALL
            jmp     void call<11u>()        # TAILCALL
            jmp     void call<12u>()        # TAILCALL
            jmp     void call<13u>()        # TAILCALL
            jmp     void call<14u>()        # TAILCALL
            jmp     void call<15u>()        # TAILCALL
            jmp     void call<16u>()        # TAILCALL
            jmp     void call<17u>()        # TAILCALL
            jmp     void call<18u>()        # TAILCALL
            jmp     void call<19u>()        # TAILCALL
    .LJTI0_0:
            .quad   .LBB0_2
            .quad   .LBB0_3
            .quad   .LBB0_4
            .quad   .LBB0_5
            .quad   .LBB0_6
            .quad   .LBB0_7
            .quad   .LBB0_8
            .quad   .LBB0_9
            .quad   .LBB0_10
            .quad   .LBB0_11
            .quad   .LBB0_12
            .quad   .LBB0_13
            .quad   .LBB0_14
            .quad   .LBB0_15
            .quad   .LBB0_16
            .quad   .LBB0_17
            .quad   .LBB0_18
            .quad   .LBB0_19
            .quad   .LBB0_20
            .quad   .LBB0_21
    
  2. Je peux dire qu'il n'utilise pas de table de saut - 4 instructions de comparaison 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) 
    

    Une solution basée sur une table de saut n'utilise pas du tout de comparaison.

  3. Soit pas assez de branches pour que le compilateur génère une table de sauts, soit votre compilateur ne les génère tout simplement pas. Je ne sais pas lequel.

EDIT 2014 : Il y a eu des discussions ailleurs de personnes familières avec l'optimiseur LLVM disant que l'optimisation de la table de saut peut être importante dans de nombreux scénarios; par exemple dans les cas où il y a une énumération avec de nombreuses valeurs et de nombreux cas contre des valeurs dans ladite énumération. Cela dit, je maintiens ce que j'ai dit ci-dessus en 2011 - trop souvent, je vois des gens penser "si je fais un changement, ce sera la même chose, peu importe le nombre de cas que j'ai" - et c'est complètement faux. Même avec une table de saut, vous obtenez le coût de saut indirect et vous payez les entrées dans la table pour chaque cas; et la bande passante mémoire est un gros problème sur le matériel moderne.

Écrivez le code pour la lisibilité. Tout compilateur digne de ce nom va voir une échelle if / else if et le transformer en commutateur équivalent ou vice versa s'il serait plus rapide de le faire.

Billy ONeal
la source
3
+1 pour avoir répondu à la question et pour des informations utiles. :-) Cependant, une question: D'après ce que je comprends, une table de saut utilise des sauts indirects ; Est-ce exact? Si tel est le cas, cela n'est-il généralement pas plus lent en raison d'une prélecture / pipelining plus difficile?
user541686
1
@Mehrdad: Oui, il utilise des sauts indirects. Cependant, un saut indirect (avec le décrochage du pipeline qui l'accompagne) peut être inférieur à des centaines de sauts directs. :)
Billy ONeal
1
@Mehrdad: Non, malheureusement. :( Je suis content d'être dans le camp des gens qui pensent toujours que la FI est plus lisible! :)
Billy ONeal
1
Quelques quips - "[commutateurs] ne fonctionne que lorsque l'entrée peut être limitée d'une certaine manière" "doivent insérer une forme de test si autour de la table pour s'assurer que l'entrée était valide dans la table. Notez également qu'elle ne fonctionne que dans la zone spécifique cas où l'entrée est une série de nombres consécutifs. ": il est tout à fait possible d'avoir une table peu peuplée, où le pointeur potentiel est lu et uniquement si un non-NULL est un saut effectué, sinon le cas par défaut s'il y en a un, puis les switchsorties. Soren a dit plusieurs autres choses que je voulais dire après avoir lu cette réponse.
Tony Delroy
2
"Tout compilateur digne de ce nom va voir une échelle if / else if et le transformer en commutateur équivalent ou vice versa" - un support pour cette affirmation? un compilateur peut supposer que l'ordre de vos ifclauses a déjà été réglé à la main pour correspondre à la fréquence et aux besoins de performances relatives, où, comme cela switchest traditionnellement considéré comme une invitation ouverte à l'optimisation, selon le choix du compilateur. Bon point re sautant passé switch:-). La taille du code dépend des cas / plage - pourrait être meilleure. Enfin, certains énumérations, champs de bits et charscénarios sont intrinsèquement valides / limités et sans frais généraux.
Tony Delroy
47

A votre question:

1. À quoi ressemblerait une table de saut de base, en x86 ou x64?

La table de saut est une adresse mémoire qui contient un pointeur sur les étiquettes dans quelque chose comme la structure d'un tableau. l'exemple suivant vous aidera à comprendre comment les tables de saut sont disposées

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

entrez la description de l'image ici

00B14538 est le pointeur vers la table de sauts et une valeur comme D8 09 AB 00 représente le pointeur d'étiquette.

2.Ce code utilise-t-il une table de saut? Non dans ce cas.

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

Il n'y a pas de différence de performances car les instructions pour les deux cas sont identiques, pas de table de saut.

4.Y a-t-il une situation dans laquelle il existe une différence de performance significative?

Si vous avez une très longue séquence de vérification if , dans ce cas, l'utilisation d'une table de saut améliore les performances (les instructions de branchement / jmp sont coûteuses si elles ne prédisent pas presque parfaitement) mais s'accompagnent du coût de la mémoire.

Le code de toutes les instructions de comparaison a également une certaine taille, donc en particulier avec les pointeurs ou les décalages 32 bits, une recherche de table de saut unique peut ne pas coûter beaucoup plus de taille dans un exécutable.

Conclusion: le compilateur est assez intelligent pour gérer un tel cas et générer des instructions appropriées :)

crypté
la source
(edit: nvm, la réponse de Billy a déjà ce que je suggérais. Je suppose que c'est un bon complément.) Il serait bon d'inclure la gcc -Ssortie: une séquence d' entrées .long L1/ .long L2table est plus significative qu'un hexdump, et plus utile à quelqu'un qui veut apprendre à regarder le compilateur. (Bien que je suppose que vous regardiez simplement le code du commutateur pour voir s'il s'agissait d'un jmp indirect ou d'un tas de jcc).
Peter Cordes
31

Le compilateur est libre de compiler l'instruction switch en tant que code équivalent à l'instruction if, ou de créer une table de raccourcis. Il choisira probablement l'un sur l'autre en fonction de ce qui s'exécutera le plus rapidement ou générera un peu le plus petit code en fonction de ce que vous avez spécifié dans les options de votre compilateur - dans le pire des cas, ce sera la même vitesse que les instructions if

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

Si le nombre de cas devient très important, une table de sauts sera beaucoup plus rapide qu'une série de if. Cependant, si les étapes entre les valeurs sont très grandes, la table de sauts peut devenir grande et le compilateur peut choisir de ne pas en générer une.

Soren
la source
13
Je ne pense pas que cela réponde à la question du PO. Du tout.
Billy ONeal
5
@ Soren: Si c'était la "question de base", je n'aurais pas pris la peine de traiter les 179 autres lignes de la question, cela n'aurait été qu'une ligne. :-)
user541686
8
@ Soren: Je vois au moins 3 sous-questions numérotées dans le cadre de la question du PO. Vous avez simplement claironné la même réponse exacte qui s'applique à toutes les questions de «performance» - à savoir que vous devez d'abord mesurer. Considérez que peut-être Mehrdad a déjà mesuré et a isolé ce morceau de code pour être un point chaud. Dans de tels cas, votre réponse est pire que sans valeur, c'est du bruit.
Billy ONeal
2
Il y a une ligne floue entre ce qu'est une table de saut et ce qui ne dépend pas de votre définition. J'ai fourni des informations sur la sous-question, partie 3.
Soren
2
@wnoise: Si c'est la seule bonne réponse, il n'y aurait jamais de raison de poser une question sur les performances. Cependant, certains d'entre nous dans le monde réel mesurent notre logiciel, et nous ne savons parfois pas comment accélérer un morceau de code une fois qu'il a été mesuré. Il est évident que Mehrdad a fait quelques efforts sur cette question avant de la poser; et je pense que ses questions spécifiques sont plus que répondables.
Billy ONeal
13

Comment savez-vous que votre ordinateur n'effectuait pas de tâche sans rapport avec le test pendant la boucle de test du commutateur et effectuait moins de tâches pendant la boucle de test if? Vos résultats de test ne montrent rien comme:

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

Mes résultats:

J'ai ajouté:

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

à la fin afin qu'il n'optimise pas la boucle car le compteur n'a jamais été utilisé dans votre exemple, alors pourquoi le compilateur effectuerait-il la boucle? Immédiatement, le commutateur a toujours été gagnant même avec un tel micro-benchmark.

L'autre problème avec votre code est:

switch (counter % 4 + 1)

dans votre boucle de commutation, contre

const size_t c = counter % 4 + 1; 

dans votre boucle if. Très grande différence si vous corrigez cela. Je crois que mettre la déclaration à l'intérieur de la déclaration switch provoque le compilateur à envoyer la valeur directement dans les registres CPU plutôt que de la mettre d'abord sur la pile. Ceci est donc en faveur de la déclaration switch et non d'un test équilibré.

Oh et je pense que vous devriez également réinitialiser le compteur entre les tests. En fait, vous devriez probablement utiliser une sorte de nombre aléatoire au lieu de +1, +2, +3, etc., car cela optimisera probablement quelque chose là-bas. Par nombre aléatoire, je veux dire un nombre basé sur l'heure actuelle, par exemple. Sinon, le compilateur pourrait transformer vos deux fonctions en une seule opération mathématique longue sans même vous soucier de boucles.

J'ai modifié le code de Ryan juste assez pour m'assurer que le compilateur ne pouvait pas comprendre les choses avant l'exécution du code:

#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

(résultats similaires sur plusieurs tentatives)

J'ai également réduit le nombre de cas / ifs à 5 et la fonction de commutation est toujours gagnante.

BobTurbo
la source
Idk, je ne peux pas le prouver; obtenez-vous des résultats différents?
user541686
+1: L'analyse comparative est difficile, et vous ne pouvez vraiment pas tirer de conclusions d'une petite différence de temps sur une seule exécution sur un ordinateur normal. Vous pouvez essayer d'exécuter un grand nombre de tests et de faire des statistiques sur les résultats. Ou compter les cycles du processeur sur une exécution contrôlée dans un émulateur.
Thomas Padron-McCarthy
Euh, où exactement avez-vous ajouté la printdéclaration? Je l'ai ajouté à la fin de l'ensemble du programme et je n'ai vu aucune différence. Je ne comprends pas non plus quel est le "problème" avec l'autre ... l'esprit d'expliquer quelle est la "très grande différence"?
user541686
1
@BobTurbo: 45983493 est sur 12 heures. C'était une faute de frappe?
Gus
1
super, maintenant je dois recommencer :)
BobTurbo
7

Un bon compilateur d'optimisation tel que MSVC peut générer:

  1. une simple table de saut si les cas sont disposés dans une belle longue portée
  2. une table de saut clairsemée (à deux niveaux) s'il y a beaucoup de lacunes
  3. une série de ifs si le nombre de cas est petit ou si les valeurs ne sont pas rapprochées
  4. une combinaison de ce qui précède si les cas représentent plusieurs groupes de plages étroitement espacées.

En bref, si le commutateur semble plus lent qu'une série d'if, le compilateur peut simplement le convertir en un. Et il est probable que ce ne soit pas seulement une séquence de comparaisons pour chaque cas, mais un arbre de recherche binaire. Voir ici pour un exemple.

Igor Skochinsky
la source
En fait, un compilateur est également en mesure de le remplacer par un hachage et un saut, qui fonctionne mieux que la solution à deux niveaux clairsemée que vous proposez.
Alice
5

Je vais répondre 2) et faire quelques commentaires généraux. 2) Non, il n'y a pas de table de saut dans le code d'assemblage que vous avez publié. Une table de saut est une table de destinations de saut et une ou deux instructions pour passer directement à un emplacement indexé à partir de la table. Une table de saut aurait plus de sens lorsqu'il existe de nombreuses destinations de commutation possibles. Peut-être que l'optimiseur sait que la logique simple sinon, est plus rapide, sauf si le nombre de destinations est supérieur à un certain seuil. Essayez à nouveau votre exemple avec disons 20 possibilités au lieu de 4.

Bill Forster
la source
+1 merci pour la réponse à # 2! :) (Btw, voici les résultats avec plus de possibilités.)
user541686
4

J'étais intrigué et j'ai regardé ce que je pouvais changer dans votre exemple pour lui permettre d'exécuter l'instruction switch plus rapidement.

Si vous obtenez 40 instructions if et ajoutez un cas 0, le bloc if s'exécutera plus lentement que l'instruction switch équivalente. J'ai les résultats ici: https://www.ideone.com/KZeCz .

L'effet de la suppression du cas 0 peut être vu ici: https://www.ideone.com/LFnrX .

Ryan Gross
la source
1
Vos liens sont tombés en panne.
TS
4

Voici quelques résultats de l'ancien benchmark bench ++ benchmark:

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

Ce que nous pouvons en voir, c'est que (sur cette machine, avec ce compilateur - VC ++ 9.0 x64), chaque iftest prend environ 0,7 nanosecondes. À mesure que le nombre de tests augmente, les échelles de temps sont presque parfaitement linéaires.

Avec l'instruction switch, il n'y a presque pas de différence de vitesse entre un test à 2 voies et un test à 10 voies, tant que les valeurs sont denses. Le test à 10 voies avec des valeurs clairsemées prend environ 1,6 fois plus de temps que le test à 10 voies avec des valeurs denses - mais même avec des valeurs clairsemées, c'est toujours mieux que le double de la vitesse d'un 10 voies if/ else if.

Conclusion: utiliser uniquement un test à 4 voies ne vous montrera pas vraiment beaucoup sur les performances de switchvs if/ else. Si vous regardez les chiffres de ce code, il est assez facile d'interpoler le fait que pour un test à 4 voies, nous nous attendrions à ce que les deux produisent des résultats assez similaires (~ 2,8 nanosecondes pour un if/ else, ~ 2,0 pour switch).

Jerry Coffin
la source
1
Un peu difficile de savoir quoi faire de cela si nous ne savons pas si le test recherche délibérément une valeur qui ne correspond pas ou qui ne correspond qu'à la fin de la chaîne if/ par elserapport à leur diffusion, etc. Impossible de trouver les bench++sources après 10 minutes googler.
Tony Delroy
3

Notez que lorsqu'un commutateur n'est PAS compilé dans une table de saut, vous pouvez très souvent écrire if plus efficacement que le commutateur ...

(1) si les cas ont un ordre, plutôt que le pire des tests pour tous les N, vous pouvez écrire vos if pour tester si dans la moitié supérieure ou inférieure, puis dans chaque moitié de cela, style de recherche binaire ... résultant en le pire des cas étant logN plutôt que N

(2) si certains cas / groupes sont beaucoup plus fréquents que d'autres cas, alors la conception de vos if pour isoler ces cas en premier peut accélérer le temps moyen à travers

Brian Kennedy
la source
Ceci est nettement faux; les compilateurs sont plus que capables de faire LES DEUX optimisations.
Alice
1
Alice, comment un compilateur est-il censé savoir quels cas se produiront plus fréquemment que d'autres cas dans vos charges de travail attendues? (A: Il ne peut pas savoir, donc il ne peut pas faire une telle optimisation.)
Brian Kennedy
(1) peut être fait facilement, et se fait dans certains compilateurs, simplement en faisant une recherche binaire. (2) peut être prédit de différentes manières ou indiqué au compilateur. N'avez-vous jamais utilisé «probable» ou «improbable» de GCC?
Alice
Et certains compilateurs permettent d'exécuter le programme dans un mode qui collecte des statistiques, puis optimise à partir de ces informations.
Phil1970
2

Non, ce sont si alors sauter autrement si alors sauter autre ... Une table de saut aurait une table d'adresses ou utiliserait un hachage ou quelque chose comme ça.

Plus rapide ou plus lent est subjectif. Vous pourriez par exemple avoir le cas 1 comme dernière chose au lieu de la première et si votre programme de test ou programme réel a utilisé le cas 1 la plupart du temps, le code serait plus lent avec cette implémentation. Donc, simplement réorganiser la liste des cas, selon la mise en œuvre, peut faire une grande différence.

Si vous aviez utilisé les cas 0-3 au lieu de 1-4, le compilateur aurait peut-être utilisé une table de sauts, le compilateur aurait dû de toute façon supprimer votre +1. C'était peut-être le petit nombre d'articles. Si vous l'aviez fait 0 - 15 ou 0 - 31 par exemple, il peut l'avoir implémenté avec une table ou utilisé un autre raccourci. Le compilateur est libre de choisir comment il implémente les choses tant qu'il répond aux fonctionnalités du code source. Et cela entre dans les différences du compilateur et les différences de version et les différences d'optimisation. Si vous voulez une table de saut, faites une table de saut, si vous voulez un arbre si-alors-sinon faites un arbre si-alors-autre. Si vous voulez que le compilateur décide, utilisez une instruction switch / case.

old_timer
la source
2

Je ne sais pas pourquoi on est plus rapide et plus lent, cependant.

Ce n'est en fait pas trop difficile à expliquer ... Si vous vous souvenez que les branches mal prédites sont des dizaines à des centaines de fois plus chères que les branches correctement prédites.

Dans la % 20version, le premier cas / if est toujours celui qui frappe. Les processeurs modernes "apprennent" quelles branches sont généralement prises et lesquelles ne le sont pas, de sorte qu'elles peuvent facilement prédire comment cette branche se comportera à presque chaque itération de la boucle. Cela explique pourquoi la version "si" vole; il n'a jamais à exécuter quoi que ce soit après le premier test et il prédit (correctement) le résultat de ce test pour la plupart des itérations. De toute évidence, le «commutateur» est implémenté légèrement différemment - peut-être même une table de saut, qui peut être lente grâce à la branche calculée.

Dans la % 21version, les branches sont essentiellement aléatoires. Ainsi, non seulement beaucoup d'entre eux exécutent chaque itération, mais le processeur ne peut pas deviner dans quelle direction ils iront. C'est le cas où une table de saut (ou une autre optimisation de «commutateur») est susceptible de vous aider.

Il est très difficile de prédire comment un morceau de code va fonctionner avec un compilateur et un processeur modernes, et cela devient plus difficile à chaque génération. Le meilleur conseil est "ne vous embêtez même pas à essayer; faites toujours le profil". Ce conseil s'améliore - et le nombre de personnes qui peuvent l'ignorer avec succès diminue - chaque année.

Tout cela pour dire que mon explication ci-dessus est en grande partie une supposition. :-)

Nemo
la source
2
Je ne vois pas d'où peuvent venir des centaines de fois plus lentement. Le pire cas d'une branche mal prévue est un blocage de pipeline, qui serait ~ 20 fois plus lent sur la plupart des processeurs modernes. Pas des centaines de fois. (D'accord, si vous utilisez une ancienne puce NetBurst, elle pourrait être 35 fois plus lente ...)
Billy ONeal
@Billy: OK, donc je regarde un peu vers l'avenir. Sur les processeurs de Sandy Bridge , «chaque branche mal prévue videra tout le pipeline, perdant ainsi le travail d'une centaine d'instructions en vol». Les pipelines deviennent vraiment plus profonds à chaque génération, en général ...
Nemo
1
Pas vrai. Le P4 (NetBurst) avait 31 étages de pipeline; Sandy Bridge a beaucoup moins d'étapes. Je pense que la "perte du travail d'une centaine d'instructions" repose sur l'hypothèse que le cache d'instructions est invalidé. Pour un saut indirect général qui se produit en fait, mais pour quelque chose comme une table de saut, il est probable que la cible du saut indirect se trouve quelque part dans le cache d'instructions.
Billy ONeal
@Billy: Je ne pense pas que nous soyons en désaccord. Ma déclaration était: "Les branches mal prévues sont des dizaines à des centaines de fois plus chères que les branches correctement prévues". Une légère exagération, peut-être ... Mais il se passe plus que de simples hits dans la profondeur du pipeline I et du pipeline d'exécution; d'après ce que j'ai lu, la file d'attente pour le décodage seul est d'environ 20 instructions.
Nemo
Si le matériel de prédiction de branche prédit de manière erronée le chemin d'exécution, les uops du chemin incorrect qui se trouvent dans le pipeline d'instructions sont simplement supprimés là où ils se trouvent, sans bloquer l'exécution. Je ne sais pas comment cela est possible (ou si je l'interprète de manière erronée), mais apparemment il n'y a pas de blocage de pipeline avec des succursalesmalprévues à Nehalem? (Là encore, je n'ai pas de i7; j'ai un i5, donc cela ne s'applique pas à mon cas.)
user541686
1

Aucun. Dans la plupart des cas particuliers, lorsque vous entrez dans l'assembleur et effectuez de véritables mesures de performances, votre question est tout simplement erronée. Pour l'exemple donné, votre réflexion est définitivement trop courte car

counter += (4 - counter % 4);

me semble être l'expression d'incrémentation correcte que vous devriez utiliser.

Jens Gustedt
la source