Jaki jest cel stosu? Po co nam to?

UPDATE: tak bardzo spodobało mi się to pytanie, że zrobiłem je tematem mojego bloga 18 listopada 2011. 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 jest transfer z pamięci do stosu lub " loading?"Z drugiej strony, dlaczego jest transfer ze stosu do pamięć czy "przechowywanie"? Dlaczego po prostu nie umieścić ich wszystkich w pamięci?

MSIL jest językiem "maszyny wirtualnej". Kompilatory takie jak kompilator C# generują CIL , a następnie w czasie wykonywania inny kompilator o nazwie JIT (Just In Time) kompilator zamienia IL w rzeczywisty kod maszynowy, który może wykonać. Więc najpierw odpowiedzmy na pytanie " po co w ogóle MSIL?"Dlaczego kompilator C# nie wypisuje kodu maszynowego?

Ponieważ jest tańsze aby to zrobić tędy. Załóżmy, że nie zrobiliśmy tego w ten sposób; Załóżmy, że każdy język musi mieć swój własny generator kodu maszynowego. Masz dwadzieścia różnych języków: C#, JScript. NET , Visual Basic, IronPython, F # ... I 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. Teraz Załóżmy, że chcesz dodać nowy procesor. Musisz napisać generator kodu do niego dwadzieścia razy, po jednym dla każdego język.

Ponadto jest to ciężka i niebezpieczna praca. Pisanie wydajnych generatorów kodu dla żetonó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 efektywnej alokacji rejestrów nowych zestawów układów. Przypuśćmy, że zrobimy to w sposób CIL. Ile masz do napisania generatorów CIL? Po jednym na język. Ile kompilatorów JIT musisz napisać? Jeden na procesor. Razem: 20 + 10 = 30 generatorów kodu. Co więcej, generator language-to-CIL jest łatwy do napisania, ponieważ CIL jest prostym językiem, a generator CIL-to-machine-code jest również łatwy do napisania, ponieważ CIL jest prostym językiem. Pozbywamy się wszystkich zawiłości C# i VB i tak dalej i" obniżamy " wszystko do prostego języka, do którego łatwo napisać jitter.

Posiadanie języka pośredniego obniża koszty produkcji nowego kompilatora językadramatycznie . Obniża również koszty obsługi nowego chipa dramatycznie. Chcesz obsługiwać nowy chip, znajdź ekspertów na tym chipie i poproś ich o napisanie CIL jitter i gotowe; następnie obsługujesz wszystkie te języki na swoim chipie.

OK, więc ustaliliśmy, dlaczego mamy MSIL; ponieważ posiadanie języka pośredniego obniża koszty. Dlaczego więc język jest "maszyną stosu"?

Ponieważ maszyny stosowe są koncepcyjnie bardzo proste dla autorów kompilatorów języka. Stosy są prostym, łatwo zrozumiałym mechanizmem dla opisujące obliczenia. Maszyny stosowe są również koncepcyjnie bardzo łatwe do obsługi przez kompilatorów JIT. Korzystanie ze stosu jest uproszczoną abstrakcją, a zatem ponownie, obniża nasze koszty.

Pytasz "po co w ogóle mieć 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ę, że "add"," call"," store " i tak dalej zawsze usuwają swoje argumenty stos i umieścić ich wynik (jeśli istnieje) na stosie. Aby wygenerować kod CIL dla tego C# wystarczy powiedzieć coś w stylu:

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, że zrobiliśmy to bez stosu. Zrobimy to po twojemu, gdzie każdy kod opcode pobiera adresy swoich operandów i adres, na który 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 jest coraz ogromny, ponieważ musimy wyraźnie przydzielić wszystkie tymczasowe przechowywanie , które normalnie przez Konwent po prostu idź na stosie . Co gorsza, nasze same opcody stają się ogromne, ponieważ wszystkie muszą teraz wziąć jako argument adres, na który będą zapisywać swój wynik, oraz adres każdego operanda. Instrukcja "add", która wie, że usunie dwie rzeczy ze stosu i włączy jedną, może być pojedynczym bajtem. Instrukcja add, która zajmuje dwa adresy operandów i adres wynikowy, będzie ogromna.

Używamy opcodów opartych na stosie ponieważ stosy rozwiązują powszechny problem. Mianowicie: chcę przydzielić trochę tymczasowego magazynu, użyć go bardzo szybko, a potem szybko się go pozbyć, gdy skończę . Zakładając, że mamy do dyspozycji stos, możemy sprawić, że opcody będą bardzo małe, a kod bardzo zwięzły.

Aktualizacja: Kilka dodatkowych myśli

Nawiasem mówiąc, pomysł drastycznego obniżenia kosztów przez (1) specyfikację maszyny wirtualnej, (2) pisanie kompilatorów, które są skierowane na język VM, i (3) pisanie implementacji maszyny wirtualnej na różnych urządzeniach nie jest wcale nowym pomysłem. Nie powstała z MSIL, LLVM, Java bytecode, ani żadnej innej nowoczesnej infrastruktury. Najwcześniejszą implementacją tej strategii jest maszyna pcode z 1966 roku.

Pierwszy raz osobiście usłyszałem o tej koncepcji, kiedy dowiedziałem się, jak implementatorom Infocom udało się uruchomić Zork na tak wielu różnych maszynach. Określili wirtualny maszyna nazwała Z-machine , a następnie stworzyła emulatory Z-machine dla całego sprzętu, na którym chcieli uruchomić swoje gry. Miało to dodatkową ogromną korzyść, że mogli zaimplementować zarządzanie pamięcią wirtualną na prymitywnych systemach 8-bitowych; gra mogła być większa niż zmieściłaby się w pamięci, ponieważ mogli po prostu stronicować kod z dysku, gdy tego potrzebowali i odrzucić go, gdy potrzebowali załadować nowy kod.