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

111

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);
}
zrywak234
źródło
Czytałem dziś książkę o Strukturach Danych, która dzieli funkcję rekurencyjną na dwie, a mianowicie preemptive(np. Algorytm silni) i Non-preemptive(np. Funkcję Ackermanna). Autor podał tylko dwa przykłady, o których wspomniałem, nie podając właściwego uzasadnienia tego rozwidlenia. Czy to bifurkacja jest taka sama jak rekurencyjne funkcje ogona i nieogonowe?
RBT
5
Przydatna rozmowa Jona Skeeta i Scotta Hanselmana na ten temat w 2016 youtu.be/H2KkiRbDZyc?t=3302
Daniel B
@RBT: Myślę, że jest inaczej. Odnosi się do liczby wywołań rekurencyjnych. Wywołania ogonowe dotyczą wywołań, które pojawiają się w pozycji ogona, tj. Ostatnią rzeczą, jaką wykonuje funkcja, jest więc zwracanie wyniku bezpośrednio z wywoływanego.
JD

Odpowiedzi:

84

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ć .

ShuggyCoUk
źródło
2
Zobacz także ten post: social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/… gdzie odkryłem, że ten ogon jest wolniejszy niż zwykłe połączenie. Eep!
cokół
77

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.

Noldorin
źródło
3
To też może okazać się pomocne: weblogs.asp.net/podwysocki/archive/2008/07/07/…
Noldorin
Nie ma sprawy, cieszę się, że jest to pomocne.
Noldorin
17
Dziękuję za zacytowanie, ponieważ teraz jest to 404!
Roman Starkov
3
Link jest teraz naprawiony.
luksan
15

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 .

devinbost
źródło
8

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.

Alexandre Brisebois
źródło
8
Jitter x64 robi to, ale kompilator C # nie
Mark Sowul
dzięki za informację. To jest białe inaczej niż wcześniej myślałem.
Alexandre Brisebois
3
Żeby wyjaśnić te dwa komentarze, C # nigdy nie emituje kodu operacji CIL „tail” i uważam, że jest to nadal prawdą w 2017 r. Jednak dla wszystkich języków ten kod jest zawsze doradczy tylko w tym sensie, że odpowiednie drgania (x86, x64 ) po cichu zignoruje to, jeśli różne warunki nie zostaną spełnione (no cóż, nie ma błędu poza możliwym przepełnieniem stosu ). To wyjaśnia, dlaczego jesteś zmuszony podążać za „ogonem” z „ret” - tak jest w tym przypadku. W międzyczasie fluktuacje mogą również swobodnie stosować optymalizację, gdy w CIL nie ma przedrostka „ogon”, ponownie, jeśli uznano to za stosowne, i niezależnie od języka .NET.
Glenn Slayden
3

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.

naiem
źródło
Trampoliny są inwazyjne (są globalną zmianą w konwencji wywoływania), ~ 10 razy wolniejsze niż właściwa eliminacja wywołań ogonowych i zaciemniają wszystkie informacje o śladach stosu, co znacznie utrudnia debugowanie i kod profilu
JD
1

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();
styl życia
źródło