Jaki jest cel stosu? Dlaczego tego potrzebujemy?

Uczę się teraz MSIL, aby nauczyć się debugować moje aplikacje C # .NET.

Zawsze zastanawiałem się: jaki jest cel stosu?

Wystarczy umieścić moje pytanie w kontekście:
dlaczego istnieje transfer z pamięci na stos lub „ładowanie”? Z drugiej strony, dlaczego istnieje przeniesienie ze stosu do pamięci lub „przechowywanie”? Dlaczego po prostu nie umieścisz ich wszystkich w pamięci?

• Czy to dlatego, że jest szybszy?
• Czy to dlatego, że jest oparty na pamięci RAM?
• Dla wydajności?

Próbuję to zrozumieć, aby pomóc mi głębiej zrozumieć kody CIL .

AKTUALIZACJA: Tak bardzo spodobało mi się to pytanie, że stałem się tematem mojego bloga 18 listopada 2011 r . Dzięki za świetne pytanie!

Zawsze zastanawiałem się: jaki jest cel stosu?

Zakładam, że masz na myśli stos ewaluacyjny języka MSIL, a nie rzeczywisty stos na wątek w czasie wykonywania.

Dlaczego istnieje przeniesienie z pamięci na stos lub „ładowanie”? Z drugiej strony, dlaczego istnieje przeniesienie ze stosu do pamięci lub „przechowywanie”? Dlaczego po prostu nie umieścisz ich wszystkich w pamięci?

MSIL to język „maszyny wirtualnej”. Kompilatory takie jak kompilator C # generują CIL , a następnie inny kompilator zwany kompilatorem JIT (Just In Time) zamienia IL w rzeczywisty kod maszynowy, który można wykonać.

Więc najpierw odpowiedzmy na pytanie „dlaczego MSIL w ogóle?” Dlaczego po prostu kompilator C # nie wypisuje kodu maszynowego?

Ponieważ taniej jest to zrobić w ten sposób. Załóżmy, że nie zrobiliśmy tego w ten sposób; załóżmy, że każdy język musi mieć własny generator kodów maszynowych. Masz dwadzieścia różnych języków: C #, JScript .NET , Visual Basic, IronPython , F # ... Załóżmy, że masz dziesięć różnych procesorów. Ile generatorów kodu musisz napisać? 20 x 10 = 200 generatorów kodu. To dużo pracy. Załóżmy teraz, że chcesz dodać nowy procesor. Musisz napisać dla niego generator kodu dwadzieścia razy, po jednym dla każdego języka.

Co więcej, jest to trudna i niebezpieczna praca. Pisanie wydajnych generatorów kodu dla układów, na których nie jesteś ekspertem, to ciężka praca! Projektanci kompilatorów są ekspertami w analizie semantycznej ich języka, a nie w efektywnym przydzielaniu rejestrów nowych zestawów układów.

Załóżmy teraz, że robimy to w CIL. Ile generatorów CIL musisz napisać? Jeden na język. Ile kompilatorów JIT musisz napisać? Jeden na procesor. Łącznie: 20 + 10 = 30 generatorów kodów. Ponadto generator języka do kodu CIL jest łatwy do napisania, ponieważ CIL jest prostym językiem, a generator kodu do kodu maszynowego jest również łatwy do napisania, ponieważ CIL jest prostym językiem. Pozbywamy się wszystkich zawiłości C # i VB oraz wszystkiego i „obniżamy” wszystko do prostego języka, dla którego łatwo jest napisać jitter.

Posiadanie języka pośredniego znacznie obniża koszty produkcji nowego kompilatora językowego . Znacząco obniża to także koszt obsługi nowego układu. Chcesz wesprzeć nowy układ, znajdziesz ekspertów na tym układzie i każesz im napisać fluktuację CIL i gotowe! następnie obsługujesz wszystkie te języki na swoim chipie.

OK, więc ustaliliśmy, dlaczego mamy MSIL; ponieważ znajomość języka obcego obniża koszty. Dlaczego zatem język jest „maszyną stosową”?

Ponieważ maszyny stosowe są koncepcyjnie bardzo łatwe w obsłudze dla twórców kompilatorów językowych. Stosy to prosty, łatwy do zrozumienia mechanizm opisywania obliczeń. Maszyny stosowe są również koncepcyjnie bardzo łatwe w obsłudze dla twórców kompilatorów JIT. Korzystanie ze stosu jest abstrakcją upraszczającą i dlatego obniża nasze koszty .

Pytasz „po co w ogóle stos?” Dlaczego nie zrobić wszystkiego bezpośrednio z pamięci? Pomyślmy o tym. Załóżmy, że chcesz wygenerować kod CIL dla:

int x = A() + B() + C() + 10;

Załóżmy, że mamy konwencję, zgodnie z którą „dodaj”, „wywołaj”, „zapisz” i tak dalej, zawsze usuwają argumenty ze stosu i umieszczają wynik (jeśli taki istnieje) na stosie. Aby wygenerować kod CIL dla tego C # mówimy po prostu coś takiego:

load the address of x // The stack now contains address of x
call A()              // The stack contains address of x and result of A()
call B()              // Address of x, result of A(), result of B()
add                   // Address of x, result of A() + B()
call C()              // Address of x, result of A() + B(), result of C()
add                   // Address of x, result of A() + B() + C()
load 10               // Address of x, result of A() + B() + C(), 10
add                   // Address of x, result of A() + B() + C() + 10
store in address      // The result is now stored in x, and the stack is empty.

Załóżmy teraz, że zrobiliśmy to bez stosu. Zrobimy to po swojemu, gdzie każdy kod operacji bierze adresy swoich operandów i adres, pod którym przechowuje swój wynik :

Allocate temporary store T1 for result of A()
Call A() with the address of T1
Allocate temporary store T2 for result of B()
Call B() with the address of T2
Allocate temporary store T3 for the result of the first addition
Add contents of T1 to T2, then store the result into the address of T3
Allocate temporary store T4 for the result of C()
Call C() with the address of T4
Allocate temporary store T5 for result of the second addition
...

Widzisz jak to idzie? Nasz kod staje się ogromny, ponieważ musimy jawnie przydzielić całą pamięć tymczasową , która normalnie zgodnie z konwencją po prostu idzie na stos . Co gorsza, same nasze kody stają się ogromne, ponieważ wszyscy muszą teraz wziąć za argument adres, pod którym zamierzają zapisać swój wynik, oraz adres każdego argumentu. Instrukcja „dodaj”, która wie, że zamierza usunąć dwie rzeczy ze stosu i nałożyć jedną rzecz, może być pojedynczym bajtem. Instrukcja add, która przyjmuje dwa adresy operandów i adres wynikowy, będzie ogromna.

Używamy kodów opartych na stosach, ponieważ stosy rozwiązują typowy problem . Mianowicie: chcę przeznaczyć trochę pamięci tymczasowej, zużyć ją bardzo szybko, a potem szybko ją pozbyć, kiedy skończę . Zakładając, że mamy do dyspozycji stos, możemy sprawić, że kody będą bardzo małe, a kod bardzo zwięzły.

AKTUALIZACJA: Kilka dodatkowych przemyśleń

Nawiasem mówiąc, pomysł drastycznego obniżenia kosztów poprzez (1) określenie maszyny wirtualnej, (2) pisanie kompilatorów ukierunkowanych na język VM i (3) pisanie implementacji VM na różnych urządzeniach, wcale nie jest nowym pomysłem . Nie pochodzi od MSIL, LLVM, kodu bajtowego Java ani żadnej innej nowoczesnej infrastruktury. Najwcześniejsza realizacja tej strategii, o której wiem, to maszyna pcode z 1966 roku.

Pierwszy raz osobiście usłyszałem o tej koncepcji, kiedy dowiedziałem się, jak implementatorzy Infocom zdołali sprawić, że Zork działał na tak wielu różnych maszynach. Określili maszynę wirtualną o nazwie Z-machine, a następnie stworzyli emulatory maszyny Z dla całego sprzętu, na którym chcieli uruchomić swoje gry. Miało to dodatkową zaletę, że mogły implementować zarządzanie pamięcią wirtualną w prymitywnych systemach 8-bitowych; gra może być większa niż zmieściłaby się w pamięci, ponieważ mogłaby po prostu umieścić kod z dysku, gdy go potrzebował, i odrzucić, gdy potrzebował załadować nowy kod.

Pamiętaj, że mówiąc o MSIL, mówisz o instrukcjach dla maszyny wirtualnej . Maszyna wirtualna używana w .NET jest maszyną wirtualną opartą na stosie. W przeciwieństwie do maszyny wirtualnej opartej na rejestrze, Dalvik VM używana w systemach operacyjnych Android jest tego przykładem.

Stos na maszynie wirtualnej jest wirtualny, od tłumacza lub kompilatora just-in-time można przetłumaczyć instrukcje maszyny wirtualnej na rzeczywisty kod działający na procesorze. Który w przypadku .NET prawie zawsze jest fluktuacją, zestaw instrukcji MSIL został zaprojektowany tak, aby był uruchamiany od samego początku. Na przykład, w przeciwieństwie do kodu bajtowego Java, ma odrębne instrukcje dotyczące operacji na określonych typach danych. Co sprawia, że ​​jest zoptymalizowany do interpretacji. Interpreter MSIL faktycznie istnieje, jest używany w .NET Micro Framework. Który działa na procesorach o bardzo ograniczonych zasobach, nie stać go na pamięć RAM wymaganą do przechowywania kodu maszynowego.

Rzeczywisty model kodu maszynowego jest mieszany, zawiera zarówno stos, jak i rejestry. Jednym z dużych zadań optymalizatora kodu JIT jest wymyślenie sposobów przechowywania zmiennych przechowywanych na stosie w rejestrach, co znacznie poprawia szybkość wykonywania. Drganie w Dalvik ma odwrotny problem.

Stos maszyn jest poza tym bardzo prostym narzędziem do przechowywania, które istnieje w projektach procesorów od bardzo dawna. Ma bardzo dobrą lokalizację odniesienia, bardzo ważną cechę nowoczesnych procesorów, które przeżuwają dane znacznie szybciej niż pamięć RAM może je dostarczyć i obsługuje rekurencję. Duży wpływ na projekt języka ma stos, widoczny we wspieraniu zmiennych lokalnych i ograniczony do treści metody. Znaczącym problemem związanym ze stosem jest ten, od którego pochodzi ta witryna.

Istnieje bardzo interesujący / szczegółowy artykuł w Wikipedii na ten temat, Zalety zestawów instrukcji maszynowych . Musiałbym to całkowicie zacytować, więc łatwiej jest po prostu umieścić link. Po prostu zacytuję podtytuły

• Bardzo zwarty kod obiektowy
• Proste kompilatory / proste tłumacze
• Minimalny stan procesora

Aby dodać trochę więcej do pytania o stos. Koncepcja stosu wywodzi się z projektu CPU, w którym kod maszynowy w arytmetycznej jednostce logicznej (ALU) działa na operandach znajdujących się na stosie. Na przykład operacja mnożenia może pobrać dwa górne operandy ze stosu, pomnożyć je i umieścić wynik z powrotem na stosie. Język maszynowy ma zazwyczaj dwie podstawowe funkcje do dodawania i usuwania operandów ze stosu; PUSH i POP. W wielu procesorach dsp (cyfrowy procesor sygnałowy) i kontrolerach maszyny (takich jak ta kontrolująca pralkę) stos znajduje się na samym chipie. Zapewnia to szybszy dostęp do ALU i konsoliduje wymaganą funkcjonalność w jednym układzie.

Jeśli nie zostanie zastosowana koncepcja stosu / sterty, a dane zostaną załadowane do losowej lokalizacji w pamięci LUB dane zostaną zapisane z losowych lokalizacji w pamięci ... będzie to bardzo nieuporządkowane i niezarządzane.

Te koncepcje są używane do przechowywania danych w predefiniowanej strukturze w celu poprawy wydajności, wykorzystania pamięci ... a zatem nazywane strukturami danych.

Można mieć system działający bez stosów, stosując styl kodowania kontynuacji przekazywania . Następnie ramki wywołań stają się kontynuacjami przydzielonymi w stercie śmieci (moduł śmieciowy potrzebuje trochę stosu).

Zobacz stare pisma Andrew Appela: Kompilowanie z kontynuacjami i odśmiecanie może być szybsze niż alokacja stosu

(Może się dzisiaj trochę mylić z powodu problemów z pamięcią podręczną)

Szukałem „przerwania” i nikt nie uznał tego za zaletę. Dla każdego urządzenia, które przerywa mikrokontroler lub inny procesor, zwykle są rejestry, które są wypychane na stos, wywoływana jest procedura obsługi przerwań, a kiedy to się dzieje, rejestry są usuwane ze stosu i umieszczane z powrotem tam, gdzie byli. Następnie wskaźnik instrukcji jest przywracany, a normalna aktywność rozpoczyna się tam, gdzie została przerwana, prawie tak, jakby przerwanie nigdy nie miało miejsca. Dzięki stosowi możesz faktycznie mieć kilka urządzeń (teoretycznie) zakłócających się nawzajem, a wszystko po prostu działa - z powodu stosu.

Istnieje również rodzina języków opartych na stosie, zwanych językami konkatenacyjnymi . Są to wszystkie (jak sądzę) języki funkcjonalne, ponieważ stos jest ukrytym parametrem przekazywanym, a także zmieniony stos jest niejawnym zwrotem z każdej funkcji. Zarówno Forth, jak i Factor (co jest doskonałe) są przykładami, podobnie jak inne. Factor został użyty podobnie jak Lua do gier skryptowych i został napisany przez Slava Pestov, geniusz pracujący obecnie w Apple. Jego Google TechTalk na youtube Obejrzałem kilka razy. Mówi o konstruktorach Boa, ale nie jestem pewien, co miał na myśli ;-).

Naprawdę uważam, że niektóre z obecnych maszyn wirtualnych, takie jak JVM, Microsoft CIL, a nawet ten, który widziałem, został napisany dla Lua, powinny być napisane w niektórych z tych języków opartych na stosie, aby były przenośne na jeszcze więcej platform. Wydaje mi się, że te języki konkatenatywne w jakiś sposób nie mają swojego powołania jako zestawy do tworzenia maszyn wirtualnych i platformy do przenoszenia. Istnieje nawet pForth, „przenośny” Forth napisany w ANSI C, który można by wykorzystać do jeszcze bardziej uniwersalnej przenośności. Ktoś próbował go skompilować za pomocą Emscripten lub WebAssembly?

W przypadku języków opartych na stosie istnieje styl kodu o nazwie zero-point, ponieważ można po prostu wyświetlić listę funkcji do wywołania bez przekazywania jakichkolwiek parametrów (czasami). Jeśli funkcje idealnie do siebie pasują, nie ma nic oprócz listy wszystkich funkcji punktu zerowego, a to byłaby twoja aplikacja (teoretycznie). Jeśli zagłębisz się w Forth lub Factor, zobaczysz, o czym mówię.

W Easy Forth , przyjemnym samouczku online napisanym w JavaScript, oto mała próbka (zauważ „sq sq sq sq” jako przykład stylu wywoływania punktu zerowego):

: sq dup * ;  ok
2 sq . 4  ok
: ^4 sq sq ;  ok
2 ^4 . 16  ok
: ^8 sq sq sq sq ;  ok
2 ^8 . 65536  ok

Ponadto, jeśli spojrzysz na źródło strony Easy Forth, zobaczysz na dole, że jest on bardzo modułowy, zapisany w około 8 plikach JavaScript.

Wydałem dużo pieniędzy na prawie każdą książkę Fortha, którą mogłem zdobyć, próbując zasymilować Fortha, ale teraz zaczynam już lepiej. Chcę dać upust tym, którzy przyjdą później, jeśli naprawdę chcesz to zdobyć (dowiedziałem się o tym za późno), zdobądź książkę na FigForth i zaimplementuj ją. Komercyjne Forthy są zbyt skomplikowane, a największą zaletą Forth jest to, że można zrozumieć cały system, od góry do dołu. W jakiś sposób Forth implementuje całe środowisko programistyczne na nowym procesorze i choć jest taka potrzebaponieważ wydawało się, że C mijało się ze wszystkim, nadal jest użyteczny jako rytuał przejścia do napisania Forth od zera. Tak więc, jeśli zdecydujesz się to zrobić, wypróbuj książkę FigForth - jest to kilka Forthów implementowanych jednocześnie na różnych procesorach. Coś w rodzaju kamienia z Rosetty.

Dlaczego potrzebujemy stosu - wydajności, optymalizacji, punktu zerowego, zapisywania rejestrów po przerwie, a dla algorytmów rekurencyjnych „właściwy kształt”.