C Sprache
In der Programmiersprache C ist es einfach, eine Schwanzrekursion durchzuführen :
int foo(...) {
return foo(...);
}
Geben Sie einfach den Rückgabewert des rekursiven Aufrufs zurück. Es ist besonders wichtig, wenn sich diese Rekursion tausend- oder sogar millionenfach wiederholen kann. Es würde viel Speicher auf dem Stapel verbrauchen .
Rost
Jetzt habe ich eine Rust-Funktion, die sich millionenfach rekursiv aufruft:
fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
match input.read(&mut [0u8]) {
Ok ( 0) => Ok(()),
Ok ( _) => read_all(input),
Err(err) => Err(err),
}
}
(Dies ist ein minimales Beispiel, das reale ist komplexer, aber es erfasst die Hauptidee)
Hier wird der Rückgabewert des rekursiven Aufrufs unverändert zurückgegeben, aber:
Garantiert es, dass der Rust-Compiler eine Schwanzrekursion anwendet?
Wenn wir beispielsweise eine Variable deklarieren, die wie a zerstört werden muss std::Vec
, wird sie dann unmittelbar vor dem rekursiven Aufruf (der eine Schwanzrekursion ermöglicht) oder nach der Rückkehr des rekursiven Aufrufs (der die Schwanzrekursion verbietet) zerstört?
Antworten:
Endaufruf sind garantiertwenn Ihre rekursive Funktion in genannt wird Schwanz Position (im Grunde die letzte Anweisung der Funktion).
Die Tail-Call- Optimierung wird von Rust niemals garantiert, obwohl der Optimierer sie möglicherweise ausführen möchte.
Nach meinem Verständnis ist dies einer der Knackpunkte, da eine Änderung der Position zerstörter Stapelvariablen umstritten wäre.
Siehe auch:
quelle
Die Antwort von Shepmaster erklärt, dass die Optimierung von Tail Calls, die ich lieber als Eliminierung von Tail Calls bezeichne, in Rust nicht garantiert ist. Aber das ist nicht die ganze Geschichte! Es gibt viele Möglichkeiten zwischen "nie passiert" und "garantiert". Schauen wir uns an, was der Compiler mit echtem Code macht.
Kommt es in dieser Funktion vor?
Ab jetzt ist die neueste Version von Rust auf Compiler Explorer ist 1,39, und es hat nicht den Schwanz Anruf zu beseitigen
read_all
.Beachten Sie diese Zeile :
call qword ptr [rip + example::read_all@GOTPCREL]
. Das ist der rekursive Aufruf. Wie Sie an seiner Existenz erkennen können, wurde es nicht beseitigt.Vergleichen Sie dies mit einer äquivalenten Funktion mit einem expliziten
loop
:die keinen zu eliminierenden Tail-Aufruf hat und daher zu einer Funktion mit nur einer kompiliert wird
call
(zur berechneten Adresse voninput.read
).Naja. Vielleicht ist Rust nicht so gut wie C. Oder doch?
Kommt es in C vor?
Hier ist eine rekursive Funktion in C, die eine sehr ähnliche Aufgabe ausführt:
Dies sollte für den Compiler sehr einfach zu beseitigen sein. Der rekursive Aufruf befindet sich ganz unten in der Funktion und C muss sich nicht um die Ausführung von Destruktoren kümmern. Trotzdem gibt es diesen rekursiven Tail Call , der ärgerlicherweise nicht beseitigt wird:
Es stellt sich heraus, dass die Tail-Call-Optimierung auch in C nicht garantiert ist. Ich habe Clang und gcc unter verschiedenen Optimierungsstufen ausprobiert, aber nichts, was ich versucht habe, würde diese ziemlich einfache rekursive Funktion in eine Schleife verwandeln.
Passiert das jemals ?
Okay, das ist nicht garantiert. Kann der Compiler das überhaupt? Ja! Hier ist eine Funktion, die Fibonacci-Zahlen über eine schwanzrekursive innere Funktion berechnet:
Der Tail-Aufruf wird nicht nur eliminiert,
fibonacci_lr
sondern die gesamte Funktion wird eingebundenfibonacci
, was nur 12 Anweisungen ergibt (und keinecall
in Sicht ist):Wenn Sie dies mit einer äquivalenten
while
Schleife vergleichen , generiert der Compiler fast dieselbe Assembly.Was ist der Punkt?
Sie sollten sich wahrscheinlich nicht auf Optimierungen verlassen, um Tail Calls zu eliminieren, weder in Rust noch in C. Es ist schön, wenn es passiert, aber wenn Sie sicher sein müssen, dass eine Funktion in einer engen Schleife kompiliert wird, ist dies zumindest für den sichersten Weg Jetzt ist eine Schleife zu verwenden.
quelle