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);
}
c#
.net
optimization
tail-recursion
ripper234
quelle
quelle
preemptive
aufteilt, nämlich (z. B. Fakultätsalgorithmus) undNon-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?Antworten:
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
while
Schleife 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 .
quelle
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.
By the way, wie sie darauf hingewiesen wurde, ist es erwähnenswert, dass Endrekursion wird auf x64 optimiert.
quelle
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 .
quelle
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.
quelle
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.
quelle
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
Proposal
Problem 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
Lassen Sie mich auch erwähnen (als zusätzliche Information): Wenn wir ein kompiliertes Lambda unter Verwendung von Ausdrucksklassen im
System.Linq.Expressions
Namespace generieren , gibt es ein Argument namens 'tailCall', das, wie in seinem Kommentar erläutert, es istIch 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:
quelle