C-Tail-Call-Optimierung

Ich höre oft Leute sagen, dass C keine Tail-Call-Eliminierung durchführt. Auch wenn es nicht vom Standard garantiert wird, wird es in der Praxis nicht sowieso von einer anständigen Implementierung durchgeführt? Angenommen, Sie zielen nur auf ausgereifte, gut implementierte Compiler ab und kümmern sich nicht um die absolute maximale Portabilität auf primitive Compiler, die für obskure Plattformen geschrieben wurden. Ist es dann vernünftig, sich auf die Eliminierung von Tail-Calls in C zu verlassen?

Was war auch der Grund dafür, die Tail-Call-Optimierung aus dem Standard herauszulassen?

Aussagen wie “C führt keine Tail-Call-Eliminierung durch” machen keinen Sinn. Wie Sie selbst richtig bemerkt haben, hängen solche Dinge ganz von der Implementierung ab. Und ja, jede anständige Implementierung kann Tail-Rekursion leicht umwandeln [an equivalent of] Ein Zyklus. Natürlich geben C-Compiler normalerweise keine Garantien dafür, welche Optimierungen in jedem einzelnen Codeabschnitt stattfinden und welche Optimierungen nicht stattfinden. Sie müssen es kompilieren und selbst sehen.

Obwohl moderne Compiler eine Tail-Call-Optimierung durchführen KÖNNEN, wenn Sie Optimierungen aktivieren, werden Ihre Debug-Builds wahrscheinlich ohne sie ausgeführt, sodass Sie Stack-Traces erhalten und in Code ein- und aussteigen und solche wunderbaren Dinge. In dieser Situation ist eine Tail-Call-Optimierung nicht erwünscht.

Da die Tail-Call-Optimierung nicht immer wünschenswert ist, macht es keinen Sinn, sie Compiler-Autoren vorzuschreiben.

Ich denke, dass Tail-Call-Optimierungen nur dort gewährleistet werden müssen, wo viel der Rekursion erwartet oder erforderlich ist; das heißt, in Sprachen, die einen funktionalen Programmierstil fördern oder erzwingen. (Bei dieser Art von Sprachen finden Sie das vielleicht for oder while Von Schleifen wird entweder dringend abgeraten, sie werden als unelegant empfunden oder fehlen wahrscheinlich sogar vollständig in der Sprache, sodass Sie aus all diesen Gründen und wahrscheinlich noch mehr auf Rekursion zurückgreifen würden.)

Die Programmiersprache C (IMHO) war eindeutig nicht entwickelt mit Blick auf die funktionale Programmierung. Es gibt alle Arten von Schleifenkonstrukten, die im Allgemeinen zugunsten der Rekursion verwendet werden: for, do .. while, while. In einer solchen Sprache würde es nicht viel Sinn machen, Tail-Call-Optimierung in einem Standard vorzuschreiben, da sie nicht unbedingt erforderlich ist, um funktionierende Programme zu garantieren.

Vergleichen Sie dies erneut mit einer funktionalen Programmiersprache, die keine hat while Schleifen: Das bedeutet, Sie werden brauchen Rekursion; was wiederum bedeutet, dass die Sprache sicherstellen muss, dass Stapelüberläufe bei vielen Iterationen kein Problem werden; damit der offizielle Standard für eine solche Sprache könnte sich dafür entscheiden, Tail-Call-Optimierung vorzuschreiben.

PS: Beachten Sie einen kleinen Fehler in meiner Argumentation zum Tail-Call-Optimierung. Gegen Ende erwähne ich Stapelüberläufe. Aber wer sagt, dass Funktionsaufrufe immer einen Stack benötigen? Auf einigen Plattformen könnten Funktionsaufrufe auf völlig andere Weise implementiert werden, und Stapelüberläufe wären niemals ein Problem. Dies wäre ein weiteres Argument dagegen, Tail-Call-Optimierung in einem Standard vorzuschreiben. (Aber verstehen Sie mich nicht falsch, ich sehe die Vorzüge solcher Optimierungen auch ohne Stack!)

Um Ihre letzte Frage zu beantworten: Der Standard sollte auf keinen Fall Aussagen zur Optimierung machen. Es kann Umgebungen geben, in denen die Implementierung mehr oder weniger schwierig ist.

Für diejenigen, die Proof-by-Construction mögen, hier ist Godbolt, der eine nette Tail-Call-Optimierung und Inline durchführt: https://godbolt.org/z/DMleUN

Wenn Sie jedoch die Optimierung auf -O3 kurbeln (oder zweifellos ein paar Jahre warten oder einen anderen Compiler verwenden), entfernt die Optimierung die Schleife/Rekursion vollständig.

Hier ist ein Beispiel, das sogar mit -O2 auf eine einzige Anweisung optimiert wird: https://godbolt.org/z/CNzWex

Der Sprachstandard definiert, wie sich die Sprache verhält, nicht wie Compiler implementiert werden müssen. Optimierung ist nicht vorgeschrieben, weil sie nicht immer erwünscht ist. Compiler bieten Optionen, damit der Benutzer Optimierungen aktivieren kann, wenn er sie wünscht, und sie auch deaktivieren kann. Die Compileroptimierung kann sich auf die Fähigkeit zum Debuggen von Code auswirken (es wird schwieriger, C Zeile für Zeile mit Assembly abzugleichen), daher ist es sinnvoll, die Optimierung nur auf Anforderung des Benutzers durchzuführen.

Es gibt Situationen, in denen die Tail-Call-Optimierung möglicherweise die ABI brechen würde oder zumindest sehr schwierig semantikerhaltend zu implementieren wäre. Denken Sie zum Beispiel an positionsunabhängigen Code in gemeinsam genutzten Bibliotheken: Einige Plattformen erlauben es Programmen, dynamisch mit Bibliotheken zu verknüpfen, um Hauptspeicher zu sparen, wenn verschiedene Anwendungen alle von derselben Funktionalität abhängen. In solchen Fällen wird die Bibliothek einmal geladen und jedem virtuellen Speicher des Programms zugeordnet, als wäre es die einzige Anwendung auf einem System. Unter UNIX und auch einigen anderen Systemen wird dies durch die Verwendung von positionsunabhängigem Code für Bibliotheken erreicht, sodass die Adressierung relativ zu einem Offset erfolgt und nicht absolut zu einem festen Adressraum. Auf vielen Plattformen muss der positionsunabhängige Code jedoch nicht Tail-Call-optimiert werden. Das Problem dabei ist, dass die Offsets zum Navigieren durch das Programm in Registern gehalten werden müssen; auf Intel 32-Bit, %ebx verwendet wird, das ein vom Angerufenen gespeichertes Register ist; andere Plattformen folgen diesem Konzept. Im Gegensatz zu Funktionen, die normale Aufrufe verwenden, müssen diejenigen, die Endaufrufe verwenden, die gespeicherten Register des Aufgerufenen wiederherstellen, bevor sie zur Subroutine abzweigen, nicht wenn sie selbst zurückkehren. Normalerweise ist das kein Problem, da sich die oberste aufrufende Funktion zu diesem Zeitpunkt nicht um den darin gespeicherten Wert kümmert %ebxaber der positionsunabhängige Code hängt von diesem Wert bei jedem einzelnen Sprung-, Aufruf- oder Verzweigungsbefehl ab.

Andere Probleme könnten anstehende Aufräumarbeiten in objektorientierten Sprachen (C++) sein, was bedeutet, dass der letzte Aufruf in einer Funktion nicht wirklich der letzte Aufruf ist – die Aufräumarbeiten sind es. Daher optimiert der Compiler in der Regel nicht, wenn dies der Fall ist.

Ebenfalls setjmp und longjmp sind natürlich problematisch, da dies effektiv bedeutet, dass eine Funktion die Ausführung mehr als einmal beenden kann, bevor sie tatsächlich beendet wird. Schwierig oder unmöglich zur Kompilierzeit zu optimieren!

Es gibt wahrscheinlich mehr technische Gründe, die man sich vorstellen kann. Dies sind nur einige Überlegungen.