Dlaczego .NET / C # nie optymalizuje się pod kątem rekurencji wywołań ogonowych?

Znalazłem to pytanie, które języki optymalizują rekurencję ogonów. Dlaczego C # nie optymalizuje rekurencji ogonowej, jeśli jest to możliwe?

W konkretnym przypadku, dlaczego ta metoda nie jest zoptymalizowana w pętli ( 32-bitowy program Visual Studio 2008 , jeśli ma to znaczenie) ?:

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

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

    Foo(i+1);
}

Kompilacja JIT jest trudnym działaniem równoważącym między nie spędzaniem zbyt wiele czasu na wykonywaniu fazy kompilacji (w ten sposób znacznie spowalniając krótkotrwałe aplikacje) a niewystarczającą analizą, aby utrzymać konkurencyjność aplikacji w dłuższej perspektywie dzięki standardowej kompilacji z wyprzedzeniem .

Co ciekawe, etapy kompilacji NGen nie są ukierunkowane na bardziej agresywne optymalizacje. Podejrzewam, że dzieje się tak dlatego, że po prostu nie chcą mieć błędów, w których zachowanie zależy od tego, czy JIT czy NGen były odpowiedzialne za kod maszynowy.

Sam CLR obsługuje optymalizację wywołań końcowych, ale kompilator specyficzny dla języka musi wiedzieć, jak wygenerować odpowiedni kod operacji, a JIT musi chcieć go uszanować. Fsc F # wygeneruje odpowiednie rozkazy (chociaż dla prostej rekurencji może po prostu przekształcić całość whilebezpośrednio w pętlę). CSC C # nie.

Zobacz ten post na blogu, aby uzyskać szczegółowe informacje (prawdopodobnie nieaktualne, biorąc pod uwagę ostatnie zmiany w JIT). Zauważ, że zmiany CLR dla wersji 4.0 x86, x64 i ia64 będą to uwzględniać .

To przesłanie opinii w witrynie Microsoft Connect powinno odpowiedzieć na Twoje pytanie. Zawiera oficjalną odpowiedź firmy Microsoft, więc polecam to.

Dzieki za sugestie. Rozważaliśmy emitowanie instrukcji wywołań końcowych w wielu punktach podczas opracowywania kompilatora C #. Istnieją jednak pewne subtelne problemy, które zmusiły nas do uniknięcia tego do tej pory: 1) W rzeczywistości użycie instrukcji .tail w CLR wiąże się z nietrywialnymi kosztami ogólnymi (nie jest to tylko instrukcja skoku, ponieważ wywołania tail ostatecznie stają się w wielu mniej rygorystycznych środowiskach, takich jak środowiska uruchomieniowe języka funkcjonalnego, w których wywołania końcowe są mocno zoptymalizowane). 2) Istnieje kilka prawdziwych metod C #, w których byłoby legalne emitowanie wywołań końcowych (inne języki zachęcają do wzorców kodowania, które mają więcej rekurencji ogona, a wiele osób, które w dużym stopniu polegają na optymalizacji wywołań końcowych, faktycznie dokonuje globalnego ponownego zapisu (na przykład transformacji z przejściem kontynuacji), aby zwiększyć ilość rekurencji ogonowej). 3) Częściowo z powodu 2) przypadki, w których metody C # przepełnienie stosu z powodu głębokiej rekursji, która powinna się powieść, są dość rzadkie.

Wszystko to powiedziawszy, nadal się temu przyglądamy i być może w przyszłej wersji kompilatora znajdziemy pewne wzorce, w których emitowanie instrukcji .tail ma sens.

Nawiasem mówiąc, jak wskazano, warto zauważyć, że rekurencja ogona jest zoptymalizowana na x64.

C # nie optymalizuje rekurencji wywołań ogonowych, ponieważ do tego służy F #!

Aby uzyskać szczegółowe informacje na temat warunków, które uniemożliwiają kompilatorowi C # wykonywanie optymalizacji wywołań końcowych, zobacz ten artykuł: Warunki wywołania końcowego JIT CLR .

Współdziałanie między C # i F #

Języki C # i F # współpracują bardzo dobrze, a ponieważ środowisko uruchomieniowe języka. Aby zapoznać się z przykładem, który pokazuje, jak łatwo jest wywołać kod F # z kodu C #, zobacz Wywoływanie kodu F # z kodu C # ; Aby zapoznać się z przykładem wywoływania funkcji C # z kodu F #, zobacz Wywoływanie funkcji C # z F # .

Aby uzyskać współdziałanie delegata, zobacz ten artykuł: Delegowanie współdziałania między F #, C # i Visual Basic .

Teoretyczne i praktyczne różnice między C # a F #

Oto artykuł, który obejmuje niektóre różnice i wyjaśnia różnice projektowe rekurencji wywołań ogonowych między C # i F #: Generowanie kodu wywołania ogonowego w językach C # i F # .

Oto artykuł z przykładami w językach C #, F # i C ++ \ CLI: Adventures in Tail Recursion in C #, F # i C ++ \ CLI

Główną teoretyczną różnicą jest to, że C # jest zaprojektowany z pętlami, podczas gdy F # jest zaprojektowany na zasadach rachunku Lambda. Bardzo dobrą książkę o zasadach rachunku Lambda można znaleźć w tej bezpłatnej książce: Structure and Interpretation of Computer Programs, autorstwa Abelsona, Sussmana i Sussmana .

Aby uzyskać bardzo dobry artykuł wprowadzający na temat wywołań ogonowych w języku F #, zobacz ten artykuł: szczegółowe wprowadzenie do wywołań ogonowych w języku F # . Na koniec, oto artykuł, który omawia różnicę między rekurencją non-tail a rekurencją tail-call (w F #): Rekursja ogonowa vs. rekurencja non-tail w Fis .

Niedawno powiedziano mi, że kompilator C # dla wersji 64-bitowej optymalizuje rekurencję ogona.

C # również to implementuje. Przyczyną, dla której nie zawsze jest stosowana, jest to, że reguły stosowane do stosowania rekurencji ogonowej są bardzo surowe.

Możesz użyć techniki trampoliny do rekurencyjnych funkcji ogonowych w C # (lub Javie). Jednak lepszym rozwiązaniem (jeśli zależy ci tylko na wykorzystaniu stosu) jest użycie tej małej metody pomocniczej do zawijania części tej samej funkcji rekurencyjnej i uczynienia jej iteracyjną, zachowując czytelność funkcji.

Jak wspomniano w innych odpowiedziach, CLR obsługuje optymalizację połączeń końcowych i wydaje się, że w przeszłości podlegał stopniowym ulepszeniom. Jednak obsługa go w C # ma otwarty Proposalproblem w repozytorium git do projektowania języka programowania C # Obsługa ogona rekurencji # 2544 .

Możesz tam znaleźć przydatne szczegóły i informacje. Na przykład wspomniany @jaykrell

Podam to, co wiem.

Czasami wywołanie ogonowe to wynik korzystny dla wszystkich. Może oszczędzać procesor. jmp jest tańszy niż call / ret. Może oszczędzać stos. Dotykanie mniejszej ilości stosu zapewnia lepszą lokalizację.

Czasami tailcall to utrata wydajności, wygrana na stackach. Środowisko CLR ma złożony mechanizm, w którym przekazuje więcej parametrów do wywoływanego niż odebrany wywołujący. Mam na myśli konkretnie więcej miejsca na stosy dla parametrów. To jest powolne. Ale oszczędza stos. Zrobi to tylko z ogonem. prefiks.

Jeśli parametry wywołującego są większe niż parametry wywoływane, zwykle jest to dość łatwa transformacja korzystna dla wszystkich. Mogą istnieć czynniki, takie jak zmiana pozycji parametru z zarządzanej na liczbę całkowitą / zmiennoprzecinkową oraz generowanie dokładnych map stosu i tym podobnych.

Jest jeszcze jeden punkt widzenia - algorytmy, które wymagają eliminacji wywołań ogonowych, aby móc przetwarzać dowolnie duże dane ze stałym / małym stosem. Nie chodzi o wydajność, ale o zdolność do biegania.

Wspomnę również (jako dodatkowe informacje), gdy generujemy skompilowaną lambdę przy użyciu klas wyrażeń w System.Linq.Expressionsprzestrzeni nazw, istnieje argument o nazwie „tailCall”, który, jak wyjaśniono w komentarzu, jest

Wartość logiczna, która wskazuje, czy optymalizacja wywołań ogona zostanie zastosowana podczas kompilowania utworzonego wyrażenia.

Jeszcze nie próbowałem i nie jestem pewien, jak może pomóc w związku z twoim pytaniem, ale prawdopodobnie ktoś może spróbować i może się przydać w niektórych scenariuszach:

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

var myFunc =  myFuncExpression.Compile();