Welche C++-Compiler führen gegebenenfalls eine Schwanzrekursionsoptimierung durch?

StackOverflow https://stackoverflow.com/questions/34125

Frage

Es scheint mir, dass es vollkommen gut funktionieren würde, eine Tail-Recursion-Optimierung sowohl in C als auch in C++ durchzuführen, doch beim Debuggen sehe ich anscheinend nie einen Frame-Stack, der auf diese Optimierung hinweist.Das ist irgendwie gut, denn der Stack sagt mir, wie tief die Rekursion ist.Allerdings wäre die Optimierung auch ganz nett.

Führen C++-Compiler diese Optimierung durch?Warum?Warum nicht?

Wie sage ich dem Compiler, dass er es tun soll?

  • Für MSVC: /O2 oder /Ox
  • Für GCC: -O2 oder -O3

Wie wäre es mit der Überprüfung, ob der Compiler dies in einem bestimmten Fall getan hat?

  • Aktivieren Sie für MSVC die PDB-Ausgabe, um den Code verfolgen zu können, und überprüfen Sie dann den Code
  • Für GCC...?

Ich würde immer noch Vorschläge annehmen, wie ich feststellen kann, ob eine bestimmte Funktion vom Compiler auf diese Weise optimiert wird (obwohl ich es beruhigend finde, dass Konrad mir sagt, ich solle davon ausgehen).

Es ist immer möglich, zu überprüfen, ob der Compiler dies überhaupt tut, indem man eine unendliche Rekursion durchführt und prüft, ob es zu einer Endlosschleife oder einem Stapelüberlauf kommt (ich habe das mit GCC gemacht und das herausgefunden). -O2 ist ausreichend), aber ich möchte in der Lage sein, eine bestimmte Funktion zu überprüfen, von der ich weiß, dass sie trotzdem beendet wird.Ich hätte gerne eine einfache Möglichkeit, das zu überprüfen :)

Nach einigen Tests habe ich herausgefunden, dass Destruktoren die Möglichkeit dieser Optimierung zunichte machen.Manchmal kann es sich lohnen, den Gültigkeitsbereich bestimmter Variablen und temporärer Variablen zu ändern, um sicherzustellen, dass sie den Gültigkeitsbereich verlassen, bevor die Return-Anweisung beginnt.

Wenn nach dem Tail-Call ein Destruktor ausgeführt werden muss, kann die Tail-Call-Optimierung nicht durchgeführt werden.

War es hilfreich?

Lösung

Alle aktuellen Mainstream-Compiler führen eine Tail-Call-Optimierung durch ziemlich gut (und das schon seit mehr als einem Jahrzehnt), auch für gegenseitig rekursive Aufrufe wie zum Beispiel:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

Es ist unkompliziert, den Compiler die Optimierung durchführen zu lassen:Schalten Sie einfach die Geschwindigkeitsoptimierung ein:

  • Verwenden Sie für MSVC /O2 oder /Ox.
  • Für GCC, Clang und ICC verwenden Sie -O3

Eine einfache Möglichkeit, zu überprüfen, ob der Compiler die Optimierung durchgeführt hat, besteht darin, einen Aufruf auszuführen, der andernfalls zu einem Stapelüberlauf führen würde – oder sich die Assembly-Ausgabe anzusehen.

Als interessante historische Anmerkung wurde im Laufe von a die Tail-Call-Optimierung für C zum GCC hinzugefügt Diplomarbeit von Mark Probst.Die Arbeit beschreibt einige interessante Vorbehalte bei der Implementierung.Es lohnt sich zu lesen.

Andere Tipps

gcc 4.3.2 integriert diese Funktion vollständig (beschissen/trivial). atoi() Umsetzung) in main().Optimierungsgrad ist -O1.Ich merke es, wenn ich damit herumspiele (sogar wenn ich es ändere). static Zu extern, die Schwanzrekursion verschwindet ziemlich schnell, daher würde ich mich bei der Programmkorrektheit nicht darauf verlassen.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}

Neben dem Offensichtlichen (Compiler führen diese Art der Optimierung nur dann durch, wenn Sie darum bitten) gibt es eine Komplexität bei der Tail-Call-Optimierung in C++:Zerstörer.

Gegeben sei so etwas wie:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

Der Compiler kann dies (im Allgemeinen) nicht optimieren, da er den Destruktor von nennen muss cls nach Der rekursive Aufruf kehrt zurück.

Manchmal kann der Compiler erkennen, dass der Destruktor keine äußerlich sichtbaren Nebenwirkungen hat (sodass dies frühzeitig erfolgen kann), aber oft ist dies nicht der Fall.

Eine besonders häufige Form davon ist wo Funky ist eigentlich ein std::vector o.ä.

Die meisten Compiler führen in einem Debug-Build keinerlei Optimierung durch.

Wenn Sie VC verwenden, versuchen Sie es mit einem Release-Build mit aktivierten PDB-Informationen. Dadurch können Sie die optimierte App durchsuchen und sollten dann hoffentlich sehen, was Sie wollen.Beachten Sie jedoch, dass das Debuggen und Nachverfolgen eines optimierten Builds Sie durcheinander bringen wird und Sie Variablen oft nicht direkt überprüfen können, da sie immer nur in Registern landen oder vollständig wegoptimiert werden.Es ist eine „interessante“ Erfahrung...

Wie Greg erwähnt, tun Compiler dies nicht im Debug-Modus.Es ist in Ordnung, dass Debug-Builds langsamer sind als ein Produkt-Build, aber sie sollten nicht häufiger abstürzen:Und wenn Sie auf eine Tail-Call-Optimierung angewiesen sind, können sie genau das tun.Aus diesem Grund ist es oft am besten, den Tail Call als normale Schleife umzuschreiben.:-(

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top