Schleife mit einer Ausführungszeit von Null

74

Ist es möglich, eine Schleife mit einer Ausführungszeit von Null zu haben? Ich würde denken, dass sogar eine leere Schleife eine Ausführungszeit haben sollte, da damit ein Overhead verbunden ist.

user3678189
quelle
37
Schleifen können vom Compiler abgewickelt und / oder vollständig entfernt werden.
Elliott Frisch
4
Eine der Hauptaufgaben eines optimierenden Compilers ist die Datenflussanalyse. Berechnungen, die Daten erzeugen, die nirgendwo fließen, werden eliminiert, einschließlich Schleifen. Das genaue Verhalten hängt von Ihrem Compiler ab.
Dietrich Epp
6
Das Schließen aufgrund einer zu weit gefassten Frage ist nicht sinnvoll. Wir haben nicht viele mögliche Antworten auf diese Frage und sie trifft auf den allgemeinen Fall sehr gut zu.
Shafik Yaghmour
3
Diese Frage entspricht keinem der Kriterien für zu weit gefasst. Wie wir empirisch aus den Antworten ersehen können, gibt es nicht zu viele von ihnen und es gibt im Grunde eine genaue Antwort. Die beiden Antworten unterscheiden sich nur in der Detailgenauigkeit, die sie bieten. Die Antworten sind nicht zu lang und obwohl sie erweitert werden könnten, haben sie noch einen langen Weg vor sich, bevor sie sich den längsten guten Antworten auf perfekt zu Themenfragen nähern würden, die es gibt.
Shafik Yaghmour
2
@georg: Pipelining kann jedoch die beobachtete Verarbeitungszeit für einen bestimmten Befehl halbieren , da er zusammen mit einem anderen Befehl im selben CPU-Zyklus ausgeführt wird. Wenn 'der andere Befehl' Ihr NOP ist, ist nur der ursprüngliche Befehlszyklus erforderlich.
Jongware

Antworten:

121

Ja, nach der Als-ob-Regel ist der Compiler nur verpflichtet, das beobachtbare Verhalten des Codes zu emulieren. Wenn Sie also eine Schleife haben, die kein beobachtbares Verhalten aufweist, kann sie vollständig optimiert werden und hat daher effektiv keine Ausführungszeit .

Beispiele

Zum Beispiel der folgende Code:

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

Kompiliert mit der gcc 4.9Verwendung des -O3Flags reduziert sich im Grunde auf das Folgende ( siehe live ):

main:
  xorl  %eax, %eax  #
  ret

Nahezu alle zulässigen Optimierungen fallen unter die Als-ob-Regel . Die einzige mir bekannte Ausnahme ist das Kopieren, das das beobachtbare Verhalten beeinflussen darf.

Einige andere Beispiele wären die Beseitigung von totem Code, mit der Code entfernt werden kann, von dem der Compiler nachweisen kann, dass er niemals ausgeführt wird. Zum Beispiel kann die folgende Schleife, obwohl sie tatsächlich einen Nebeneffekt enthält, optimiert werden, da wir beweisen können, dass sie niemals ausgeführt wird ( siehe live ):

#include <stdio.h>

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

Die Schleife wird wie im vorherigen Beispiel optimiert. Ein interessanteres Beispiel wäre der Fall, in dem eine Berechnung in einer Schleife in eine Konstante abgeleitet werden kann, wodurch die Notwendigkeit einer Schleife vermieden wird ( nicht sicher, in welche Optimierungskategorie dies fällt ), zum Beispiel:

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

kann weg optimiert werden, um ( live zu sehen ):

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

Wir können sehen, dass es keine Schleife gibt.

Wo ist als ob Regel in der Norm abgedeckt

Die Als-ob-Regel wird im Entwurf des C99-Standardabschnitts 5.1.2.3 Programmausführung behandelt, in dem es heißt:

In der abstrakten Maschine werden alle Ausdrücke gemäß der Semantik ausgewertet. Eine tatsächliche Implementierung muss keinen Teil eines Ausdrucks auswerten, wenn daraus geschlossen werden kann, dass sein Wert nicht verwendet wird und keine erforderlichen Nebenwirkungen auftreten (einschließlich solcher, die durch den Aufruf einer Funktion oder den Zugriff auf ein flüchtiges Objekt verursacht werden).

Die Als-ob-Regel gilt auch für C ++ und gccführt auch im C ++ - Modus zum gleichen Ergebnis. Der C ++ - Standardentwurf behandelt dies im Abschnitt 1.9 Programmausführung :

Die semantischen Beschreibungen in dieser Internationalen Norm definieren eine parametrisierte nichtdeterministische abstrakte Maschine. Diese Internationale Norm stellt keine Anforderungen an die Struktur konformer Implementierungen. Insbesondere müssen sie die Struktur der abstrakten Maschine nicht kopieren oder emulieren. Vielmehr sind konforme Implementierungen erforderlich, um (nur) das beobachtbare Verhalten der abstrakten Maschine zu emulieren, wie nachstehend erläutert.5

Shafik Yaghmour
quelle
Ich würde wetten, dass die meisten, wenn nicht alle Sprachspezifikationen eine Als-ob- Regel haben. Es macht normalerweise keinen Sinn, eine Berechnung durchzuführen, wenn sie nicht verwendet wird und keine Nebenwirkungen hat. Es verschwendet nur Zeit und Energie.
Craig S. Anderson
16
@CraigAnderson: Das ist wahr , dass große Mehrheit der Zeit, aber es gibt seltene Fälle , in denen Sie keine nutzlosen Berechnungen, wie in Verschlüsselungsoperationen tun wollen , wo Sie alle Codepfade die gleiche Menge an Zeit , um nehmen mögen , um zu verhindern Timing Seite Kanalangriffe .
Adam Rosenfield
Mit anderen Worten : Für echte Schleifen, die tatsächliche, unvermeidbare, nicht betrügerische Arbeit ausführen, lautet die Antwort: Nein . Für Pseudo-Loops, die nur überflüssige Dinge tun: Ja .
Lutz Prechelt
52

Ja - Wenn der Compiler feststellt, dass die Schleife toter Code ist (niemals ausgeführt wird), generiert er keinen Code dafür. Diese Schleife hat eine Ausführungszeit von 0, obwohl sie streng genommen auf Maschinencodeebene nicht vorhanden ist.

Craig S. Anderson
quelle
12

Neben Compiler-Optimierungen weisen einige CPU-Architekturen, insbesondere DSPs, keine Overhead-Schleifen auf , wobei eine Schleife mit einer festen Anzahl von Iterationen von der Hardware effektiv optimiert wird (siehe z. B. http://www.dsprelated.com/showmessage/20681) /1.php

Paul R.
quelle
3

Der Compiler ist nicht verpflichtet, den Ausdruck oder einen Teil eines Ausdrucks auszuwerten, der keine Nebenwirkungen hat und dessen Ergebnis verworfen wird.

Harbison und Steele, C: Ein Referenzhandbuch

Maxim Chetrusca
quelle