c - Quale è più veloce: while (1) o while (2)?




11 Answers

Entrambi i loop sono infiniti, ma possiamo vedere quale prende più istruzioni / risorse per iterazione.

Usando gcc, ho compilato i due seguenti programmi per l'assemblaggio a diversi livelli di ottimizzazione:

int main(void) {
    while(1) {}
    return 0;
}


int main(void) {
    while(2) {}
    return 0;
}

Anche senza ottimizzazioni ( -O0 ), l'assembly generato era identico per entrambi i programmi . Pertanto, non vi è alcuna differenza di velocità tra i due anelli.

Per riferimento, ecco l'assembly generato (utilizzando gcc main.c -S -masm=intel con un flag di ottimizzazione):

Con -O0 :

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Con -O1 :

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Con -O2 e -O3 (stessa uscita):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Infatti, l'assembly generato per il loop è identico per ogni livello di ottimizzazione:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

I bit importanti sono:

.L2:
    jmp .L2

Non riesco a leggere il montaggio molto bene, ma questo è ovviamente un ciclo incondizionato. L'istruzione jmp reimposta incondizionatamente il programma sull'etichetta .L2 senza nemmeno confrontare un valore con true, e ovviamente lo fa immediatamente fino a quando il programma non viene concluso. Questo corrisponde direttamente al codice C / C ++:

L2:
    goto L2;

Modificare:

È interessante notare che, anche senza ottimizzazioni , tutti i loop seguenti hanno prodotto lo stesso identico output ( jmp condizionale) in assembly:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

E anche con mio stupore:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

Le cose diventano un po 'più interessanti con le funzioni definite dall'utente:

int x(void) {
    return 1;
}

while(x()) {}


#include<math.h>

double x(void) {
    return sqrt(7);
}

while(x()) {}

A -O0 , questi due esempi chiamano effettivamente x ed eseguono un confronto per ogni iterazione.

Primo esempio (restituendo 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Secondo esempio (restituendo sqrt(7) ):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Tuttavia, a -O1 e sopra, entrambi producono lo stesso assembly degli esempi precedenti (una jmp incondizionata all'etichetta precedente).

TL; DR

Sotto GCC, i diversi loop sono compilati per un assemblaggio identico. Il compilatore valuta i valori costanti e non si preoccupa di eseguire alcun confronto effettivo.

La morale della storia è:

  • Esiste uno strato di traduzione tra il codice sorgente C ++ e le istruzioni della CPU, e questo strato ha importanti implicazioni per le prestazioni.
  • Pertanto, le prestazioni non possono essere valutate solo guardando il codice sorgente.
  • Il compilatore dovrebbe essere abbastanza intelligente da ottimizzare questi casi banali. I programmatori non dovrebbero sprecare il loro tempo a pensare a loro nella stragrande maggioranza dei casi.

Questa è stata una domanda di intervista fatta da un senior manager.

Quale è più veloce?

while(1) {
    // Some code
}

o

while(2) {
    //Some code
}

Ho detto che entrambi hanno la stessa velocità di esecuzione, come l'espressione dentro while dovrebbe finalmente valutare il true o il false . In questo caso, entrambi valutano true e non ci sono istruzioni condizionali extra all'interno della condizione while . Quindi, entrambi avranno la stessa velocità di esecuzione e io preferisco mentre (1).

Ma l'intervistatore ha detto con sicurezza: "Controlla le basi, while(1) è più veloce di while(2) ." (Non stava mettendo alla prova la mia fiducia)

È vero?

Vedi anche: "for (;;)" più veloce di "while (TRUE)"? Se no, perché la usano?




Le risposte esistenti che mostrano il codice generato da un particolare compilatore per un particolare target con un particolare set di opzioni non rispondono completamente alla domanda - a meno che la domanda non sia stata posta in quel contesto specifico ("Che è più veloce usando gcc 4.7.2 per x86_64 con opzioni predefinite? ", ad esempio).

Per quanto riguarda la definizione del linguaggio, nella macchina astratta while (1) valuta la costante intera 1 e while (2) valuta la costante intera 2 ; in entrambi i casi il risultato viene confrontato per uguaglianza a zero. Lo standard linguistico non dice assolutamente nulla sulla performance relativa dei due costrutti.

Posso immaginare che un compilatore estremamente ingenuo possa generare un codice macchina diverso per le due forme, almeno quando compilato senza richiedere l'ottimizzazione.

D'altra parte, i compilatori C devono assolutamente valutare alcune espressioni costanti in fase di compilazione, quando appaiono in contesti che richiedono un'espressione costante. Ad esempio, questo:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

richiede una diagnosi; un compilatore pigro non ha la possibilità di posticipare la valutazione di 2+2 fino al tempo di esecuzione. Dal momento che un compilatore deve avere la capacità di valutare le espressioni costanti in fase di compilazione, non c'è una buona ragione per non trarre vantaggio da tale capacità anche quando non è richiesta.

Lo standard C ( N1570 6.8.5p4) lo dice

Un'istruzione di iterazione fa sì che un'istruzione chiamata il corpo del ciclo sia eseguita ripetutamente finché l'espressione di controllo non è uguale a 0.

Quindi le espressioni costanti rilevanti sono 1 == 0 e 2 == 0 , entrambe valutano il valore int 0 . (Questi confronti sono impliciti nella semantica del ciclo while , ma non esistono come espressioni C effettive.)

Un compilatore perversamente ingenuo potrebbe generare codice diverso per i due costrutti. Ad esempio, per il primo potrebbe generare un ciclo infinito incondizionato (trattando 1 come caso speciale) e per il secondo potrebbe generare un confronto esplicito in tempo di esecuzione equivalente a 2 != 0 . Ma non ho mai incontrato un compilatore C che si comporterebbe in quel modo, e dubito seriamente che un compilatore di questo tipo esista.

La maggior parte dei compilatori (sono tentato di dire tutti i compilatori di qualità di produzione) hanno opzioni per richiedere ulteriori ottimizzazioni. Con questa opzione, è ancora meno probabile che qualsiasi compilatore generi codice diverso per i due moduli.

Se il compilatore genera codice diverso per i due costrutti, per prima cosa controlla se le diverse sequenze di codice abbiano effettivamente prestazioni diverse. Se lo fanno, prova a compilare di nuovo con un'opzione di ottimizzazione (se disponibile). Se sono ancora diversi, invia un bug report al fornitore del compilatore. Non è (necessariamente) un bug nel senso di una mancata conformità allo standard C, ma è quasi certamente un problema che dovrebbe essere corretto.

In conclusione: while (1) e while(2) quasi sicuramente hanno le stesse prestazioni. Hanno esattamente la stessa semantica e non c'è alcuna buona ragione per cui un compilatore non generi codice identico.

E sebbene sia perfettamente legale per un compilatore generare codice più veloce per while(1) che per while(2) , è ugualmente legale per un compilatore generare codice più veloce per while(1) che per un'altra occorrenza di while(1) nel stesso programma.

(C'è un'altra domanda implicita in quella che hai chiesto: come affrontare un intervistatore che insiste su un punto tecnico errato, probabilmente sarebbe una buona domanda per il sito di Workplace ).




La tua spiegazione è corretta. Questa sembra essere una domanda che mette alla prova la tua sicurezza in aggiunta alla conoscenza tecnica.

A proposito, se hai risposto

Entrambi i pezzi di codice sono ugualmente veloci, perché entrambi richiedono tempi infiniti per essere completati

l'intervistatore direbbe

Ma while (1) può fare più iterazioni al secondo; puoi spiegare perché? (questa è una sciocchezza, prova di nuovo la tua fiducia)

Quindi rispondendo come hai fatto, hai risparmiato un po 'di tempo che altrimenti avresti sprecato a discutere questa brutta domanda.

Ecco un codice di esempio generato dal compilatore sul mio sistema (MS Visual Studio 2012), con le ottimizzazioni disattivate:

yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...

Con le ottimizzazioni attivate:

xxx:
    jmp xxx

Quindi il codice generato è esattamente lo stesso, almeno con un compilatore ottimizzante.




Ovviamente non conosco le reali intenzioni di questo manager, ma propongo una visione completamente diversa: quando assumi un nuovo membro in una squadra, è utile sapere come reagisce alle situazioni di conflitto.

Ti hanno portato in conflitto. Se questo è vero, sono intelligenti e la domanda è stata buona. Per alcuni settori, come il settore bancario, pubblicare il tuo problema su potrebbe essere un motivo di rifiuto.

Ma ovviamente non lo so, propongo solo un'opzione.




Avresti dovuto chiedergli come ha raggiunto questa conclusione. Sotto qualsiasi compilatore decente là fuori, i due compilano le stesse istruzioni asm. Quindi, avrebbe dovuto dirti anche il compilatore per iniziare. E anche così, dovresti conoscere molto bene il compilatore e la piattaforma per fare anche un'ipotesi teorica. E alla fine, non importa in pratica, dal momento che ci sono altri fattori esterni come la frammentazione della memoria o il carico del sistema che influenzeranno il loop più di questo dettaglio.




Un'altra domanda su una tale domanda sarebbe vedere se hai il coraggio di dire al tuo manager che ha torto! E con che dolcezza puoi comunicarlo.

Il mio primo istinto sarebbe stato generare output di assembly per mostrare al manager che qualsiasi compilatore decente dovrebbe prendersene cura, e se non lo fa, invierete la prossima patch per questo :)




Ho usato per programmare il codice C e Assembly quando questo tipo di assurdità avrebbe potuto fare la differenza. Quando ha fatto la differenza l'abbiamo scritto in Assembly.

Se mi venisse posta questa domanda, avrei ripetuto la famosa citazione di Donald Knuth del 1974 sull'ottimizzazione prematura e ho camminato se l'intervistatore non ha riso e non si è mosso.




Se sei preoccupato dell'ottimizzazione, dovresti usare

for (;;)

perché quello non ha test. (modalità cinica)




Sono entrambi uguali - lo stesso.

Secondo le specifiche qualsiasi cosa che non sia 0 è considerata vera, quindi anche senza alcuna ottimizzazione, e un buon compilatore non genererà alcun codice per while (1) o while (2). Il compilatore genererebbe un semplice controllo per != 0.




Forse l'intervistatore ha posto intenzionalmente una domanda così stupida e voleva che tu facessi 3 punti:

  1. Ragionamento di base. Entrambi i loop sono infiniti, è difficile parlare di prestazioni.
  2. Conoscenza dei livelli di ottimizzazione. Voleva sapere da te se permettevi al compilatore di fare qualsiasi ottimizzazione per te, ottimizzerebbe la condizione, specialmente se il blocco non era vuoto.
  3. Conoscenza dell'architettura dei microprocessori. La maggior parte delle architetture ha un'istruzione CPU speciale per il confronto con 0 (sebbene non necessariamente più veloce).



Dal momento che le persone che cercano di rispondere a questa domanda vogliono il ciclo più veloce, avrei risposto che entrambi sono ugualmente compilati nello stesso codice assembly, come indicato nelle altre risposte. Ciononostante puoi suggerire all'intervistatore l'uso di 'loop unwroll'; un do do {} while loop invece del ciclo while.

Cauto: è necessario assicurarsi che il ciclo venga eseguito almeno una volta almeno .

Il ciclo dovrebbe avere una condizione di rottura all'interno.

Anche per quel tipo di ciclo preferirei personalmente l'uso di do {} while (42) poiché qualsiasi numero intero, ad eccezione di 0, farebbe il lavoro.




Related