Dlaczego pętle są szybsze niż rekurencja?

W praktyce rozumiem, że każdą rekurencję można zapisać jako pętlę (i vice versa (?)) I jeśli mierzymy z rzeczywistymi komputerami, stwierdzimy, że pętle są szybsze niż rekurencja dla tego samego problemu. Ale czy istnieje jakaś teoria, która czyni tę różnicę, czy jest to głównie uzasadnienie?

Powód, dla którego pętle są szybsze niż rekurencja, jest łatwy.
Pętla wygląda tak w złożeniu.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Pojedynczy skok warunkowy i trochę księgowości dla licznika pętli.

Rekurencja (gdy nie jest lub nie może być zoptymalizowana przez kompilator) wygląda następująco:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

Jest o wiele bardziej skomplikowany i dostajesz co najmniej 3 skoki (1 test, aby sprawdzić, czy zostały wykonane, jedno wezwanie i jeden powrót).
Również w rekursji parametry należy skonfigurować i pobrać.
Żadna z tych rzeczy nie jest potrzebna w pętli, ponieważ wszystkie parametry są już skonfigurowane.

Teoretycznie parametry mogą również pozostać na miejscu z rekurencją, ale żaden kompilator, o którym wiem, nie posunąłby się tak daleko w optymalizacji.

Różnice między połączeniem a jmp
Para zwrot-wywołanie nie jest dużo droższa niż jmp. Para zajmuje 2 cykle, a jmp zajmuje 1; ledwo zauważalne.
W konwencjach wywoływania, które obsługują parametry rejestru, narzut na parametry w minimalnym stopniu, ale nawet parametry stosu są tanie, o ile bufory procesora się nie przepełniają .
Jest to narzut związany z konfiguracją wywołania podyktowany konwencją wywoływania i stosowaną obsługą parametrów, która spowalnia rekurencję.
Jest to bardzo zależne od implementacji.

Przykład słabej obsługi rekurencji Na przykład, jeśli przekazany zostanie parametr, który jest zliczany jako referencja (np. Parametr typu niezarządzanego), doda 100 cykli, wykonując zablokowaną korektę liczby referencyjnych, całkowicie zabijając wydajność w stosunku do pętli.
W językach dostosowanych do rekurencji takie złe zachowanie nie występuje.

Optymalizacja procesora
Innym powodem, dla którego rekurencja jest wolniejsza, jest to, że działa przeciwko mechanizmom optymalizacji procesorów.
Zwroty można przewidzieć poprawnie tylko wtedy, gdy nie ma ich zbyt wiele z rzędu. CPU ma bufor stosu zwrotnego z (kilkoma) garściami wpisów. Gdy te skończą się, każdy dodatkowy zwrot zostanie źle przewidziany, powodując ogromne opóźnienia.
Na każdym procesorze używającym bufora zwrotnego stosu najlepiej unikać rekurencji przekraczającej rozmiar bufora.

Informacje o trywialnych przykładach kodu wykorzystujących rekurencję
Jeśli użyjesz trywialnego przykładu rekurencji, takiego jak generowanie liczb Fibonacciego, te efekty nie występują, ponieważ każdy kompilator, który „wie” o rekurencji, przekształci ją w pętlę, tak jak każdy programista wart swojej soli by.
Jeśli uruchomisz te trywialne przykłady w środowisku, które nie optymalizuje się odpowiednio, stos wywołań (niepotrzebnie) wyrośnie poza granice.

Informacje o rekursji ogona
Zauważ, że czasami kompilator optymalizuje rekursję ogona, zmieniając go w pętlę. Najlepiej jest polegać na tym zachowaniu tylko w językach, które mają dobrze znane osiągnięcia w tym zakresie.
Wiele języków wstawia ukryty kod czyszczenia przed ostatnim zwrotem, co zapobiega optymalizacji rekurencji ogona.

Pomieszanie prawdziwej i pseudo-rekurencji
Jeśli środowisko programistyczne przekształca rekurencyjny kod źródłowy w pętlę, to prawdopodobnie nie jest wykonywana rekurencja.
Prawdziwa rekurencja wymaga zapasu bułki tartej, aby procedura rekurencyjna mogła prześledzić swoje kroki po jej wyjściu.
To prowadzenie tego szlaku powoduje, że rekurencja jest wolniejsza niż korzystanie z pętli. Efekt ten potęgują obecne implementacje procesora, jak opisano powyżej.

Wpływ środowiska programowania
Jeśli Twój język jest nastawiony na optymalizację rekurencji, to i tak zawsze idź dalej i używaj rekurencji przy każdej okazji. W większości przypadków język zmieni twoją rekurencję w pewnego rodzaju pętlę.
W przypadkach, w których nie jest to możliwe, programista również byłby mocno wciśnięty. Jeśli Twój język programowania nie jest dostosowany do rekurencji, należy go unikać, chyba że domena jest przystosowana do rekurencji.
Niestety wiele języków nie radzi sobie dobrze z rekurencją.

Niewłaściwe użycie rekurencji
Nie ma potrzeby obliczania sekwencji Fibonacciego za pomocą rekurencji, w rzeczywistości jest to patologiczny przykład.
Rekurencję najlepiej stosować w językach, które ją wyraźnie obsługują lub w domenach, w których świeci rekurencja, takich jak przetwarzanie danych przechowywanych w drzewie.

Rozumiem, że każdą rekurencję można zapisać jako pętlę

Tak, jeśli chcesz postawić wózek przed koniem.
Wszystkie wystąpienia rekurencji można zapisać w pętli, niektóre z nich wymagają użycia jawnego stosu, takiego jak pamięć.
Jeśli potrzebujesz rzucić własny stos tylko po to, aby przekształcić kod rekurencyjny w pętlę, równie dobrze możesz użyć zwykłej rekurencji.
O ile oczywiście nie masz specjalnych potrzeb, takich jak używanie enumeratorów w strukturze drzewa i nie masz odpowiedniego wsparcia językowego.

Te inne odpowiedzi są nieco mylące. Zgadzam się, że podają szczegółowe informacje na temat implementacji, które mogą wyjaśnić tę rozbieżność, ale przeceniają sprawę. Jak poprawnie zasugerował jmite, są one zorientowane na implementację w kierunku zepsutych implementacji wywołań / rekurencji funkcji. Wiele języków implementuje pętle za pomocą rekurencji, więc ewidentnie pętle nie będą szybsze w tych językach. Rekurencja nie jest w żaden sposób mniej wydajna niż zapętlenie (gdy oba mają zastosowanie) w teorii. Pozwólcie mi zacytować streszczenie artykułu Guya Steele'a z 1977 r. Obalenie mitu „Drogiego wezwania do postępowania” lub implementacji procedur uważanych za szkodliwe lub Lambda: ostateczne GOTO

Folklor stwierdza, że ​​oświadczenia GOTO są „tanie”, podczas gdy wywołania procedur są „drogie”. Ten mit jest w dużej mierze wynikiem źle zaprojektowanych implementacji językowych. Rozważany jest historyczny rozwój tego mitu. Omawiane są zarówno pomysły teoretyczne, jak i istniejące wdrożenie, które obalają ten mit. Pokazano, że nieograniczone stosowanie wywołań procedur zapewnia dużą swobodę stylistyczną. W szczególności każdy schemat blokowy można zapisać jako program „strukturalny” bez wprowadzania dodatkowych zmiennych. Trudność związana z instrukcją GOTO i wywołaniem procedury charakteryzuje się konfliktem między abstrakcyjnymi koncepcjami programowania a konkretnymi konstrukcjami językowymi.

„Konflikt między abstrakcyjnymi pojęciami programowania a konkretnymi konstrukcjami językowymi” wynika z faktu, że większość modeli teoretycznych, na przykład nietypowego rachunku lambda , nie ma stosu . Oczywiście ten konflikt nie jest konieczny, jak ilustruje powyższy artykuł i co pokazują również języki, które nie mają mechanizmu iteracji innego niż rekurencja, takiego jak Haskell.

fixfix f x = f (fix f) x$(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$

Teraz na przykład. Zdefiniuj factjako

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Oto ocena tego fact 3, gdzie dla zwięzłości użyję gjako synonimu fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), tj fact = g 1. To nie wpływa na mój argument.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Z kształtu widać, nawet nie patrząc na szczegóły, że nie ma wzrostu i każda iteracja potrzebuje takiej samej ilości miejsca. (Technicznie, wynik liczbowy rośnie, co jest nieuniknione i tak samo prawdziwe dla whilepętli.) Przeciwstawiam się, aby wskazać tutaj na nieograniczająco rosnący „stos”.

Wydaje się, że archetypiczna semantyka rachunku lambda już robi to, co jest powszechnie nazywane „optymalizacją wywołania ogona”. Oczywiście nie ma tu miejsca „optymalizacja”. Nie ma tutaj specjalnych zasad dla połączeń „ogonowych” w przeciwieństwie do „normalnych” połączeń. Z tego powodu trudno jest podać „abstrakcyjną” charakterystykę tego, co robi „optymalizacja” wywołania ogona, ponieważ w wielu abstrakcyjnych charakterystykach semantyki wywołania funkcji nie ma nic do zrobienia w „optymalizacji” wywołania ogona!

To, że analogiczna definicja fact„przepełnienia stosu” w wielu językach jest brakiem prawidłowego wdrożenia semantyki wywołań funkcji przez te języki. (Niektóre języki mają wymówkę). Sytuacja jest w przybliżeniu analogiczna do implementacji języka, która implementowała tablice z listami połączonymi. Indeksowanie do takich „tablic” byłoby wówczas operacją O (n), która nie spełnia oczekiwań tablic. Gdybym wykonał osobną implementację języka, który używał prawdziwych tablic zamiast połączonych list, nie powiedziałbym, że zaimplementowałem „optymalizację dostępu do tablicy”, powiedziałbym, że naprawiłem zepsutą implementację tablic.

Odpowiadając na odpowiedź Veedrac. Stosy nie są „fundamentalne” dla rekurencji . W zakresie, w jakim zachowanie „przypominające stos” występuje podczas oceny, może się to zdarzyć tylko w przypadkach, w których pętle (bez struktury danych pomocniczych) nie miałyby zastosowania w pierwszej kolejności! Innymi słowy, mogę zaimplementować pętle z rekurencją o dokładnie takiej samej charakterystyce wydajności. Rzeczywiście, Scheme i SML zawierają konstrukcje zapętlone, ale oba definiują je w kategoriach rekurencji (i przynajmniej w Schemacie doczęsto są implementowane jako makro, które rozwija się w wywołania rekurencyjne). Podobnie, w odpowiedzi Johana nic nie mówi kompilator musi wyemitować zestaw opisany przez Johna do rekurencji. W rzeczy samej,dokładnie ten sam zestaw, niezależnie od tego, czy używasz pętli, czy rekurencji. Kompilator byłby (w pewnym stopniu) zobowiązany do emitowania asemblera, tak jak to opisuje Johan, gdy robisz coś, czego nie da się wyrazić za pomocą pętli. Jak opisano w pracy Steele i wykazano w praktyce języków takich jak Haskell, Scheme i SML, nie jest „wyjątkowo rzadkie”, że wezwania do ogona można „zoptymalizować”, zawsze mogąbyć „zoptymalizowanym”. To, czy określone użycie rekurencji będzie działało w stałej przestrzeni, zależy od tego, jak jest napisane, ale ograniczenia, które musisz zastosować, aby to umożliwić, to ograniczenia, których potrzebujesz, aby dopasować swój problem do kształtu pętli. (W rzeczywistości są one mniej rygorystyczne. Występują problemy, takie jak kodowanie automatów stanów, które są czystsze i wydajniej obsługiwane za pomocą wywołań typu tail, w przeciwieństwie do pętli, które wymagałyby zmiennych pomocniczych.) Ponownie, jedyna rekurencja wymaga więcej pracy kiedy twój kod i tak nie jest pętlą.

Domyślam się, że Johan odnosi się do kompilatorów C, które mają arbitralne ograniczenia, kiedy wykona „optymalizację” wywołania końcowego. Johan prawdopodobnie odnosi się również do języków takich jak C ++ i Rust, kiedy mówi o „językach z typami zarządzanymi”. RAII idiom z C ++ i obecny w Rust, a także sprawia, że rzeczy, które pozornie wyglądają jak rekurencja ogonowa, nie rekurencja ogonowa (bo „destruktorów” nadal trzeba nazwać). Pojawiły się propozycje zastosowania innej składni, aby włączyć nieco inną semantykę, która umożliwiałaby rekurencję ogona (a mianowicie niszczyciele wywołań przedostatnie wywołanie ogona i oczywiście nie zezwalają na dostęp do „zniszczonych” obiektów). (Odśmiecanie nie ma takiego problemu, a wszystkie Haskell, SML i Scheme to języki odśmiecane.) W zupełnie innym stylu niektóre języki, takie jak Smalltalk, ujawniają „stos” jako obiekt pierwszej klasy, w tych przypadki „stos” nie jest już szczegółem implementacji, chociaż nie wyklucza to posiadania osobnych typów wywołań o różnej semantyce. (Java twierdzi, że tak nie jest ze względu na sposób, w jaki obsługuje niektóre aspekty bezpieczeństwa, ale tak naprawdę jest to nieprawda ).

W praktyce częstość niedziałających implementacji wywołań funkcji wynika z trzech głównych czynników. Po pierwsze, wiele języków dziedziczy zepsutą implementację po języku implementacji (zwykle C). Po drugie, deterministyczne zarządzanie zasobami jest przyjemne i sprawia, że ​​problem jest bardziej skomplikowany, chociaż oferuje to tylko garstka języków. Po trzecie, i z mojego doświadczenia wynika, że ​​większość ludzi obchodzi to, że chcą ślady stosu, gdy wystąpią błędy do celów debugowania. Tylko drugi powód może być potencjalnie motywowany teoretycznie.

Zasadniczo różnica polega na tym, że rekurencja obejmuje stos, strukturę danych pomocniczych, której prawdopodobnie nie chcesz, podczas gdy pętle nie robią tego automatycznie. Tylko w rzadkich przypadkach typowy kompilator może wywnioskować, że tak naprawdę wcale nie potrzebujesz stosu.

Jeśli porównasz zamiast tego pętle działające ręcznie na przydzielonym stosie (np. Przez wskaźnik do pamięci stosu), zwykle nie znajdziesz ich szybciej ani nawet wolniej niż przy stosie sprzętowym.