[C] switch sneller dan intelligente if

[analog_]

Ik zit met een probleem, niet in de exacte definitie maar ik merk iets op wat voor mij onlogisch lijkt. Het gaat dus om de snelheid van een bepaalde methode om tot hetzelfde resultaat te komen, je kan het met een switch doen of met geneste if's. Mij lijkt dat de geneste if's veel sneller moeten zijn omdat laten we het volgende doen : c = (1) ? 2 : 3; waarbij de getallen staan voor de verstreken tijd. Terwijl een switch alle opties overloopt en dus infeite voor elke optie 1 tijdseenheid nodig heeft en dan de juiste 2. Allemaal leuk en wel in theorie, ik zal er wat voorbeeldjes bij plakken :

C:

# include <stdio.h>

int main(void) {
    double i,b;
    int a,x,y;
    for(i=0;i<100000000;i++) {
        for(a=1;a<10;a++) {
            switch(a) {
                case 9 :
                    y=-1;
                    x=-1;
                break;
                case 8 :
                    y=-1;
                    x=0;        
                break;
                case 7 : 
                    y=-1;
                    x=1;
                break;
                case 6 :
                    y=0;
                    x=-1;
                break;
                case 5 :
                    y=0;
                    x=0;
                break;
                case 4 :
                    y=0;
                    x=1;
                break;
                case 3 :
                    y=1;
                    x=-1;
                break;
                case 2 :
                    y=1;
                    x=0;
                break;
                case 1 :
                    y=1;
                    x=1;
                break;
            }
        }
    }
}

C:

# include <stdio.h>

int main(void) {
    double i,b;
    int a,x,y;
    for(i=0;i<100000000;i++) {
        for(a=1;a<10;a++) {
            y = (a > 6) ? -1 : (a<2) ? 1 : 0;
            x = (a%3) ? 1 : ((a+2)%3) ? -1 : 0; 
        }
    }
}

De snelheid meet ik met het time commando op linux (dit compileer ik met GCC 4.1.1 op Gentoo) en draai ik op een Dell Inspiron 6400. De switch draait in een 8 tal seconden en de if structuur in 15 seconden.

[CyBeR]

Hoeveel code je gebruikt is niet heel boeiend qua executietijd bij dit soort dingen. Het gaat om welke CPU-instructies je code oplevert en hoe lang die erover doen om te draaien. En een lijstje met vergelijkingen langslopen gaat nu eenmaal een stuk sneller dan die modulo's die in je tweede voorbeeld zitten.

[ Voor 7% gewijzigd door CyBeR op 27-12-2006 22:32 ]

[Verwijderd]

Ik weet niet echt wat je bedoelt maar een switch loopt niet alles af. Omgezet naar asm jumped hij dan gelijk naar bv case label 6

zoiets (weet niet of het helemaal klopt):
cmp eax, 10
jmp [eax*4+addr]

dat is dan sneller dan die berekeningen

[ Voor 31% gewijzigd door Verwijderd op 27-12-2006 22:39 ]

[latka]

Mr.SiS schreef op woensdag 27 december 2006 @ 22:29:
Ik zit met een probleem, niet in de exacte definitie maar ik merk iets op wat voor mij onlogisch lijkt. Het gaat dus om de snelheid van een bepaalde methode om tot hetzelfde resultaat te komen, je kan het met een switch doen of met geneste if's. Mij lijkt dat de geneste if's veel sneller moeten zijn.

Kijk eens naar de gegenereerde asm (objdump). De compiler optimaliseert de switch waarschijnlijk weg.

C:

switch(a) {
    case 1: bla(); break;
    case 2: bla2(); break;
}

Zal iets worden als:

C:

void *(*fncPtrs) = { bla, bla2; }
*(fncPtr[a])

Oftwel, een switch kun je makkelijk omzetten naar een jumptable.

(tsja, een voorbeeld met code typen duurt langer

[ Voor 3% gewijzigd door latka op 27-12-2006 22:39 ]

[-FoX-]

Ligt niet aan de switch hoor. Je gaat aan de hand van bepaalde "states" beslissingen nemen. Dat is uiteraard sneller dan al dan niet simpele berekeningen te maken om een bepaalde keuze te kunnen maken. Er is zelfs een design pattern die dit gedrag beschrijft "state machine"

[hamsteg]

bovenstaand voorbeeld wordt zeer waarschijnlijk door de compiler omgezet naar een array !!

y[] = { 1,1,1,0,0,0,-1,-1,-1 };
x[] = { 1,0,-1,1,0,-1,1,0,-1};

zo-wie-zo moet je dat op deze manier oplossen maakt de code zeer compact.

edit:
Compact is wat anders als moeilijke constructie

.

[ Voor 18% gewijzigd door hamsteg op 28-12-2006 11:57 ]

[analog_]

latka schreef op woensdag 27 december 2006 @ 22:38:

C:

void *(*fncPtrs) = { bla, bla2; }
*(fncPtr[a])

Ik begin net met C (enfin ik ben er nu twee modules mee bezig). Wat ik begrijp van jullie C/ASM voorbeeldjes (niet dat ik ASM ken). Dat hij het omzet naar een tabel met pointers richting de waardes ?

PHP:

$tabel = array ( 
        1 => array(1,1);
        2 => array(0,0);
        3 => array(1,0);
    );
    
$tabel[$a];

edit:

hamsteg schreef op woensdag 27 december 2006 @ 22:52:...

Ah dit begrijp ik wel volledig. Bedankt

[ Voor 14% gewijzigd door analog_ op 27-12-2006 22:54 ]

[Soultaker]

Toch is dat een wat verkeerde voorstelling van zaken. Wat latka zei klopte beter: de compiler genereert (onder andere) jumps naar codelocaties. In pseudo-BASIC (spreekt misschien wat meer tot de verbeelding) zou het er zo uit zien:

QBasic:

10   A = 1
20   WHILE A < 10
30   IF A < 1 OR A > 9 GOTO 1000
40   GOTO 100*A
100  Y = -1
110  X = -1
120  GOTO 1000
210  Y = -1
220  X = 0
230  GOTO 1000 
-- etc.
1000 A = A + 1
1010 WEND

Verder doet de compiler nog veel meer dingen, die ook invloed hebben op de code die gegenereert wordt. Zo kan 'ie case-clauses die dezelfde werking hebben samenvoegen, bijvoorbeeld. Of hij kan de controle (zie 30) elimineren omdat uit de context duidelijk is dat a altijd tussen 1 en 10 zit.

In de praktijk valt er vaak weinig zinnigs te zeggen over de snelheid van een C programma, als je niet erbij verteld welke compiler je gebruikt hebt, hoe je die configureert, voor welk platform (hardware én software) je compileert, en op welke hardware je test. C-statements tellen zoals je in de TS doet is volstrekt zinloos.

Als ik jouw programma met optimalisaties compileer draait het in een paar miliseconde, omdat de compiler slim genoeg is om al die for-lusjes er helemaal uit te gooien. Je doet immers niets met het resultaat, dus hoeft het programma ze ook niet uit te voeren. (Het programma start op, doet niets, en sluit meteen weer af.) Blijkbaar heb jij een hele rare compiler gebruikt, of die niet goed geconfigureerd.

[RobIII]

Daarbij (en dat wordt vaak vergeten) is 1 asm statement != 1 clockcycle; sommige instructies hebben meer clockcycli nodig dan andere dus als je nested-if's dusdanig worden gecompileerd dat er 1 clockcycle ergens meer gebruikt wordt ondanks minder statements (om maar eens wat te roepen) kan het bij een groot aantal cycli best meetbaar worden
En dan hebben we het nog niet eens gehad over branche-prediction, pipe-line optimizations enzovoorts

[ Voor 13% gewijzigd door RobIII op 28-12-2006 00:19 ]

[Verwijderd]

Maar dan nog is 't mooi dat een stuk goed leesbare code 't een stuk beter doet dan een (allicht knap geschreven) constructie waar maar 1 ding aan mist:

C:

/* you are not supposed to understand this */

[.oisyn]

Houd er ook rekening mee dat modulo en delingen relatief gezien baggertraag zijn.

[Infinitive]

Verwijderd schreef op woensdag 27 december 2006 @ 22:34:
Ik weet niet echt wat je bedoelt maar een switch loopt niet alles af. Omgezet naar asm jumped hij dan gelijk naar bv case label 6

zoiets (weet niet of het helemaal klopt):
cmp eax, 10
jmp [eax*4+addr]

dat is dan sneller dan die berekeningen

Dat is ook weer afhankelijk van diverse zaken, zoals het aantal alternatieven in de switch. Het voorbeeld dat je geeft bevat een indirecte jump - een jump naar een adres wat berekend moet worden - en dat kan bij (moderne) processoren nogal vervelend uitpakken i.v.m. pipeline en cache. Een paar cmp's + jne's is dan weer effectiever (ook weer afhankelijk van branchprediction en dat soort zaken).

Enfin, het is dus zeker zinnig om een switch als een switch op te schrijven i.p.v. het zelf uit te rollen naar ifjes. Dan kan de compiler zelf besluiten wat waarschijnlijk efficienter is. Als je helemaal een performance freak bent dan bestaat er vast wel een of andere pragma waarmee je de keuze kan beinvloeden. Een switch laat iig de mogelijkheden open

[MSalters]

Ik verwacht dat elke compiler die een beetje goed is, een loop unroll doet op de a=[1,10). In dat geval is er simpelweg geen switch meer. Als je nadenkt over de resulterende code, dan snap je ook dat het eerste voorbeeld redelijk belachelijk is. Je hebt alle code al uitgewerkt staan, alleen omdat jij de code van beneden naar boven hebt geschreven heb je nog een for-loop en een switch nodig.

[XTerm]

Het snelheidsverschil heeft bitter weinig te maken met de for loop of de case switch en ALLES met de mod 3 operatie die je daar doet.

Een module neemt op een x86 tussen de 20 en de 40 cycles in en domineert je hele programma.

Neem volgende 3 voorbeelden:

Voorbeeld bm_if:

code:

int main()
{
    int c;
    int Q=0,d=0;
    
    for(c=0;c<100000000;c++){
        if(Q==0)d++;
        if(Q==1)d--;
        if(Q==2)d--;
        if(Q==3)d--;
        if(Q==4)d++;
        if(Q==5)d--;
        if(Q==6)d++;
        if(Q==7)d++;
        if(Q==8)d--;
        if(Q==9)d++;
        Q++;
        if(Q>=10)Q=0;
    }
}

Voorbeeld: bm_sif:

code:

int main()
{
    int c;
    int Q=0,d=0;
    
    for(c=0;c<100000000;c++){
        if(Q==0)d++;
        else if(Q==1)d--;
        else if(Q==2)d--;
        else if(Q==3)d--;
        else if(Q==4)d++;
        else if(Q==5)d--;
        else if(Q==6)d++;
        else if(Q==7)d++;
        else if(Q==8)d--;
        else if(Q==9)d++;
        Q++;
        if(Q>=10)Q=0;
    }
}

En als laatste bm_case:

code:

int main()
{
    int c;
    int Q=0,d=0;
    
    for(c=0;c<100000000;c++){
        switch(Q){
            case 0: d++; break;
            case 1: d--; break;
            case 2: d--; break;
            case 3: d--; break;
            case 4: d++; break;
            case 5: d--; break;
            case 6: d++; break;
            case 7: d++; break;
            case 8: d--; break;
            case 9: d++; break;
        }
        Q++;
        if(Q>=10)Q=0;
    }
}

In deze voorbeelden zit de code tijd echt in de if/case structuur.

Resultaten:

code:

bm_if    2630 ms
bm_sif   1720 ms
bm_case  1080 ms

Het snelheidsverschil tussen bm_if en bm_sif is makkelijk te verklaren, je laat hem minder ifs doen. Het snelheidsverschil is klein omdat de Intel cpu reeds een boel trucs uithaalt om bm_if te optimaliseren, hier zie je de branchpredictor aan het werk, en hij doet zijn werk goed.

Het verschil met de case is te verklaren in de asm code

Dit is bm_sif:

code:

...
.L3:
        cmpl    $0, -12(%ebp)
        jne     .L4
        incl    -8(%ebp)
        jmp     .L6
.L4:
        cmpl    $1, -12(%ebp)
        jne     .L7
        decl    -8(%ebp)
        jmp     .L6
.L7:
        cmpl    $2, -12(%ebp)
        jne     .L9
        decl    -8(%ebp)
        jmp     .L6
...

De waarde wordt gecmpd met een constante, eventueel wordt uit de structuur gesprongen, zo niet wordt de incl of de decl gedaan.

Bij de case zit het zo

code:

    .file   "bm_case.c"
    .text
.globl main
    .type   main, @function
main:
    leal    4(%esp), %ecx
    andl    $-16, %esp
    pushl   -4(%ecx)
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %ecx
    subl    $16, %esp
    movl    $0, -12(%ebp)
    movl    $0, -8(%ebp)
    movl    $0, -16(%ebp)
    jmp .L2
.L3:
    cmpl    $9, -12(%ebp)
    ja  .L4
    movl    -12(%ebp), %eax
    sall    $2, %eax
    movl    .L15(%eax), %eax
    jmp *%eax
    .section    .rodata
    .align 4
    .align 4
.L15:
    .long   .L5
    .long   .L6
    .long   .L7
    .long   .L8
    .long   .L9
    .long   .L10
    .long   .L11
    .long   .L12
    .long   .L13
    .long   .L14
    .text
.L5:
    incl    -8(%ebp)
    jmp .L4
.L6:
    decl    -8(%ebp)
    jmp .L4
.L7:
    decl    -8(%ebp)
    jmp .L4
.L8:
    decl    -8(%ebp)
    jmp .L4
.L9:
    incl    -8(%ebp)
    jmp .L4
.L10:
    decl    -8(%ebp)
    jmp .L4
.L11:
    incl    -8(%ebp)
    jmp .L4
.L12:
    incl    -8(%ebp)
    jmp .L4
.L13:
    decl    -8(%ebp)
    jmp .L4
.L14:
    incl    -8(%ebp)
.L4:
    incl    -12(%ebp)
    cmpl    $9, -12(%ebp)
    jle .L16
    movl    $0, -12(%ebp)
.L16:
    incl    -16(%ebp)
.L2:
    cmpl    $99999999, -16(%ebp)
    jle .L3
    addl    $16, %esp
    popl    %ecx
    leave
    leal    -4(%ecx), %esp
    ret
    .size   main, .-main
    .ident  "GCC: (GNU) 4.1.1 (Gentoo 4.1.1)"
    .section    .note.GNU-stack,"",@progbits

Wat hier gebeurt is dat de compiler een soort van jump tabel maakt, waardoor met 1 optelling meteen naar de juiste code gejmp'd wordt.
(ingenieus, heb wel even op de asm zitten staren )