Какова цель стека? Зачем нам это нужно?

обновление: мне так понравился этот вопрос, что я сделал это тема моего блога 18 ноября 2011 года. Спасибо за отличный вопрос!

Я всегда задавался вопросом: какова цель стека?

Я предполагаю, что вы имеете в виду стек оценке языка MSIL, а не фактического стека для каждого потока во время выполнения.

почему происходит перенос из памяти в стек или "загрузка"?"С другой стороны, почему происходит перенос из стека в память или"хранение"? Почему бы просто не поместить их все в память?

MSIL-это язык "виртуальной машины". Компиляторы, такие как компилятор C#, генерируют CIL, а затем во время выполнения другой компилятор, называемый JIT (как раз вовремя) компилятор превращает IL в фактический машинный код, который может выполняться.

Итак, сначала давайте ответим на вопрос "почему у MSIL вообще есть?"Почему бы просто не заставить компилятор C# написать машину код?

потому что это дешевле сделать это таким образом. Предположим, что мы не сделали это; предположим, что каждый язык должен иметь собственный генератор машинного кода. У вас есть двадцать разных языков: C#,JScript .NET, Visual Basic,IronPython,F#... И предположим, что у вас есть десять разных процессоров. Сколько генераторов кода вам нужно написать? 20 х 10 = 200 генераторов кода. Это большая работа. Теперь предположим, что вы хотите добавить новый процессор. Вы должны написать генератор кода для него двадцать раз, по одному для каждого языка.

кроме того, это трудная и опасная работа. Написание эффективных генераторов кода для чипов, в которых вы не являетесь экспертом, - это тяжелая работа! Разработчики компиляторов являются экспертами по семантическому анализу своего языка, а не по эффективному распределению регистров новых чипсетов.

Теперь предположим, что мы делаем это способом CIL. Сколько генераторов CIL вам нужно написать? По одному на каждый язык. Сколько JIT-компиляторов вам нужно написать? По одному на процессор. Итого: 20 + 10 = 30 генераторы кода. Кроме того, генератор языка в CIL легко писать, потому что CIL-это простой язык, а генератор кода CIL-to-machine также легко писать, потому что CIL-это простой язык. Мы избавляемся от всех тонкостей C# и VB и еще много чего и "опускаем" все до простого языка, на котором легко написать дрожание.

наличие промежуточного языка снижает стоимость создание нового компилятора языка резко. Это также значительно снижает стоимость поддержки нового чипа. Вы хотите поддерживать новый чип, вы находите некоторых экспертов на этом чипе и заставляете их писать дрожание CIL, и все готово; затем вы поддерживаете все эти языки на своем чипе.

Итак, мы установили, почему у нас есть MSIL; потому что наличие промежуточного языка снижает затраты. Почему же тогда язык является "стековой машиной"?

потому что стековые машины концептуально очень просты для авторов компиляторов языка. Стеки-это простой, легко понятный механизм для описания вычислений. Стековые машины также концептуально очень просты для JIT-компиляторов. Использование стека-это упрощающая абстракция, и поэтому снова это снижает наши расходы.

вы спросите: "зачем вообще иметь стек?"Почему бы просто не сделать все прямо из памяти? Ну, давайте подумаем об этом. Предположим, вы хотите, чтобы генерирует CIL-код для:

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

предположим, что у нас есть соглашение, которое "добавляет", "вызывает", "хранит" и т. д. всегда берет свои аргументы из стека и помещает их результат (если он есть) в стек. Чтобы создать CIL-код для этого C#, мы просто скажем что-то вроде:

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.

Теперь предположим, что мы сделали это без стека. Мы сделаем это по-твоему, где каждый код операции принимает адреса своих операндов и адрес, на который он хранит его результат:

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
...

вы видите, как это происходит? Наш код становится огромный потому что мы должны явно выделить все временное хранилище это обычно по соглашению просто идет в стек. Хуже того, наши опкоды сами по себе становятся огромными, потому что все они теперь должны принимать в качестве аргумента адрес, в который они собираются записать свой результат, и адрес каждого операнда. Инструкция" добавить", которая знает, что она будет взять две вещи из стека и положить одну вещь, может быть один байт. Инструкцию add, которая принимает два адреса операндов и адрес результата будет огромная.

мы используем стековые опкоды, потому что стеки решают общую проблему. А именно: я хочу выделить некоторое временное хранилище, использовать его очень скоро, а затем быстро избавиться от него, когда я закончу. Сделав предположение, что у нас есть стек в нашем распоряжении, мы можем сделать коды операций очень маленький и код очень лаконичный.

обновление: некоторые дополнительные мысли

Кстати, эта идея резкого снижения затрат за счет (1) указания виртуальной машины, (2) написания компиляторов, ориентированных на язык виртуальной машины, и (3) написания реализаций виртуальной машины на различных аппаратных средствах, вовсе не является новой идеей. Он не был создан с помощью MSIL, LLVM, байт-кода Java или любых других современных инфраструктур. Самая ранняя реализация этой стратегии, о которой я знаю, - это машина приложения в P - С 1966 года.

впервые я лично услышал об этой концепции, когда узнал, как разработчикам Infocom удалось получить Зорк работает на стольких разных машинах так хорошо. Они указали виртуальную машину под названием Z-машины а затем сделал эмуляторы Z-machine для всего оборудования, на котором они хотели запускать свои игры. Это имело дополнительное огромное преимущество, которое они могли реализовать виртуальная память управление на примитивных 8-битных системах; игра может быть больше, чем поместится в памяти, потому что они могли бы просто страница код с диска, когда они нуждались в нем и отбросить его, когда им нужно было загрузить новый код.