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

Поэтому я сейчас изучаю MSIL, чтобы научиться отлаживать мои приложения на C # .NET.

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

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

• Потому что это быстрее?
• Это потому, что он основан на оперативной памяти?
• Для эффективности?

Я пытаюсь понять это, чтобы помочь мне понять коды CIL гораздо глубже.

ОБНОВЛЕНИЕ: мне очень понравился этот вопрос, поэтому я сделал его темой моего блога 18 ноября 2011 года . Спасибо за отличный вопрос!

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, у нас есть соглашение, что «add», «call», «store» и т. Д. Всегда убирают свои аргументы из стека и помещают их результат (если он есть) в стек. Чтобы сгенерировать 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 или любой другой современной инфраструктурой. Самая ранняя реализация этой стратегии, о которой я знаю, - это машина pcode 1966 года.

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

Помните, что когда вы говорите о MSIL, вы говорите о инструкциях для виртуальной машины. ВМ, используемая в .NET, является виртуальной машиной, основанной на стеке. В отличие от виртуальной машины на основе регистров, виртуальная машина Dalvik, используемая в операционных системах Android, является тому примером.

Стек в виртуальной машине является виртуальным, это зависит от интерпретатора или компилятора, работающего точно в срок, чтобы преобразовать инструкции виртуальной машины в реальный код, который выполняется на процессоре. Что в случае .NET почти всегда вызывает дрожание, набор инструкций MSIL был спроектирован так, чтобы его можно было подключить с самого начала. В отличие от байт-кода Java, например, он имеет четкие инструкции для операций с конкретными типами данных. Что делает его оптимизированным для интерпретации. Хотя интерпретатор MSIL действительно существует, он используется в .NET Micro Framework. Который работает на процессорах с очень ограниченными ресурсами, не может позволить себе оперативную память, необходимую для хранения машинного кода.

Фактическая модель машинного кода является смешанной, имеющей как стек, так и регистры. Одна из главных задач оптимизатора кода JIT - найти способы хранения переменных, которые хранятся в стеке, в регистрах, что значительно повышает скорость выполнения. У джиттера Dalvik есть противоположная проблема.

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

Об этом есть очень интересная / подробная статья в Википедии « Преимущества стековых машинных инструкций» . Мне нужно было бы процитировать его целиком, поэтому проще просто поставить ссылку. Я просто процитирую субтитры

• Очень компактный объектный код
• Простые компиляторы / простые интерпретаторы
• Минимальное состояние процессора

Чтобы добавить немного больше к вопросу стека. Концепция стека вытекает из конструкции ЦП, где машинный код в арифметико-логическом блоке (ALU) работает с операндами, расположенными в стеке. Например, операция умножения может взять два верхних операнда из стека, умножить их и поместить результат обратно в стек. Машинный язык обычно имеет две основные функции для добавления и удаления операндов из стека; Жми и поп. Во многих процессорах dsp (цифровой сигнальный процессор) и контроллерах машин (например, управляющих стиральной машиной) стек находится на самой микросхеме. Это обеспечивает более быстрый доступ к ALU и объединяет необходимые функциональные возможности в единую микросхему.

Если концепция стека / кучи не соблюдается и данные загружаются в произвольную область памяти ИЛИ данные сохраняются из случайных областей памяти ... она будет очень неструктурированной и неуправляемой.

Эти концепции используются для хранения данных в заранее определенной структуре для повышения производительности, использования памяти ... и, следовательно, называются структурами данных.

Можно иметь систему, работающую без стеков, используя стиль кодирования продолжения передачи . Затем кадры вызовов становятся продолжениями, размещенными в куче для сбора мусора (сборщику мусора потребуется некоторый стек).

Посмотрите старые сочинения Эндрю Аппеля: Компиляция с продолжениями и сборкой мусора может быть быстрее, чем распределение стеков

(Он может быть немного не прав сегодня из-за проблем с кешем)

Я искал «прерывание», и никто не считал это преимуществом. Для каждого устройства, которое прерывает микроконтроллер или другой процессор, обычно существуют регистры, которые помещаются в стек, вызывается подпрограмма обслуживания прерываний, и когда это делается, регистры извлекаются из стека и возвращаются туда, где они мы. Затем указатель инструкций восстанавливается, и нормальная активность начинается с того места, где он остановился, почти как если бы прерывания никогда не происходило. С помощью стека вы можете на самом деле иметь несколько устройств (теоретически), которые прерывают друг друга, и все это просто работает - из-за стека.

Существует также семейство стековых языков, называемых конкатенационными языками . Все они (я считаю) функциональные языки, потому что стек является неявным передаваемым параметром, а также измененный стек является неявным возвращением каждой функции. И Forth и Factor (что превосходно) являются примерами, наряду с другими. Фактор использовался аналогично Lua для скриптовых игр и был написан Славой Пестовым, гением, в настоящее время работающим в Apple. Его Google TechTalk на YouTube я смотрел несколько раз. Он говорит о конструкторах Боа, но я не уверен, что он имеет в виду ;-).

Я действительно считаю, что некоторые из существующих виртуальных машин, такие как JVM, CIL от Microsoft и даже та, которую я видел, была написана для Lua, должны быть написаны на некоторых из этих стековых языков, чтобы сделать их переносимыми на еще большее количество платформ. Я думаю, что эти сцепленные языки почему-то не имеют своих названий как наборов для создания виртуальных машин и платформ переносимости. Существует даже pForth, «портативный» Forth, написанный на ANSI C, который можно использовать для еще более универсальной переносимости. Кто-нибудь пытался скомпилировать его с помощью Emscripten или WebAssembly?

В языках на основе стека существует стиль кода, называемый нулевой точкой, потому что вы можете просто перечислить функции, которые нужно вызвать, не передавая никаких параметров вообще (время от времени). Если функции отлично сочетаются друг с другом, у вас будет только список всех функций с нулевой точкой, и это будет вашим приложением (теоретически). Если вы углубитесь в Forth или Factor, вы поймете, о чем я говорю.

В Easy Forth , хорошем онлайн-учебнике, написанном на JavaScript, вот небольшой пример (обратите внимание на «sq sq sq sq» в качестве примера стиля вызова с нулевой точкой):

: 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

Кроме того, если вы посмотрите на исходный текст веб-страницы Easy Forth, то увидите, что он очень модульный и содержит около 8 файлов JavaScript.

Я потратил много денег почти на каждую книгу Forth, которую я мог заполучить в попытке ассимилировать Forth, но теперь я только начинаю понимать это лучше. Я хочу выразить готовность тем, кто придет, если вы действительно хотите получить это (я узнал об этом слишком поздно), получите книгу на FigForth и реализуйте это. Коммерческие Forths все слишком сложны, и самое большое в Forth является то, что можно постичь всю систему, сверху донизу. Так или иначе, Forth реализует целую среду разработки на новом процессоре, и хотя необходимостьпоскольку это, кажется, проходит с C на всем, все еще полезно в качестве обряда написать Forth с нуля. Итак, если вы решите сделать это, попробуйте книгу FigForth - это несколько Forths, реализованных одновременно на различных процессорах. Этакий Розеттский Камень Фортов.

Зачем нам нужен стек - эффективность, оптимизация, нулевая точка, сохранение регистров при прерывании, а для рекурсивных алгоритмов это «правильная форма».