Ottimizzazione di un “while (1);” in C ++ 0x

Aggiornato, vedi sotto!

Ho sentito e letto che C ++ 0x consente a un compilatore di stampare “Ciao” per il seguente frammento

#include  int main() { while(1) ; std::cout << "Hello" << std::endl; } 

Apparentemente ha qualcosa a che fare con i thread e le capacità di ottimizzazione. Mi sembra che questo possa sorprendere molte persone.

Qualcuno ha una buona spiegazione del perché questo è stato necessario per consentire? Come riferimento, la bozza C ++ 0x più recente dice 6.5/5

Un ciclo che, al di fuori dell’istruzione for-init nel caso di una dichiarazione for,

  • non effettua chiamate alle funzioni I / O della libreria e
  • non accede o modifica oggetti volatili, e
  • non esegue operazioni di sincronizzazione (1.10) o operazioni atomiche (Articolo 29)

può essere assunto dall’implementazione per terminare. [Nota: ha lo scopo di consentire le trasformazioni del compilatore, come la rimozione di loop vuoti, anche quando la risoluzione non può essere dimostrata. – nota finale]

Modificare:

Questo articolo perspicace parla del testo degli standard

Sfortunatamente, le parole “comportamento indefinito” non sono usate. Tuttavia, ogni volta che lo standard dice “il compilatore può assumere P”, è implicito che un programma che ha la proprietà non-P ha semantica indefinita.

È corretto, e il compilatore è autorizzato a stampare “Ciao” per il programma di cui sopra?


C’è un filo ancora più penetrante qui , che riguarda un analogo cambiamento in C, iniziato dal Guy che ha fatto l’articolo sopra collegato. Tra gli altri fatti utili, presentano una soluzione che sembra applicabile anche a C ++ 0x ( Aggiornamento : Questo non funzionerà più con n3225 – vedi sotto!)

 endless: goto endless; 

A un compilatore non è permesso di ottimizzarlo, a quanto pare, perché non è un ciclo, ma un salto. Un altro ragazzo riassume la modifica proposta in C ++ 0x e C201X

Scrivendo un ciclo, il programmatore sta affermando che il ciclo fa qualcosa con un comportamento visibile (esegue I / O, accede a oggetti volatili, o esegue operazioni di sincronizzazione o atomiche), o che alla fine termina. Se violento questa ipotesi scrivendo un ciclo infinito senza effetti collaterali, sto mentendo al compilatore e il comportamento del mio programma non è definito. (Se sono fortunato, il compilatore potrebbe avvertirmi.) Il linguaggio non fornisce (non fornisce più?) Un modo per esprimere un ciclo infinito senza comportamento visibile.


Aggiornamento del 3.1.2011 con n3225: la commissione ha spostato il testo a 1.10 / 24 e dice

L’implementazione può assumere che qualsiasi thread alla fine esegua una delle seguenti operazioni:

  • terminare,
  • effettuare una chiamata a una funzione I / O della libreria,
  • accedere o modificare un object volatile, o
  • eseguire un’operazione di sincronizzazione o un’operazione atomica.

Il trucco goto non funzionerà più!

Qualcuno ha una buona spiegazione del perché questo è stato necessario per consentire?

Sì, Hans Boehm fornisce una motivazione per questo in N1528: Perché un comportamento indefinito per loop infiniti? sebbene questo sia il documento WG14, la logica si applica anche al C ++ e il documento si riferisce sia a WG14 che a WG21:

Come indica correttamente N1509, la bozza corrente fornisce essenzialmente un comportamento indefinito a cicli infiniti in 6.8.5p6. Un grosso problema è che consente al codice di spostarsi attraverso un loop potenzialmente non terminante. Ad esempio, supponiamo di avere i seguenti cicli, dove count e count2 sono variabili globali (o che hanno avuto il loro indirizzo), e p è una variabile locale, il cui indirizzo non è stato preso:

 for (p = q; p != 0; p = p -> next) { ++count; } for (p = q; p != 0; p = p -> next) { ++count2; } 

Questi due anelli potrebbero essere uniti e sostituiti dal seguente ciclo?

 for (p = q; p != 0; p = p -> next) { ++count; ++count2; } 

Senza la speciale dispensazione in 6.8.5p6 per loop infiniti, ciò non sarebbe consentito: se il primo ciclo non termina perché q punta a una lista circolare, l’originale non scrive mai su count2. Quindi potrebbe essere eseguito in parallelo con un altro thread che accede o aggiorna count2. Questo non è più sicuro con la versione trasformata che accede al count2 nonostante il loop infinito. Quindi la trasformazione potenzialmente introduce una corsa di dati.

In casi come questo, è molto improbabile che un compilatore sia in grado di dimostrare la terminazione del loop; dovrebbe capire che q punta a una lista aciclica, che credo sia al di là della capacità della maggior parte dei compilatori tradizionali, e spesso imansible senza informazioni complete sul programma.

Le restrizioni imposte dai loop non terminanti sono una restrizione sull’ottimizzazione dei loop di terminazione per i quali il compilatore non può provare la terminazione, nonché sull’ottimizzazione dei loop effettivamente non terminanti. I primi sono molto più comuni di questi ultimi e spesso più interessanti da ottimizzare.

Esistono chiaramente anche cicli for-loop con una variabile del ciclo intero in cui sarebbe difficile per un compilatore provare la terminazione, e sarebbe quindi difficile per il compilatore ristrutturare i loop senza 6.8.5p6. Anche qualcosa del genere

 for (i = 1; i != 15; i += 2) 

o

 for (i = 1; i < = 10; i += j) 

sembra non banale da gestire. (Nel primo caso, per dimostrare la terminazione è necessaria una teoria dei numeri di base, in quest'ultimo caso, è necessario conoscere qualcosa sui possibili valori di j. Il wrap-around per interi non firmati può complicare ulteriormente alcuni di questi ragionamenti. )

Questo problema sembra essere applicato a quasi tutte le trasformazioni di ristrutturazione del ciclo, tra cui la parallelizzazione del compilatore e le trasformazioni dell'ottimizzazione della cache, che probabilmente avranno sempre più importanza e sono già spesso importanti per il codice numerico. Questo sembra trasformarsi in un costo sostanziale per il vantaggio di poter scrivere loop infiniti nel modo più naturale ansible, soprattutto perché la maggior parte di noi raramente scrive loop intenzionalmente infiniti.

L'unica differenza principale con C è che C11 fornisce un'eccezione per il controllo di espressioni che sono espressioni costanti che differiscono da C ++ e rendono il tuo esempio specifico ben definito in C11.

Per me, la giustificazione rilevante è:

Questo ha lo scopo di consentire le trasformazioni del compilatore, come la rimozione di loop vuoti, anche quando la risoluzione non può essere dimostrata.

Presumibilmente, questo è dovuto al fatto che provare la terminazione meccanicamente è difficile , e l’incapacità di provare la terminazione ostacola i compilatori che potrebbero altrimenti fare trasformazioni utili, come lo spostamento di operazioni non dipendenti da prima del ciclo a dopo o viceversa, eseguendo operazioni post-loop in un thread mentre il ciclo viene eseguito in un altro e così via. Senza queste trasformazioni, un ciclo potrebbe bloccare tutti gli altri thread mentre aspettano che il thread finisca il ciclo. (Uso “thread” liberamente per indicare qualsiasi forma di elaborazione parallela, inclusi flussi di istruzioni VLIW separati.)

EDIT: esempio stupido:

 while (complicated_condition()) { x = complicated_but_externally_invisible_operation(x); } complex_io_operation(); cout < < "Results:" << endl; cout << x << endl; 

Qui, sarebbe più veloce per un thread eseguire l'operazione complex_io_operation mentre l'altro sta eseguendo tutti i calcoli complessi del ciclo. Ma senza la clausola che hai citato, il compilatore deve provare due cose prima di poter fare l'ottimizzazione: 1) che complex_io_operation() non dipende dai risultati del ciclo, e 2) che il ciclo terminerà . Provare 1) è abbastanza facile, dimostrando 2) è il problema di arresto. Con la clausola, può presumere che il ciclo termini e ottenga una vittoria di parallelizzazione.

Immagino anche che i progettisti abbiano considerato che i casi in cui si verificano loop infiniti nel codice di produzione sono molto rari e di solito sono cose come loop event-driven che accedono all'I / O in qualche modo. Di conseguenza, hanno pessimizzato il caso raro (loop infiniti) in favore dell'ottimizzazione del caso più comune (non infinito, ma difficile da dimostrare meccanicamente non infinito, cicli).

Tuttavia, ciò significa che i loop infiniti utilizzati negli esempi di apprendimento ne risentiranno e aumenteranno i trucchi nel codice principiante. Non posso dire che sia interamente una buona cosa.

EDIT: per quanto riguarda l'articolo perspicace che ora colleghi, direi che "il compilatore può assumere X riguardo al programma" è logicamente equivalente a "se il programma non soddisfa X, il comportamento non è definito". Possiamo mostrarlo come segue: supponiamo che esista un programma che non soddisfa la proprietà X. Dove si definirà il comportamento di questo programma? Lo standard definisce solo il comportamento assumendo che la proprietà X sia vera. Sebbene lo standard non dichiari esplicitamente il comportamento indefinito, lo ha dichiarato non definito dall'omissione.

Si consideri un argomento simile: "il compilatore può assumere che una variabile x è assegnata al massimo una volta sola tra i punti di sequenza" è equivalente a "assegnare a x più di una volta tra i punti di sequenza non definito".

Penso che l’interpretazione corretta sia quella della tua modifica: i cicli infiniti vuoti sono comportamenti indefiniti.

Non direi che è un comportamento particolarmente intuitivo, ma questa interpretazione ha più senso di quella alternativa, che al compilatore è concesso arbitrariamente ignorare loop infiniti senza invocare UB.

Se i cicli infiniti sono UB, significa semplicemente che i programmi non terminanti non sono considerati significativi: secondo C ++ 0x, non hanno semantica.

Anche questo ha un certo senso. Si tratta di un caso speciale, in cui non si verificano più effetti collaterali (ad esempio, non viene mai restituito nulla dal main ) e un numero di ottimizzazioni del compilatore è ostacolato dalla necessità di preservare loop infiniti. Ad esempio, lo spostamento di calcoli attraverso il ciclo è perfettamente valido se il ciclo non ha effetti collaterali, perché alla fine il calcolo verrà eseguito in ogni caso. Ma se il ciclo non termina mai, non possiamo riorganizzare in modo sicuro il codice attraverso di esso, perché potremmo semplicemente cambiare quali operazioni vengono effettivamente eseguite prima che il programma si blocchi. A meno che non trattiamo un programma sospeso come UB, cioè.

Penso che questo sia in linea con questo tipo di domanda , che fa riferimento ad un altro thread . L’ottimizzazione può occasionalmente rimuovere i loop vuoti.

Il problema rilevante è che al compilatore è permesso riordinare il codice i cui effetti collaterali non sono in conflitto. L’ordine sorprendente di esecuzione potrebbe verificarsi anche se il compilatore ha prodotto un codice macchina non terminante per il ciclo infinito.

Credo che questo sia l’approccio giusto. Le specifiche del linguaggio definiscono i modi per far rispettare l’ordine di esecuzione. Se vuoi un ciclo infinito che non può essere riordinato, scrivi questo:

 volatile int dummy_side_effect; while (1) { dummy_side_effect = 0; } printf("Never prints.\n"); 

Penso che il problema potrebbe essere meglio indicato, come “Se una parte successiva del codice non dipende da una parte precedente del codice, e la parte precedente del codice non ha effetti collaterali su nessuna altra parte del sistema, l’output del compilatore può eseguire il pezzo di codice successivo prima, dopo, o mescolato con, l’esecuzione del primo, anche se il primo contiene cicli, senza riguardo per quando o se il codice precedente verrebbe effettivamente completato . Per esempio, il compilatore potrebbe riscrivere:

 void testfermat (int n)
 {
   int a = 1, b = 1, c = 1;
   while (pow (a, n) + pow (b, n)! = pow (c, n))
   {
     se (b> a) a ++;  altrimenti se (c> b) {a = 1;  b ++};  else {a = 1;  b = 1;  c ++};
   }
   printf ("Il risultato è");
   printf ("% d /% d /% d", a, b, c);
 }

come

 void testfermat (int n)
 {
   if (fork_is_first_thread ())
   {
     int a = 1, b = 1, c = 1;
     while (pow (a, n) + pow (b, n)! = pow (c, n))
     {
       se (b> a) a ++;  altrimenti se (c> b) {a = 1;  b ++};  else {a = 1;  b = 1;  c ++};
     }
     signal_other_thread_and_die ();
   }
   else // Secondo thread
   {
     printf ("Il risultato è");
     wait_for_other_thread ();
   }
   printf ("% d /% d /% d", a, b, c);
 }

Generalmente non irragionevole, anche se potrei preoccuparmi che:

   int total = 0;
   for (i = 0; num_reps> i; i ++)
   {
     update_progress_bar (i);
     totale + = do_something_slow_with_no_side_effects (i);
   }
   show_result (totale);

potrebbe diventare

   int total = 0;
   if (fork_is_first_thread ())
   {
     for (i = 0; num_reps> i; i ++)
       totale + = do_something_slow_with_no_side_effects (i);
     signal_other_thread_and_die ();
   }
   altro
   {
     for (i = 0; num_reps> i; i ++)
       update_progress_bar (i);
     wait_for_other_thread ();
   }
   show_result (totale);

Avendo una CPU gestire i calcoli e un altro gestire gli aggiornamenti della barra di avanzamento, la riscrittura migliorerebbe l’efficienza. Sfortunatamente, renderebbe la barra di progresso più semplice di quanto dovrebbero essere.

Non è decidibile per il compilatore per casi non banali se è un ciclo infinito.

In diversi casi, può accadere che il tuo ottimizzatore raggiunga una class di complessità migliore per il tuo codice (ad esempio è O (n ^ 2) e ottieni O (n) o O (1) dopo l’ottimizzazione).

Quindi, includere una regola del genere che non consente la rimozione di un ciclo infinito nello standard C ++ renderebbe imansible l’ottimizzazione. E molte persone non lo vogliono. Penso che questo risponda alla tua domanda.


Un’altra cosa: non ho mai visto alcun esempio valido in cui hai bisogno di un ciclo infinito che non fa nulla.

L’unico esempio di cui ho sentito parlare è un brutto trucco che in realtà dovrebbe essere risolto diversamente: si trattava di sistemi incorporati in cui l’unico modo per triggersre un ripristino era di bloccare il dispositivo in modo che il watchdog lo riavvia automaticamente.

Se conosci qualche esempio valido / valido in cui hai bisogno di un ciclo infinito che non fa nulla, per favore dimmelo.

Penso che valga la pena sottolineare che i loop che sarebbero infiniti a parte il fatto che interagiscono con altri thread tramite variabili non volatili e non sincronizzate possono ora produrre un comportamento errato con un nuovo compilatore.

In altre parole, rendi volatili i tuoi globals – così come gli argomenti passati in tale ciclo tramite puntatore / riferimento.