Warum wäre eine rekursive Version einer Funktion schneller als eine iterative Version in C?

Ich habe Ihren Code lokal kompiliert und ausgeführt. Durch Verschieben des printf außerhalb des zeitgesteuerten Blocks werden beide Versionen jedes Mal in ~ 5 ms ausgeführt.

Ein zentraler Fehler in Ihrem Timing ist also, dass Sie das komplexe Biest von printf messen und seine Laufzeit den Code, den Sie eigentlich messen wollen, in den Schatten stellt.

Meine main() -Funktion sieht jetzt so aus:

  

Ist meine Art der Zeitmessung falsch?

Ja. In den kurzen Zeitspannen, die Sie messen, kann der Scheduler einen großen Einfluss auf Ihr Programm haben. Sie müssen Ihren Test entweder länger machen, um solche Unterschiede zu mitteln, oder stattdessen CLOCK_PROCESS_CPUTIME_ID verwenden, um die von Ihrem Prozess verwendete CPU-Zeit zu messen.

Zum einen vermisst Ihr rekursiver Schritt return :

Sollte sein:

Dieser Überblick bewirkt, dass der Rückgabewert von descgrad undefiniert ist, so dass der Compiler überhaupt keinen Code erzeugen muss;)

Zunächst haben Sie in der Zeit, die Sie messen wollten, einen Ausdruck eingefügt. Es ist immer ein riesiges No-No, weil es Ihren Prozess während der Konsolenausgabe anhalten kann und höchstwahrscheinlich auch. Tatsächlich kann JEDER Systemaufruf solche Zeitmessungen vollständig löschen.

Und zweitens können Scheduler-Interrupts, wie bereits erwähnt, in einem kurzen Zeitraum eine große Auswirkung haben.

Das ist nicht perfekt, aber probier das mal für deinen main und du wirst sehen, dass es tatsächlich sehr wenig Unterschied gibt. Wenn Sie die Schleifenanzahl erhöhen, nähert sich das Verhältnis 1.0.

}

BEARBEITEN: Nachdem ich die zerlegte Ausgabe mit objdump -dS betrachtet habe, habe ich ein paar Dinge bemerkt:
   Bei -O3-Optimierung optimiert der obige Code den Funktionsaufruf vollständig. Es produziert jedoch immer noch Code für die beiden Funktionen und keiner ist tatsächlich rekursiv.

Zweitens ist mit -O0, so dass der resultierende Code tatsächlich rekursiv ist, die rekursive Version buchstäblich eine Billion langsamer. Meine Vermutung ist, weil der Aufruf-Stack Variablen zwingt, im Speicher zu landen, wo die iterative Version keine Register und / oder Cache mehr hat.

Die akzeptierte Antwort ist falsch .

Es besteht ein Unterschied in den Laufzeiten der iterativen Funktion und der rekursiven Funktion und der Grund ist die Compileroptimierung -foptimize-sibling-calls hinzugefügt von -O3 .

Zuerst der Code:

Bisherige Beiträge haben richtig darauf hingewiesen, dass Sie viele Male iterieren müssen, um Umgebungseinflüsse zu vermeiden. In Anbetracht dessen habe ich Ihre Differenzierungsfunktion zugunsten von time.h function auf difftime data verworfen, da bei vielen Iterationen alles, was feiner als eine Sekunde ist, bedeutungslos ist. Außerdem habe ich die printfs im Benchmark entfernt.

Ich habe auch einen Fehler in der rekursiven Implementierung behoben. Die if-Anweisung Ihres ursprünglichen Codes wurde auf time_t überprüft, was inkorrekt ist (oder sich zumindest von der iterativen Implementierung unterscheidet). Die iterativen Schleifen während fabs () & gt; Genauigkeit, daher sollte die rekursive Funktion nicht rekursiv sein, wenn fabs & lt; = genau ist. Das Hinzufügen von Iterationszählern zu beiden Funktionen bestätigt, dass dieser Fix die Funktion logisch äquivalent macht.

Kompilieren und Ausführen mit fabs(xnew-xo) < precision :

Kompilieren und Ausführen ohne -O3

Unter keiner Optimierung führt Iteration BETTER als Rekursion durch.

Unter -O3 optimization führt die Rekursion jedoch zehn Millionen Iterationen in weniger als einer Sekunde durch. Der Grund ist, dass -O3 hinzugefügt wird, wodurch Geschwister- und Tail-rekursive Aufrufe optimiert werden. Genau das nutzt Ihre rekursive Funktion.

Um sicher zu sein, habe ich es alle -foptimize-sibling-calls Optimierungen EXCEPT -O3 :

Rekursion, ohne die Tail-Call-Optimierung, führt schlechter als Iteration aus, genauso wie wenn sie mit NO-Optimierung kompiliert wird. Lesen Sie hier über Compiler-Optimierungen .

BEARBEITEN:

Als Bestätigung der Korrektheit habe ich meinen Code aktualisiert, einschließlich der Rückgabewerte. Außerdem setzte ich zwei statische Variablen auf 0 und erhöhte sie jeweils bei Rekursion und Iteration, um die korrekte Ausgabe zu überprüfen:

Die Ausgabe:

Die Antworten sind die gleichen und die Wiederholung ist die gleiche.

Interessant ist auch, dass das statische Variablen-Fetching / Incrementing einen erheblichen Einfluss auf die Tail-Call-Optimierung hat, aber die Rekursion immer noch die Iteration übertrifft.

Erstens scheint clock_gettime die Wanduhrzeit zu messen, nicht Ausführungszeit. Zweitens ist die tatsächliche Zeit, die Sie messen, die Ausführungszeit von printf , nicht die Ausführungszeit Ihrer Funktion. Und drittens, wenn Sie printf das erste Mal aufrufen, ist es nicht im Speicher, also es muss mit eingemischt werden, was signifikante Datenträger-IO mit sich bringt. Die Reihenfolge umkehren Sie führen die Tests aus, und die Ergebnisse werden ebenfalls umgekehrt.

Wenn Sie einige signifikante Messungen erhalten möchten, müssen Sie sicherstellen das

1. nur der Code, den Sie messen möchten, befindet sich in den Messschleifen, oder zumindest ist der zusätzliche Code sehr gering im Vergleich zu dem, was Sie sind Messen,
2. Sie tun etwas mit den Ergebnissen, so dass der Compiler das nicht kann Optimiere den gesamten Code (kein Problem in deinen Tests),
3. Sie führen den zu messenden Code eine große Anzahl aus Zeiten, den Durchschnitt nehmend,
4. Sie messen die CPU-Zeit und nicht die Wanduhrzeit und
5. Sie stellen sicher, dass alles eingeloggt ist, bevor Sie das Programm starten Messungen.

In vielen Fällen sind bei modernen Hardware-Cache-Fehlern der limitierende Leistungsfaktor für kleine Schleifenkonstrukte. Eine rekursive Implementierung erzeugt weniger wahrscheinlich Cache-Misses auf dem Befehlspfad.