Wissen C- und C++-Optimierer normalerweise, welche Funktionen keine Nebenwirkungen haben?

Sagen wir für sehr gängige mathematische Funktionen wie sin, cos usw. … erkennt der Compiler, dass sie keine Nebenwirkungen haben und die Möglichkeit haben, sie in äußere Schleifen zu verschieben? Zum Beispiel

// Unoptimized

double YSinX(double x,int y)
{
   double total = 0.0;
   for (int i = 0; i < y; i++)
      total += sin(x);
   return total;
}

// Manually optimized

double YSinX(double x,int y)
{
   double total = 0.0, sinx = sin(x);
   for (int i = 0; i < y; i++)
      total += sinx;
   return total;
}

Wenn ja, gibt es eine Möglichkeit, eine Funktion als nebenwirkungsfrei zu deklarieren und somit sicher auf diese Weise zu optimieren? Die anfängliche Profilerstellung einer VS2010-App legt nahe, dass die Optimierung vorteilhaft ist.

Siehe auch diese verwandte Frage, die nah dran ist, aber meine eigene nicht ganz beantwortet.

Bearbeiten: Einige großartige Antworten. Die, die ich akzeptierte, basierte ebenso auf den Kommentaren, die sie provozierte, wie auf der Antwort selbst, insbesondere auf dem verlinkten Artikel, und auf der Tatsache, dass das Heben in Situationen, in denen dies der Fall ist, möglicherweise nicht auftritt errno gesetzt ist (also ein Nebeneffekt). Als solches und im Kontext meiner Arbeit erscheint diese Art der manuellen Optimierung immer noch sinnvoll.

GCC hat zwei Attribute, pure und const, die verwendet werden können, um eine solche Funktion zu markieren. Wenn die Funktion keine Nebenwirkung hat und ihr Ergebnis nur von ihren Argumenten abhängt, sollte die Funktion deklariert werden constwenn die Ergebnisse auch von einer globalen Variablen abhängen können, sollte die Funktion deklariert werden pure. Neuere Versionen haben auch eine -Wsuggest-attribute Warnoption das kann Funktionen zeigen, die deklariert werden sollten const oder pure.

Tatsächlich werden die heutigen gängigen Compiler die Art von ausführen schleifeninvariante Codebewegung Optimierung, nach der Sie fragen. Eine Demonstration dazu finden Sie in der zweiten Übung darin Dieser Artikel mit dem Titel “Wird es optimiert?”oder verwenden gcc -S -O3 und/oder clang -S -O3 um das Beispiel unten zusammenzubauen und zu inspizieren main Einstiegspunkt in der Montage, wie ich es aus Neugier tat. Wenn Ihr VS2010-Compiler diese Optimierung nicht durchführt, macht das nichts; llvm/clang „integriert mit MSVC 2010, 2012, 2013 und 14 CTP“.

Aus theoretischer Sicht erklären diese beiden Zitate den Spielraum oder Spielraum, den ein Compiler hat, wenn er Optimierungen durchführt. Sie sind vom C11-Standard. IIRC C++11 hat etwas Ähnliches.

§5.1.2.3p4:

In der abstrakten Maschine werden alle Ausdrücke so ausgewertet, wie es die Semantik vorgibt. Eine tatsächliche Implementierung muss einen Teil eines Ausdrucks nicht auswerten, wenn daraus abgeleitet werden kann, dass sein Wert nicht verwendet wird und dass keine erforderlichen Nebeneffekte erzeugt werden (einschließlich solcher, die durch das Aufrufen einer Funktion oder den Zugriff auf ein flüchtiges Objekt verursacht werden).

§5.1.2.3p6:

Die Mindestanforderungen an eine konforme Implementierung sind:

— Zugriffe auf flüchtige Objekte werden streng nach den Regeln der abstrakten Maschine ausgewertet.

— Bei Programmende müssen alle in Dateien geschriebenen Daten mit dem Ergebnis identisch sein, das die Ausführung des Programms gemäß der abstrakten Semantik hervorgebracht hätte.

— Die Eingangs- und Ausgangsdynamik von interaktiven Geräten muss wie in 7.21.3 spezifiziert erfolgen. Die Absicht dieser Anforderungen besteht darin, dass eine ungepufferte oder zeilengepufferte Ausgabe so schnell wie möglich erscheint, um sicherzustellen, dass Aufforderungsmeldungen tatsächlich erscheinen, bevor ein Programm auf eine Eingabe wartet.

Dies ist das beobachtbare Verhalten des Programms.

Daher könnte ein Compiler Ihr gesamtes Programm in die Auswertung zur Kompilierzeit heben, wenn er dazu in der Lage ist. Betrachten Sie zum Beispiel das folgende Programm:

#include <math.h>
#include <stdio.h>

double YSinX(double x,int y)
{
    double total = 0.0;
    for (int i = 0; i < y; i++)
        total += sin(x);
    return total;
}

int main(void) {
    printf("%f\n", YSinX(M_PI, 4));
}

Ihr Compiler erkennt möglicherweise, dass dieses Programm ausgibt 0.0\n jedes Mal und optimieren Sie Ihr Programm in:

int main(void) { puts("0.0"); }

Das ist, Bereitstellung Ihr Compiler kann das auch nicht beweisen sin Noch YsinX irgendwelche verursachen erforderlich Nebenwirkungen. Beachten Sie, dass sie immer noch Nebenwirkungen haben können (und wahrscheinlich tun), aber das sind sie nicht erforderlich um die Ausgabe dieses Programms zu erzeugen.

Um das theoretische Wissen in der Praxis anzuwenden, habe ich beide getestet llvm/clang (3.8.0 ab clang --version) und gcc (6.4.0 ab gcc --version) durch Zusammenbau (mit gcc -S -O3/clang -S -O3) den obigen Code auf meinem Windows 10-System, beide dieser Compiler haben die oben beschriebene Optimierung effektiv angewendet; in der Praxis können Sie erwarten main aus dem obigen Beispiel in ein Maschinencode-Äquivalent umzuwandeln int main(void) { printf("%f", 0.0); }.

Sie haben eine Frage zu “dem Compiler” gestellt. Wenn Sie sich darauf beziehen alle C- oder C++-Implementierungen, gibt es keine garantierten Optimierungen und eine C-Implementierung muss nicht einmal ein Compiler sein. Sie müssten es uns sagen welche spezielle C- oder C++-Implementierung; Wie ich oben erklärt habe, lässt sich LLVM/Clang „mit MSVC 2010, 2012, 2013 und 14 CTP integrieren“, sodass es möglich ist, dass Sie das verwenden. Wenn Ihr C- oder C++-Compiler keinen optimalen Code produziert, besorgen Sie sich einen neuen Compiler (z. B. LLVM/Clang) oder erstellen Sie die Optimierung selbst, vorzugsweise indem Sie Ihren Compiler so modifizieren, dass Sie einen Patch an die Entwickler senden und die Optimierung automatisch an sie weitergeben können weitere Projekte.

Was benötigt wird, um diesen Unterausdruck aus der Schleife zu heben, ist nicht Reinheit, sondern Idempotenz.

Idempotenz bedeutet, dass eine Funktion bei einmaligem Aufruf die gleichen Nebenwirkungen und Ergebnisse hat, als wenn sie viele Male mit den gleichen Argumenten aufgerufen wird. Daher kann der Compiler den Funktionsaufruf außerhalb der Schleife platzieren, nur durch eine Bedingung geschützt (würde die Schleife mindestens einmal iterieren?). Der eigentliche Code nach der Huboptimierung wäre dann:

double YSinX(double x,int y)
{
   double total = 0.0;
   int i = 0;
   if (i < y) {
       double sinx = sin(x);  // <- this goes between the loop-initialization
                              // first test of the condition expression
                              // and the loop body
       do {
          total += sinx;
          i++;
       } while (i < y);
   }
   return total;
}

Die Unterscheidung zwischen __attribute__(pure) und idempotent ist wichtig, da diese Funktionen, wie adl in seinem Kommentar anmerkt, einen Nebeneffekt der Einstellung haben errno.

Seien Sie jedoch vorsichtig, denn Idempotenz gilt nur für wiederholte Aufrufe ohne dazwischenliegende Anweisungen. Der Compiler muss eine Datenflussanalyse durchführen, um zu beweisen, dass die Funktion und der intervenierende Code nicht interagieren (z. B. verwendet der intervenierende Code nur Locals, deren Adressen nie verwendet werden), bevor er Idempotenz ausnutzen kann. Dies ist nicht erforderlich, wenn bekannt ist, dass die Funktion rein ist. Aber Reinheit ist eine viel stärkere Bedingung, die nicht auf sehr viele Funktionen zutrifft.

Ich denke ja. Wenn Sie die Ausgabe der Compiler-Disassemblierung erhalten, können Sie sehen, dass sin in einem anderen Label als dem Loop-Label für ‘for’ aufgerufen wird: (kompiliert mit g++ -O1 -O2 -O3)

Leh_func_begin1:
        pushq   %rbp
Ltmp0:
        movq    %rsp, %rbp
Ltmp1:
        pushq   %rbx
        subq    $8, %rsp
Ltmp2:
        testl   %edi, %edi
        jg      LBB1_2
        pxor    %xmm1, %xmm1
        jmp     LBB1_4
LBB1_2:
        movl    %edi, %ebx
        callq   _sin ;sin calculated
        pxor    %xmm1, %xmm1
        .align  4, 0x90
LBB1_3:
        addsd   %xmm0, %xmm1
        decl    %ebx
        jne     LBB1_3 ;loops here till i reaches y
LBB1_4:
        movapd  %xmm1, %xmm0

Ich hoffe, ich liege richtig.