Warum optimiert .NET / C # nicht für die Tail-Call-Rekursion?

111

Ich fand diese Frage, welche Sprachen die Schwanzrekursion optimieren. Warum optimiert C # die Schwanzrekursion nicht, wann immer dies möglich ist?

Warum wird diese Methode für einen konkreten Fall nicht in einer Schleife optimiert ( Visual Studio 2008 32-Bit, wenn dies wichtig ist)?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}
ripper234
quelle
Ich habe heute ein Buch über Datenstrukturen gelesen, das die rekursive Funktion in zwei Teile preemptiveaufteilt, nämlich (z. B. Fakultätsalgorithmus) und Non-preemptive(z. B. Ackermann-Funktion). Der Autor gab nur zwei Beispiele an, die ich erwähnt habe, ohne eine angemessene Begründung für diese Gabelung zu geben. Ist diese Gabelung gleichbedeutend mit rekursiven Funktionen für Schwanz und Nicht-Schwanz?
RBT
5
Nützliches Gespräch darüber von Jon Skeet und Scott Hanselman am 2016 youtu.be/H2KkiRbDZyc?t=3302
Daniel B
@RBT: Ich denke das ist anders. Es bezieht sich auf die Anzahl der rekursiven Aufrufe. Bei Tail Calls handelt es sich um Anrufe, die in der Tail-Position angezeigt werden, dh als letztes, was eine Funktion tut, gibt sie das Ergebnis direkt vom Angerufenen zurück.
JD

Antworten:

84

Die JIT-Kompilierung ist ein schwieriger Spagat zwischen nicht zu viel Zeit für die Kompilierungsphase (wodurch kurzlebige Anwendungen erheblich verlangsamt werden) und nicht genügend Analysen, um die Anwendung langfristig wettbewerbsfähig zu halten, mit einer Standard-Kompilierung vor der Zeit .

Interessanterweise zielen die NGen- Kompilierungsschritte nicht darauf ab, ihre Optimierungen aggressiver zu gestalten. Ich vermute, das liegt daran, dass sie einfach keine Fehler haben wollen, bei denen das Verhalten davon abhängt, ob die JIT oder NGen für den Maschinencode verantwortlich waren.

Die CLR selbst unterstützt die Tail-Call-Optimierung, aber der sprachspezifische Compiler muss wissen, wie der relevante Opcode generiert wird, und die JIT muss bereit sein, ihn zu respektieren. F # 's fsc werden die entsprechenden OP - Codes erzeugen (wenn auch für eine einfache Rekursion kann es nur das Ganze in eine umwandeln whileSchleife direkt). Csc von C # nicht.

In diesem Blog-Beitrag finden Sie einige Details (möglicherweise aufgrund der jüngsten JIT-Änderungen veraltet). Beachten Sie, dass die CLR-Änderungen für 4.0 x86, x64 und ia64 dies berücksichtigen .

ShuggyCoUk
quelle
2
Siehe auch diesen Beitrag: social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/… wobei ich feststelle, dass der Schwanz langsamer ist als ein normaler Anruf. Eep!
Sockel
77

Diese Microsoft Connect-Feedback-Übermittlung sollte Ihre Frage beantworten. Es enthält eine offizielle Antwort von Microsoft, daher würde ich empfehlen, dies zu tun.

Danke für den Vorschlag. Wir haben an mehreren Stellen in der Entwicklung des C # -Compilers erwogen, Anweisungen für Tail Calls zu senden. Es gibt jedoch einige subtile Probleme, die uns bisher dazu veranlasst haben, dies zu vermeiden: 1) Die Verwendung des .tail-Befehls in der CLR verursacht tatsächlich nicht triviale Gemeinkosten (es handelt sich nicht nur um einen Sprungbefehl, da Tail-Aufrufe letztendlich werden in vielen weniger strengen Umgebungen wie Laufzeitumgebungen mit funktionaler Sprache, in denen Tail Calls stark optimiert sind). 2) Es gibt nur wenige echte C # -Methoden, bei denen es legal wäre, Tail-Aufrufe auszugeben (andere Sprachen fördern Codierungsmuster mit mehr Tail-Rekursion). und viele, die sich stark auf die Tail-Call-Optimierung verlassen, schreiben tatsächlich global neu (z. B. Continuation Passing-Transformationen), um die Tail-Rekursion zu erhöhen. 3) Teilweise aufgrund von 2) sind Fälle, in denen C # -Methoden aufgrund einer tiefen Rekursion, die erfolgreich gewesen sein sollte, überlaufen, ziemlich selten.

Alles in allem werden wir uns dies weiterhin ansehen und möglicherweise in einer zukünftigen Version des Compilers einige Muster finden, bei denen es sinnvoll ist, .tail-Anweisungen auszugeben.

By the way, wie sie darauf hingewiesen wurde, ist es erwähnenswert, dass Endrekursion wird auf x64 optimiert.

Noldorin
quelle
3
Dies könnte auch hilfreich sein: weblogs.asp.net/podwysocki/archive/2008/07/07/…
Noldorin
Kein Problem, ich bin froh, dass Sie es hilfreich finden.
Noldorin
17
Danke, dass Sie es zitiert haben, denn es ist jetzt ein 404!
Roman Starkov
3
Der Link ist jetzt behoben.
Luksan
15

C # optimiert nicht für die Tail-Call-Rekursion, da F # dafür gedacht ist!

Weitere Informationen zu den Bedingungen, die den C # -Compiler daran hindern, Tail-Call-Optimierungen durchzuführen, finden Sie in diesem Artikel: JIT CLR-Tail-Call-Bedingungen .

Interoperabilität zwischen C # und F #

C # und F # arbeiten sehr gut zusammen. Da die .NET Common Language Runtime (CLR) unter Berücksichtigung dieser Interoperabilität entwickelt wurde, wurde jede Sprache mit Optimierungen entwickelt, die für ihre Absichten und Zwecke spezifisch sind. Ein Beispiel, das zeigt, wie einfach es ist, F # -Code aus C # -Code aufzurufen, finden Sie unter Aufrufen von F # -Code aus C # -Code . Ein Beispiel für das Aufrufen von C # -Funktionen aus F # -Code finden Sie unter Aufrufen von C # -Funktionen aus F # .

Informationen zur Interoperabilität von Delegaten finden Sie in diesem Artikel: Interoperabilität zwischen F #, C # und Visual Basic delegieren .

Theoretische und praktische Unterschiede zwischen C # und F #

In diesem Artikel werden einige der Unterschiede behandelt und die Entwurfsunterschiede bei der Tail-Call-Rekursion zwischen C # und F # erläutert: Generieren des Tail-Call-Opcodes in C # und F # .

Hier ist ein Artikel mit einigen Beispielen in C #, F # und C ++ \ CLI: Abenteuer in der Schwanzrekursion in C #, F # und C ++ \ CLI

Der hauptsächliche theoretische Unterschied besteht darin, dass C # mit Schleifen entworfen wird, während F # nach Prinzipien der Lambda-Rechnung entworfen wird. Ein sehr gutes Buch über die Prinzipien der Lambda-Rechnung finden Sie in diesem kostenlosen Buch: Struktur und Interpretation von Computerprogrammen von Abelson, Sussman und Sussman .

Einen sehr guten Einführungsartikel zu Tail Calls in F # finden Sie in diesem Artikel: Detaillierte Einführung in Tail Calls in F # . Schließlich ist hier ein Artikel, der den Unterschied zwischen Nicht-Schwanz-Rekursion und Schwanz-Anruf-Rekursion (in F #) behandelt: Schwanz-Rekursion vs. Nicht-Schwanz-Rekursion in Fis .

Devinbost
quelle
8

Mir wurde kürzlich gesagt, dass der C # -Compiler für 64-Bit die Schwanzrekursion optimiert.

C # implementiert dies ebenfalls. Der Grund, warum es nicht immer angewendet wird, ist, dass die Regeln für die Anwendung der Schwanzrekursion sehr streng sind.

Alexandre Brisebois
quelle
8
Der x64- Jitter tut dies, der C # -Compiler jedoch nicht
Mark Sowul
Danke für die Auskunft. Das ist weiß anders als ich vorher dachte.
Alexandre Brisebois
3
Um diese beiden Kommentare zu verdeutlichen, gibt C # niemals den CIL-Opcode 'tail' aus, und ich glaube, dass dies auch 2017 noch zutrifft. Für alle Sprachen ist dieser Opcode jedoch immer nur in dem Sinne empfehlenswert, dass die jeweiligen Jitter (x86, x64) ) ignoriert es stillschweigend, wenn verschiedene Bedingungen nicht erfüllt sind (naja, kein Fehler außer möglichem Stapelüberlauf ). Dies erklärt, warum Sie gezwungen sind, "Schwanz" mit "Ret" zu folgen - es ist für diesen Fall. In der Zwischenzeit können die Jitter die Optimierung auch anwenden, wenn in der CIL kein "Tail" -Präfix vorhanden ist, was wiederum als angemessen erachtet wird und unabhängig von der .NET-Sprache.
Glenn Slayden
3

Sie können die Trampolintechnik für schwanzrekursive Funktionen in C # (oder Java) verwenden. Die bessere Lösung (wenn Sie sich nur für die Stapelauslastung interessieren) besteht jedoch darin, diese kleine Hilfsmethode zu verwenden, um Teile derselben rekursiven Funktion zu verpacken und iterativ zu machen, während die Funktion lesbar bleibt.

naiem
quelle
Trampoline sind invasiv (sie stellen eine globale Änderung der Aufrufkonvention dar), ~ 10x langsamer als die ordnungsgemäße Eliminierung von Tail-Anrufen und verschleiern alle Stack-Trace-Informationen, was das Debuggen und Profilieren von Code erheblich erschwert
JD
1

Wie bereits erwähnt, unterstützt CLR die Tail-Call-Optimierung und scheint historisch gesehen schrittweise verbessert worden zu sein. Die Unterstützung in C # hat jedoch ein offenes ProposalProblem im Git-Repository für das Design der C # -Programmiersprache Support Tail Recursion # 2544 .

Dort finden Sie einige nützliche Details und Informationen. Zum Beispiel @jaykrell erwähnt

Lass mich geben, was ich weiß.

Manchmal ist Tailcall eine Win-Win-Leistung. Es kann CPU sparen. jmp ist billiger als call / ret Es kann Stack sparen. Wenn Sie weniger Stapel berühren, wird die Lokalität verbessert.

Manchmal ist Tailcall ein Leistungsverlust, Stack Win. Die CLR verfügt über einen komplexen Mechanismus, mit dem mehr Parameter an den Angerufenen übergeben werden können, als der Anrufer erhalten hat. Ich meine speziell mehr Stapelplatz für Parameter. Das ist langsam. Aber es spart Stapel. Dies geschieht nur mit dem Schwanz. Präfix.

Wenn die Aufruferparameter stapelgroß als die Angerufenenparameter sind, ist dies normalerweise eine ziemlich einfache Win-Win-Transformation. Es kann Faktoren wie die Änderung der Parameterposition von verwaltet zu Integer / Float und die Generierung präziser StackMaps und dergleichen geben.

Nun gibt es einen anderen Winkel, nämlich den von Algorithmen, die eine Tailcall-Eliminierung erfordern, um beliebig große Daten mit festem / kleinem Stapel verarbeiten zu können. Hier geht es nicht um Leistung, sondern um die Fähigkeit, überhaupt zu laufen.

Lassen Sie mich auch erwähnen (als zusätzliche Information): Wenn wir ein kompiliertes Lambda unter Verwendung von Ausdrucksklassen im System.Linq.ExpressionsNamespace generieren , gibt es ein Argument namens 'tailCall', das, wie in seinem Kommentar erläutert, es ist

Ein Bool, das angibt, ob beim Kompilieren des erstellten Ausdrucks die Tail-Call-Optimierung angewendet wird.

Ich habe es noch nicht ausprobiert und bin mir nicht sicher, wie es im Zusammenhang mit Ihrer Frage helfen kann, aber wahrscheinlich kann es jemand versuchen und kann in einigen Szenarien nützlich sein:


var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func<  >>(body:  , tailCall: true, parameters:  );

var myFunc =  myFuncExpression.Compile();
Lebensstil
quelle