Wird der Compiler das Entkommen einer inneren Schleife optimieren?

Question

Der Code Ich habe sieht wie folgt aus (alle Verwendungen gezeigt getan):

bool done = false; 
for(int i = 0; i < big; i++) 
{ 
    ... 
    for(int j = 0; j < wow; j++) 
    { 
    ... 
    if(foo(i,j)) 
    { 
     done = true; 
     break; 
    } 
    ... 
    } 
    if(done) break; 
    ... 
} 

werden alle Compiler wandelt es in diese:

for(int i = 0; i < big; i++) 
{ 
    ... 
    for(int j = 0; j < wow; j++) 
    { 
    ... 
    if(foo(i,j)) 
     goto __done; // same as a labeled break if we had it 
    ... 
    } 
    ... 
} 
__done:; 

Hinweis: Während ich bin meistens interessiert an Wenn die if(done)break; wird umgangen und als toter Code entfernt, bin ich auch interessiert, wenn es und done wird insgesamt entfernt.

Answer 1

Offensichtlich hängt das vom Compiler ab. Wenn Sie sich nicht sicher sind, sollten Sie am besten die Assembly-Ausgabe des Compilers anzeigen (alle gängigen Compiler haben dafür einen Schalter). Auch wenn Sie mit Assembly nicht vertraut sind, können Sie die Debug-Version zumindest mit der optimierten Version vergleichen.

Das gesagt, ist dies eine der wenigen Situationen, in denen goto keine schlechte Idee ist. Fühlen Sie sich frei, es aus inneren Schleifen zu brechen.

bearbeiten

habe gerade versucht, die in VS2010 folgenden und es ist in der Tat optimieren die äußere Bedingung:

bool done = false; 
for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 10; j++) 
    { 
     if(i == 7 && j == 3) 
     { 
      done = true; 
      break; 
     } 
    } 
    if(done) break; 
} 
return 0; 

Answer 2

GNU Compiler macht genau das, mit Optimierungsstufe beginnend -O1 (ich benutze gcc 4.5.1 auf x86_64)

call _Z3fooii // al = foo(i,j) 
testb %al, %al 
jne .L14 
... 

wo .L14 das Etikett genau platziert ist, wo Sie __done gelegt:

Eine bessere Frage könnte sein: welcher moderne Compiler nicht diese Optimierung durchführen?

Answer 3

Ich habe versucht, GCC 4.2.1 mit den folgenden:

// Prevent optimizing out calls to foo and loop unrolling: 
extern int big, wow; 
bool foo(int,int); 

void 
bar() 
{ 
    int done = false; 
    for(int i = 0; i < big; i++) 
    { 
     for(int j = 0; j < wow; j++) 
     { 
      if(foo(i,j)) 
      { 
       done = true; 
       break; 
      } 
     } 
     if(done) 
      break; 
    } 
} 

... und es fällt durch gerade mit -O3 Postambel:

33: e8 fc ff ff ff   call 34 <bar()+0x34> ; call to foo* 
    38: 84 c0     test %al,%al 
    3a: 74 e5     je  21 <bar()+0x21> ; next loop iteration 
    3c: 83 c4 10    add $0x10,%esp 
    3f: 5b      pop %ebx 
    40: 5e      pop %esi 
    41: 5d      pop %ebp 
    42: c3      ret 

*** Das von einem ist nicht verknüpfte Objektdatei, call 34 ist eigentlich Anruf an foo.

Answer 4

Ich versuche nicht snarky zu sein, aber ... ist es wichtig? Im Allgemeinen denke ich, dass es am besten ist, Compiler zu ihrem Job zu lassen, und dieser Job besteht darin, den "besten" (kompilierten) Code, der Ihrem Quellcode entspricht, zu erstellen (beachten Sie, dass "am besten" je nach Ihren Bedürfnissen variieren kann). Alle Leistungsaspekte in Ihrem Code sollten mit einem Profiler und guten Arbeitskenntnissen in Bezug auf algorithmische Komplexität identifiziert werden.

Wenn Sie nur neugierig sind, dann ignorieren Sie diesen Kommentar. Aber wenn Sie Ihren Code irgendwie optimieren wollen, dann gibt es meiner Meinung nach viel bessere Möglichkeiten.