C Tail Call optimization
Często słyszę, jak ludzie mówią, że C nie wykonuje eliminacji połączeń ogonowych. Mimo, że nie jest to gwarantowane przez standard, czy nie jest to wykonywane w praktyce przez jakąś przyzwoitą implementację? Zakładając, że kierujesz się tylko dojrzałymi, dobrze zaimplementowanymi kompilatorami i nie dbasz o absolutną maksymalną przenośność do prymitywnych kompilatorów napisanych dla niejasnych platform, czy rozsądne jest polegać na eliminacji wywołań ogonowych w C?
Ponadto, jakie były przesłanki do pozostawienia optymalizacji połączeń ogonowych poza standardem?
8 answers
Stwierdzenia takie jak "C nie wykonuje eliminacji wywołań ogonowych" nie mają sensu. Jak sam dobrze zauważyłeś, takie rzeczy zależą całkowicie od realizacji. I tak, każda porządna implementacja może łatwo przekształcić rekurencję ogonową w [odpowiednik] cyklu. Oczywiście kompilatory C zwykle nie dają żadnych gwarancji co do tego, jakie optymalizacje będą i jakie optymalizacje nie będą miały miejsca w każdym konkretnym fragmencie kodu. Musisz to skompilować i zobaczyć na własne oczy.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-12-15 20:06:26
Aby odpowiedzieć na ostatnie pytanie: standard zdecydowanie nie powinien składać żadnych oświadczeń o optymalizacji. Mogą istnieć środowiska, w których jest to mniej lub bardziej trudne do wdrożenia.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-18 16:28:16
Chociaż nowoczesne Kompilatory mogą optymalizować wywołania ogonowe, jeśli włączysz optymalizacje, Twoje Kompilacje debugowania prawdopodobnie będą działać bez tego, abyś mógł uzyskać ślady stosu i wejść / wyjść z kodu i wspaniałych rzeczy takich jak to. W tej sytuacji optymalizacja połączeń ogonowych nie jest pożądana.
Ponieważ optymalizacja wywołań ogonowych nie zawsze jest pożądana, nie ma sensu zlecać jej pisarzom kompilatorów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-05-01 17:34:55
Myślę, że optymalizacja wywołań ogonowych musi być zagwarantowana tylko wtedy, gdydużo rekursji jest oczekiwane lub wymagane; to znaczy w językach, które zachęcają lub wymuszają styl programowania funkcyjnego. (W przypadku tego typu języków może się okazać, że pętle for lub while są albo zdecydowanie odradzane, postrzegane jako nieeleganckie, albo prawdopodobnie nawet całkowicie nieobecne w języku, więc uciekałbyś się do rekursji z tych wszystkich powodów, i prawdopodobnie nie tylko.)
C język programowania (IMHO) wyraźnie był, a nie zaprojektowany z myślą o programowaniu funkcyjnym. Istnieją wszystkie rodzaje konstrukcji pętli, które są zwykle używane na rzecz rekurencji: for, do .. while, while. W takim języku nie ma sensu zalecać optymalizacji połączeń ogonowych w standardzie, ponieważ nie jest to ściśle wymagane do zagwarantowania pracy programów.
Kontrast z funkcyjnym językiem programowania, który nie ma pętli while: oznacza to, że będziesz need recursion; co z kolei oznacza, że język musi upewnić się, że przy wielu iteracjach przepełnienie stosu nie stanie się problemem; dlatego oficjalny standard dla takiego języka może zalecić optymalizację wywołań ogonowych.
P. S.: zwróć uwagę na drobną wadę w moim argumencie dla optymalizacji połączeń ogonowych. Pod koniec, wspominam przepełnienia stosu. Ale kto powiedział, że wywołania funkcji zawsze wymagają stosu? Na niektórych platformach funkcja wywołania mogą być zaimplementowane w zupełnie inny sposób, a przepełnienia stosów nigdy nie będą problemem. Byłby to kolejny argument przeciwko przepisywaniu optymalizacji wywołań ogonowych w standardzie. (Ale nie zrozum mnie źle, widzę zalety takich optymalizacji, nawet bez stosu!)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-03-25 00:17:05
Standard języka określa, jak język zachowuje się, a nie jak kompilatory są wymagane do implementacji. Optymalizacja nie jest wymagana, ponieważ nie zawsze jest pożądana. Kompilatory zapewniają opcje, dzięki którym użytkownik może włączyć optymalizacje, jeśli sobie tego życzy, i może je również wyłączyć. Optymalizacja kompilatora może mieć wpływ na możliwość debugowania kodu (trudniej jest dopasować C do montażu w sposób liniowy), więc sensowne jest wykonywanie optymalizacji tylko u użytkownika Prośba.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-18 16:35:48
Są sytuacje, w których optymalizacja wywołania ogonowego mogłaby potencjalnie złamać ABI lub przynajmniej być bardzo trudna do zaimplementowania w sposób semantyczny. Pomyśl na przykład o niezależnym od pozycji kodzie w bibliotekach współdzielonych: niektóre platformy pozwalają programom łączyć się dynamicznie z bibliotekami w celu zapisania pamięci głównej, gdy różne aplikacje zależą od tej samej funkcjonalności. W takich przypadkach Biblioteka jest ładowana raz i mapowana do każdej pamięci wirtualnej programu jakby to była jedyna aplikacja w systemie. W systemach UNIX, a także w niektórych innych systemach, jest to osiągane przez użycie kodu niezależnego od pozycji dla bibliotek, tak że adresowanie jest względne do przesunięcia, a nie bezwzględne do stałej przestrzeni adresowej. Jednak na wielu platformach kod niezależny od pozycji nie może być zoptymalizowany. Problem polega na tym, że offsety do poruszania się po programie muszą być przechowywane w rejestrach; na Intel 32-bit, %ebx jest używany, który jest callee zapisane Zarejestruj się; inne platformy podążają za tym pojęciem. W przeciwieństwie do funkcji wykorzystujących zwykłe wywołania, te wdrażające wywołania ogonowe muszą przywrócić zapisane rejestry callee przed rozgałęzieniem się do podprogramu, a nie kiedy same zwracają. Zwykle nie jest to problemem, ponieważ w tym momencie funkcja top most nie dba o wartość przechowywaną w %ebx, ale kod niezależny od pozycji zależy od tej wartości każdego polecenia skoku, wywołania lub gałęzi.
Inne problemy mogą być oczekujące czyszczenie w językach obiektowych (c++), co oznacza, że ostatnie wywołanie funkcji nie jest w rzeczywistości ostatnim wywołaniem-czyszczenie jest. Dlatego kompilator zwykle nie optymalizuje, gdy tak się dzieje.
Również setjmp i longjmp są oczywiście problematyczne, ponieważ skutecznie oznacza to, że funkcja może zakończyć wykonywanie więcej niż jeden raz, zanim faktycznie się skończy. Trudne lub niemożliwe do optymalizacji w czasie kompilacji!
Jest prawdopodobnie więcej powodów technicznych, które można sądzić z. To tylko kilka rozważań.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-17 10:04:27
Dla tych, którzy lubią proof by construction, oto godbolt robi ładną optymalizację połączeń ogonowych i inline: https://godbolt.org/z/DMleUN
Jeśli jednak podkręcisz optymalizację do-O3 (lub bez wątpienia poczekasz kilka lat lub użyjesz innego kompilatora), optymalizacja całkowicie usunie pętlę/rekursję.
Oto przykład, który optymalizuje do pojedynczej instrukcji nawet z-O2: https://godbolt.org/z/CNzWex
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-08-20 07:55:09
Często Kompilatory rozpoznają sytuacje, w których funkcja nie będzie musiała nic robić po wywołaniu innej funkcji, i zastępują to wywołanie skokiem. Wiele przypadków, w których można to zrobić bezpiecznie, jest łatwych do rozpoznania, a takie przypadki kwalifikują się jako "Bezpieczne owoce nisko wiszące". Nawet na kompilatorach, które mogą wykonać taką optymalizację, jednak nie zawsze może być oczywiste, kiedy powinna lub będzie wykonana. Różne czynniki mogą sprawić, że koszt połączenia ogonowego będzie większy niż koszt połączenia normalnego, oraz czynniki te nie zawsze mogą być przewidywalne. Na przykład, jeśli funkcja kończy się na return foo(1,2,3,a,b,c,4,5,6);, może być praktyczne skopiowanie a, b I c do rejestrów, wyczyszczenie stosu i przygotowanie argumentów do przekazania, ale może być za mało rejestrów dostępnych do obsługi foo(a,b,c,d,e,f,g,h,i); podobnie.
Jeśli język miał specjalną składnię "tail call", która wymagała, aby Kompilatory, które wykonują tail call, jeśli to w ogóle możliwe, i odmawiają kompilacji w przeciwnym razie, kod mógł bezpiecznie przyjąć takie funkcje być zagnieżdżone dowolnie głęboko. Podczas używania zwykłej składni wywołania nie ma jednak ogólnego sposobu, aby dowiedzieć się, czy kompilator byłby w stanie wykonać wywołanie ogonowe taniej niż "zwykłe".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-08-30 14:50:01