Dlaczego programy używają stosów wywołań, jeśli można wstawiać zagnieżdżone wywołania funkcji?

33

Dlaczego nie chcesz, aby kompilator pobierał program taki jak ten:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

i przekonwertować na program taki jak ten:

function c(b) { return b^2 + 5 };

eliminując w ten sposób potrzebę zapamiętania przez komputer adresu zwrotnego c (b)?

Podejrzewam, że zwiększone miejsce na dysku twardym i pamięć RAM potrzebne do przechowywania programu i obsługi jego kompilacji (odpowiednio) są powodem, dla którego używamy stosów wywołań. Czy to jest poprawne?

moonman239
źródło
30
Zobacz, co się stanie, jeśli zrobisz to w programie o dowolnym znaczącym rozmiarze. W szczególności funkcje są wywoływane z więcej niż jednego miejsca.
user253751
10
Ponadto czasami kompilator nie wie, która funkcja jest wywoływana! Głupi przykład:window[prompt("Enter function name","")]()
user253751
26
Jak wdrożyć function(a)b { if(b>0) return a(b-1); }bez stosu?
pjc50
8
Gdzie jest związek z programowaniem funkcjonalnym?
mastov
14
@ pjc50: jest rekurencyjny, więc kompilator przekształca go w pętlę ze zmienną b. Ale biorąc pod uwagę, nie wszystkie funkcje rekurencyjne mogą wyeliminować rekurencję, a nawet jeśli funkcja w zasadzie może, kompilator może nie być wystarczająco inteligentny, aby to zrobić.
Steve Jessop,

Odpowiedzi:

75

Nazywa się to „wstawianiem” i wiele kompilatorów robi to jako strategia optymalizacji w przypadkach, w których ma to sens.

W twoim przykładzie ta optymalizacja pozwoliłaby zaoszczędzić zarówno miejsce, jak i czas wykonania. Ale jeśli funkcja została wywołana w wielu miejscach w programie (nierzadko!), Zwiększyłaby rozmiar kodu, więc strategia staje się bardziej wątpliwa. (I oczywiście, jeśli funkcja wywołała się bezpośrednio lub pośrednio, wstawienie byłoby niemożliwe, ponieważ kod stałby się nieskończony).

I oczywiście jest to możliwe tylko dla funkcji „prywatnych”. Funkcje udostępniane zewnętrznym dzwoniącym nie mogą być optymalizowane, przynajmniej w językach z dynamicznym łączeniem.

JacquesB
źródło
7
@Blrfl: Nowoczesne kompilatory nie potrzebują już definicji w nagłówku; mogą łączyć się między jednostkami tłumaczeniowymi. Wymaga to jednak przyzwoitego linkera. Definicje w plikach nagłówkowych są obejściem dla niemych linkerów.
MSalters
3
„Funkcji, które są udostępniane zewnętrznym dzwoniącym, nie można zoptymalizować” - funkcja musi istnieć, ale można podać dowolną daną witrynę wywołującą (w swoim własnym kodzie lub, jeśli mają źródło, zewnętrznych dzwoniących).
Random832
14
Wow, 28 głosów za odpowiedzią, która nawet nie wspomina o przyczynie, dla której wszystko jest niemożliwe: Rekurencja.
mastov
3
@R ..: LTO to optymalizacja czasu LINK, a nie optymalizacja czasu ładowania.
MSalters
2
@immibis: Ale jeśli kompilator wprowadzi ten jawny stos, wówczas stos ten będzie stosem wywołań.
użytkownik2357112 obsługuje Monikę
51

Pytanie to składa się z dwóch części: Dlaczego w ogóle istnieje wiele funkcji (zamiast zastępować wywołania funkcji ich definicją) i dlaczego implementować te funkcje za pomocą stosów wywołań zamiast statycznego przydzielania danych gdzie indziej?

Pierwszym powodem jest rekurencja. Nie tylko rodzaj „och, zróbmy nowe wywołanie funkcji dla każdego pojedynczego elementu na tej liście”, ale także skromny rodzaj, w którym możesz mieć dwa wywołania funkcji jednocześnie, z wieloma innymi funkcjami pomiędzy nimi. Aby to obsługiwać, musisz umieścić zmienne lokalne na stosie i ogólnie nie można wstawiać funkcji rekurencyjnych.

Jest też problem z bibliotekami: nie wiesz, które funkcje będą wywoływane z miejsca i jak często, więc „biblioteka” nigdy tak naprawdę nie mogłaby zostać skompilowana, tylko wysłana do wszystkich klientów w dogodnym formacie wysokiego poziomu, który następnie byłby wbudowany w aplikację. Oprócz innych problemów z tym, całkowicie tracisz dynamiczne łączenie ze wszystkimi jego zaletami.

Ponadto istnieje wiele powodów, aby nie wstawiać funkcji, nawet jeśli można:

  1. To niekoniecznie jest szybsze. Konfigurowanie ramki stosu i burzenie jej może być tuzinem instrukcji pojedynczego cyklu, dla wielu dużych lub zapętlonych funkcji, które nie stanowią nawet 0,1% czasu ich wykonywania.
  2. To może być wolniejsze. Powielanie kodu wiąże się z kosztami, np. Zwiększy presję w pamięci podręcznej instrukcji.
  3. Niektóre funkcje są bardzo duże i wywoływane z wielu miejsc, dlatego wprowadzenie ich wszędzie zwiększa wartość binarną daleko poza rozsądne możliwości.
  4. Kompilatory często mają trudności z bardzo dużymi funkcjami. Wszystko inne jest równe, funkcja rozmiaru 2 * N zajmuje więcej niż 2 * czas T, podczas gdy funkcja rozmiaru N zajmuje czas T.

źródło
1
Jestem zaskoczony punktem 4. Jaki jest tego powód?
JacquesB
12
@JacquesB Wiele algorytmów optymalizacji jest kwadratowych, sześciennych, a nawet technicznie NP-kompletnych. Kanonicznym przykładem jest alokacja rejestru, która jest NP-kompletna przez analogię z kolorem grafu. (Zwykle kompilatory nie próbują dokładnego rozwiązania, ale tylko kilka bardzo słabych heurystyk przebiega w czasie liniowym). Wiele prostych, jednoprzebiegowych optymalizacji wymaga najpierw przejść analizy superliniowej, takich jak wszystko, co zależy od dominacji w przepływach sterowania (ogólnie n log n czas z n podstawowymi blokami).
2
„Naprawdę masz tutaj dwa pytania” Nie, nie mam. Tylko jeden - dlaczego nie traktować wywołania funkcji jako symbolu zastępczego, który kompilator mógłby, na przykład, zastąpić kodem wywoływanej funkcji?
moonman239
4
@ moonman239 Wtedy twoje słowa mnie wyrzuciły. Mimo to twoje pytanie może zostać rozłożone, tak jak ja w mojej odpowiedzi, i myślę, że to przydatna perspektywa.
16

Stosy pozwalają nam elegancko ominąć ograniczenia narzucone przez skończoną liczbę rejestrów.

Wyobraź sobie, że masz dokładnie 26 globalnych „rejestrów az” (lub nawet posiadasz tylko 7-bajtowych rejestrów układu 8080). I każda funkcja, którą piszesz w tej aplikacji, dzieli tę płaską listę.

Naiwnym początkiem byłoby przydzielenie kilku pierwszych rejestrów do pierwszej funkcji i wiedząc, że zajęło to tylko 3, zacznij od „d” dla drugiej funkcji… Szybko skończysz.

Zamiast tego, jeśli masz metaforyczny taśmę, jak maszyna Turinga, można mieć każda funkcja rozpocząć „wywołać inną funkcję” zapisując wszystkie zmienne to korzystania i forward () taśmę, a następnie funkcja wywoływany może radzić z tak wielu rejestruje się, jak chce. Po zakończeniu procesu odbiorca zwraca kontrolę funkcji nadrzędnej, która wie, gdzie w razie potrzeby zaczepić wyjście odbiorcy, a następnie odtwarza taśmę do tyłu, aby przywrócić jej stan.

Podstawowa ramka wywołania jest właśnie taka i jest tworzona i upuszczana przez znormalizowane sekwencje kodów maszynowych, które kompilator umieszcza wokół przejść z jednej funkcji do drugiej. (Minęło dużo czasu, odkąd musiałem pamiętać moje ramki stosu C, ale możesz przeczytać o różnych sposobach, które spadają z tego, co na X86_calling_conventions .)

(rekurencja jest niesamowita, ale jeśli kiedykolwiek musiałbyś żonglować rejestrami bez stosu, naprawdę doceniłbyś stosy).


Podejrzewam, że zwiększone miejsce na dysku twardym i pamięć RAM potrzebne do przechowywania programu i obsługi jego kompilacji (odpowiednio) są powodem, dla którego używamy stosów wywołań. Czy to jest poprawne?

Chociaż możemy teraz wstawiać więcej, („większa szybkość” jest zawsze dobra; „mniej kb zestawu” oznacza bardzo mało w świecie strumieni wideo) Głównym ograniczeniem jest zdolność kompilatora do spłaszczania określonych typów wzorców kodu.

Na przykład obiekty polimorficzne - jeśli nie znasz jedynego rodzaju obiektu, który zostanie ci przekazany, nie możesz spłaszczyć; musisz spojrzeć na tabelę funkcji obiektu i wywołać ten wskaźnik ... trywialne do wykonania w czasie wykonywania, niemożliwe do wstawienia w czasie kompilacji.

Nowoczesny łańcuch narzędzi może z radością wprowadzać funkcję zdefiniowaną polimorficznie, gdy spłaszczy już tyle osób wywołujących, aby dokładnie wiedzieć , jaki jest smak obiektu obj:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

powyżej kompilator może wybrać statyczne wstawianie, od InlineMe poprzez cokolwiek, co jest w środku act (), ani nie trzeba dotykać żadnych tabel w czasie wykonywania.

Ale jakakolwiek niepewność w jaki smak obiektu pozostawi je jako wezwanie do dyskretnej funkcji, nawet jeśli niektóre inne wywołania tej samej funkcji wstawiane.

Xander
źródło
11

Przypadki, których to podejście nie obsługuje:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Tam języki i platformy z ograniczoną lub brak połączeń stosów. Mikroprocesory PIC mają stos sprzętu ograniczony do 2 do 32 pozycji . Stwarza to ograniczenia projektowe.

Rekurencja zakazów COBOL: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

Nałożenie zakazu rekurencji oznacza, że ​​możesz reprezentować cały callgraph programu statycznie jako DAG. Twój kompilator może następnie wyemitować jedną kopię funkcji dla każdego miejsca, z którego jest wywoływany, ze stałym skokiem zamiast powrotu. Nie wymaga stosu, po prostu więcej miejsca na program, potencjalnie całkiem dużo dla złożonych systemów. Ale w przypadku małych systemów wbudowanych oznacza to, że możesz zagwarantować, że nie wystąpi przepełnienie stosu w czasie wykonywania, co byłoby złą wiadomością dla reaktora jądrowego / turbiny odrzutowej / sterowania przepustnicą samochodu itp.

pjc50
źródło
12
Twój pierwszy przykład to podstawowa rekurencja i masz rację. Ale twoim drugim przykładem wydaje się być pętla for wywołująca inną funkcję. Funkcja wstawiania różni się od rozwijania pętli; funkcja może być wbudowana bez rozwijania pętli. A może przeoczyłem jakiś subtelny szczegół?
jpmc26
1
Jeśli twój pierwszy przykład ma na celu zdefiniowanie szeregu Fibonacciego, jest błędny. (Brakuje fibpołączenia.)
Paŭlo Ebermann
1
Chociaż zakaz rekurencji oznacza, że ​​cały wykres połączeń może być reprezentowany jako DAG, nie oznacza to, że można wyszczególnić pełną listę zagnieżdżonych sekwencji połączeń w rozsądnej ilości miejsca. W jednym z moich projektów dla mikrokontrolera z 128KB przestrzeni kodu popełniłem błąd, prosząc o wykres wywołań, który obejmowałby wszystkie funkcje, które mogłyby wpłynąć na maksymalne wymagania pamięci RAM parametru i ten wykres wywołania był gigantyczny. Pełny wykres wywołań byłby jeszcze dłuższy, i dotyczyłby programu mieszczącego się w 128 KB przestrzeni kodu.
supercat
8

Chcesz wstawiania funkcji , a większość kompilatorów ( optymalizujących ) to robi.

Zauważ, że wstawianie wymaga znajomości wywoływanej funkcji (i jest skuteczne tylko wtedy, gdy wywoływana funkcja nie jest zbyt duża), ponieważ koncepcyjnie zastępuje wywołanie przez przepisanie wywoływanej funkcji. Tak więc generalnie nie można wstawić nieznanej funkcji (np. Wskaźnika funkcji - i który zawiera funkcje z dynamicznie połączonych bibliotek współdzielonych - co jest być może widoczne jako metoda wirtualna w niektórych vtable ; ale niektóre kompilatory mogą czasami zoptymalizować techniki dewirtualizacji ). Oczywiście nie zawsze jest możliwe wstawienie funkcji rekurencyjnych (niektóre sprytne kompilatory mogą korzystać z częściowej oceny, a w niektórych przypadkach mogą wstawiać funkcje rekurencyjne).

Zauważ też, że inlinizacja, nawet jeśli jest to łatwo możliwe, nie zawsze jest skuteczna: ty (właściwie twój kompilator) możesz zwiększyć tak duży rozmiar kodu, że pamięci podręczne procesora (lub predyktor gałęzi ) działałyby mniej wydajnie, a to sprawiłoby, że Twój program działał wolniej.

Trochę koncentruję się na funkcjonalnym stylu programowania , ponieważ oznaczyłeś swoje pytanie jako takie.

Zauważ, że nie musisz mieć stosu wywołań (przynajmniej w sensie maszynowym wyrażenia „stos wywołań”). Możesz użyć tylko stosu.

Tak, warto spojrzeć na kontynuacje i przeczytaj więcej o kontynuacji przechodzącą stylu (CPS) i CPS transformacji (intuicyjnie, można użyć kontynuacji zamknięć jak reified „klatek nazywają” alokowanych na stercie, a są one sort-naśladując stos wywołań; potrzebujesz wydajnego śmietnika ).

Andrew Appel napisał książkę Compiling with Continuations, a stary zbiór śmieci papierowych może być szybszy niż przydzielanie stosów . Zobacz także artykuł A. Kennedy'ego (ICFP2007) Kompilacja z kontynuacjami, ciąg dalszy

Polecam także przeczytanie książki Lisp In Small Pieces Queinnec, która zawiera kilka rozdziałów związanych z kontynuacją i kompilacją.

Zauważ też, że niektóre języki (np. Brainfuck ) lub abstrakcyjne maszyny (np. OISC , RAM ) nie mają żadnych funkcji wywoływania, ale wciąż są kompletne Turinga , więc (teoretycznie) nawet nie potrzebujesz żadnego mechanizmu wywoływania funkcji, nawet jeśli jest to niezwykle wygodne. BTW, niektóre stare architektury zestawu instrukcji (np. IBM / 370 ) nie mają nawet stosu wywołań sprzętowych lub instrukcji maszyny wywołującej push (IBM / 370 miał tylko instrukcję maszyny rozgałęzienia i łącza )

W końcu, jeśli cały twój program (w tym wszystkie potrzebne biblioteki) nie ma żadnej rekurencji, możesz zapisać adres zwrotny (i zmienne „lokalne”, które faktycznie stają się statyczne) każdej funkcji w lokalizacjach statycznych. Stare kompilatory Fortran77 zrobiły to na początku lat 80. XX wieku (więc skompilowane programy nie używały wtedy żadnego stosu wywołań).

Basile Starynkevitch
źródło
2
Bardzo dyskusyjne jest to, że CPS nie ma „stosu połączeń”. Nie ma go na stosie , mistycznym regionie zwykłej pamięci RAM, który ma trochę wsparcia sprzętowego %espitp., Ale nadal utrzymuje równoważną księgowość na trafnie nazwanym stosie spaghetti w innym regionie pamięci RAM. W szczególności adres zwrotny jest zasadniczo zakodowany w kontynuacji. I oczywiście kontynuacje nie są szybsze (i wydaje mi się, że o to właśnie chodziło OP) niż nie wykonywanie żadnych połączeń przez inlining.
W starych dokumentach Appela stwierdzono (i wykazano za pomocą testów porównawczych), że CPS może być tak szybki, jak posiadanie stosu wywołań.
Basile Starynkevitch,
Jestem z tego sceptyczny, ale niezależnie od tego twierdziłem.
1
Tak naprawdę było to na stacji roboczej MIPS z końca lat osiemdziesiątych. Prawdopodobnie hierarchia pamięci podręcznej na obecnych komputerach nieznacznie zmieniłaby wydajność. Było kilka artykułów analizujących twierdzenia Appela (i na obecnych maszynach przydzielanie stosu może być nieco szybsze - o kilka procent - niż starannie wykonane śmieci)
Basile Starynkevitch
1
@Gilles: Wiele nowszych rdzeni ARM, takich jak Cortex M0 i M3 (i prawdopodobnie inne, takie jak M4), obsługuje obsługę stosu sprzętowego do obsługi przerwań. Ponadto, zestaw instrukcji Thumb zawiera ograniczony podzbiór instrukcji STRM / STRM, który obejmuje STRMDB R13 z dowolną kombinacją R0-R7 z / bez LR i LDRMIA R13 dowolnej kombinacji R0-R7 z / bez PC, co skutecznie leczy R13 jako wskaźnik stosu.
supercat
8

Inlining (zastępujący wywołania funkcji równoważną funkcjonalnością) działa dobrze jako strategia optymalizacji dla małych prostych funkcji. Narzut wywołania funkcji może być skutecznie zamieniony na niewielką karę w zwiększonym rozmiarze programu (lub w niektórych przypadkach w ogóle bez kary).

Jednak duże funkcje, które z kolei wywołują inne funkcje, mogą doprowadzić do ogromnej eksplozji rozmiaru programu, jeśli wszystko zostanie wstawione.

Głównym celem wywoływanych funkcji jest ułatwienie efektywnego ponownego użycia, nie tylko przez programistę, ale także przez samą maszynę, i obejmuje takie właściwości, jak rozsądna pamięć lub ślad na dysku.

Za to, co jest warte: możesz mieć funkcje wywoływalne bez stosu wywołań. Na przykład: IBM System / 360. Podczas programowania w takich językach, jak FORTRAN na tym sprzęcie, licznik programu (adres zwrotny) zostanie zapisany w małej części pamięci zarezerwowanej tuż przed punktem wejścia funkcji. Pozwala na funkcje wielokrotnego użytku, ale nie pozwala na kod rekurencyjny lub wielowątkowy (próba wywołania rekurencyjnego lub ponownego połączenia spowoduje nadpisanie wcześniej zapisanego adresu zwrotnego).

Jak wyjaśniono w innych odpowiedziach, stosy to dobre rzeczy. Ułatwiają rekurencję i połączenia wielowątkowe. Chociaż każdy algorytm zakodowany w celu użycia rekurencji może być kodowany bez polegania na rekurencji, wynik może być bardziej złożony, trudniejszy do utrzymania i może być mniej wydajny. Nie jestem pewien, czy architektura bez stosu mogłaby w ogóle obsługiwać wielowątkowość.

Zenilogix
źródło