Loop con un tempo di esecuzione pari a zero

È ansible avere un ciclo che ha un tempo di esecuzione pari a zero? Penserei che anche un ciclo vuoto dovrebbe avere un tempo di esecuzione poiché c’è un sovraccarico ad esso associato.

Sì, sotto la regola as-if il compilatore è obbligato solo a emulare il comportamento osservabile del codice, quindi se si dispone di un ciclo che non ha alcun comportamento osservabile allora può essere completamente ottimizzato e quindi avrà effettivamente zero tempi di esecuzione .

Esempi

Ad esempio il seguente codice:

int main() { int j = 0 ; for( int i = 0; i < 10000; ++i ) { ++j ; } } 

compilato con gcc 4.9 usando il flag -O3 fondamentalmente finisce per ridurre a quanto segue ( vederlo dal vivo ):

 main: xorl %eax, %eax # ret 

Praticamente tutte le ottimizzazioni permesse rientrano nella regola as-if , l'unica eccezione di cui sono a conoscenza è la copia elison che è autorizzata ad attuare il comportamento osservabile.

Alcuni altri esempi includono l' eliminazione del codice morto che può rimuovere il codice che il compilatore può provare non verrà mai eseguito. Ad esempio, anche se il seguente ciclo contiene effettivamente un effetto collaterale, può essere ottimizzato perché possiamo provare che non verrà mai eseguito ( guardalo dal vivo ):

 #include  int main() { int j = 0 ; if( false ) // The loop will never execute { for( int i = 0; i < 10000; ++i ) { printf( "%d\n", j ) ; ++j ; } } } 

Il ciclo ottimizzerà lo stesso come nell'esempio precedente. Un esempio più interessante potrebbe essere il caso in cui un calcolo in un ciclo può essere dedotto in una costante evitando così la necessità di un ciclo ( non sono sicuro su quale categoria di ottimizzazione rientra in questo ), ad esempio:

 int j = 0 ; for( int i = 0; i < 10000; ++i ) { ++j ; } printf( "%d\n", j ) ; 

può essere ottimizzato per ( vederlo dal vivo ):

 movl $10000, %esi #, movl $.LC0, %edi #, xorl %eax, %eax # call printf # 

Possiamo vedere che non è coinvolto alcun loop.

Dove è come se la regola fosse contemplata nello standard

La regola as-if è trattata nella bozza di standard C99 sezione 5.1.2.3 Esecuzione del programma che dice:

Nella macchina astratta, tutte le espressioni sono valutate come specificato dalla semantica. Un'implementazione reale non deve valutare parte di un'espressione se può dedurre che il suo valore non è usato e che non vengono prodotti effetti collaterali necessari (compresi quelli causati dal chiamare una funzione o dall'accedere a un object volatile).

La regola as-if si applica anche a C ++, gcc produrrà lo stesso risultato anche in modalità C ++. Lo standard di bozza C ++ lo copre nella sezione 1.9 Esecuzione del programma :

Le descrizioni semantiche di questo standard internazionale definiscono una macchina astratta non parametrica parametrizzata. Questo standard internazionale non impone alcun requisito sulla struttura delle implementazioni conformi. In particolare, non è necessario copiare o emulare la struttura della macchina astratta. Piuttosto, sono necessarie implementazioni conformi per emulare (solo) il comportamento osservabile della macchina astratta come spiegato di seguito.5

Sì, se il compilatore determina che il ciclo è un codice morto (non verrà mai eseguito), quindi non genererà il codice per esso. Quel ciclo avrà tempo di esecuzione 0, anche se in senso stretto non esiste a livello di codice macchina.

Oltre all’ottimizzazione del compilatore, alcune architetture della CPU, in particolare i DSP, non hanno un looping overhead , per cui un loop con un numero fisso di iterazioni viene efficacemente ottimizzato dall’hardware, vedere ad esempio http://www.dsprelated.com/showmessage/20681 /1.php

Il compilatore non è obbligato a valutare l’espressione, o una parte di un’espressione, che non ha effetti collaterali e il cui risultato è scartato.

Harbison e Steele, C: A Reference Manual