Я понимаю, что такое указатель стека - но для чего он используется?

Указатель стека указывает на вершину стека, в котором хранятся данные на основе того, что мы называем «LIFO». Чтобы украсть чужую аналогию, это похоже на стопку посуды, в которую вы кладете и принимаете посуду сверху. Указатель стека OTOH указывает на верхнюю «тарелку» стека. По крайней мере, это верно для x86.

Но почему компьютер / программа «заботится» о том, на что указывает указатель стека? Другими словами, для чего нужно иметь указатель стека и знать, куда он указывает?

Объяснение, понятное программистам на Си, будет оценено.

Какой цели на самом деле служит этот стек, в отличие от объяснения его структуры?

У вас есть много ответов, которые точно описывают структуру данных, хранящихся в стеке, и я отмечаю, что это противоположность заданного вами вопроса.

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

Давайте распакуем это.

Продолжение просто говоря, ответ на вопрос : «Что будет происходить дальше в моей программе?» В каждой точке каждой программы что-то должно произойти дальше. Будут вычислены два операнда, затем программа продолжит вычислять их сумму, а затем программа продолжит, присвоив сумму переменной, а затем ... и так далее.

Реификация - это просто хайфлютинское слово для конкретной реализации абстрактной концепции. "Что происходит дальше?" абстрактное понятие; способ построения стека является частью того, как эта абстрактная концепция превращается в реальную машину, которая действительно вычисляет вещи.

Сопрограммы - это функции, которые могут запоминать, где они находились, некоторое время передавать управление другим сопрограммам, а затем возобновлять с того места, где они остановились позже, но не обязательно сразу после только что названного выхода сопрограмм. Подумайте о «yield return» или «await» в C #, который должен помнить, где они были, когда запрашивается следующий элемент или асинхронная операция завершается. Языки с сопрограммами или похожими языковыми функциями требуют более продвинутых структур данных, чем стек, для реализации продолжения.

Как в стеке реализовано продолжение? Другие ответы говорят как. В стеке хранятся (1) значения переменных и временных переменных, время жизни которых, как известно, не превышает активацию текущего метода, и (2) адрес кода продолжения, связанного с самой последней активацией метода. На языках с обработкой исключений в стеке также может храниться информация о «продолжении ошибок», то есть о том, что программа будет делать дальше, когда возникнет исключительная ситуация.

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

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

Основное использование стека - хранить адрес возврата для функций:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

и с точки зрения C это все. С точки зрения компилятора:

• все аргументы функции передаются регистрами ЦП - если регистров недостаточно, аргументы помещаются в стек
• после завершения функции (большинство) регистров должны иметь те же значения, что и до их ввода - поэтому используемые регистры сохраняются в стеке

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

Все это работает, так как нам все равно, сколько элементов уже в стеке или сколько элементов кто-то еще добавит в будущем, нам просто нужно знать, сколько мы переместили указатель стека, и восстановить его после того, как мы закончим.

ЛИФО против ФИФО

LIFO расшифровывается как Last In, First Out. Как и в случае, последний элемент, помещенный в стек, является первым элементом, извлеченным из стека.

То, что вы описали по аналогии с блюдами (в первой редакции ), это очередь или FIFO, First In, First Out.

Основное различие между ними заключается в том, что LIFO / стек выдвигает (вставляет) и извлекает (удаляет) с одного и того же конца, а FIFO / очередь делает это с противоположных концов.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

Указатель стека

Давайте посмотрим, что происходит под колпаком стека. Вот немного памяти, каждое поле является адресом:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

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

Итак, давайте подтолкнем a, b, and cснова. Графика слева, операция «высокого уровня» в середине, псевдокод C-ish справа:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

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

Теперь давайте поп:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Popнапротив push, он настраивает указатель стека так, чтобы он указывал на предыдущее местоположение, и удаляет элемент, который был там (обычно, чтобы вернуть его тому, кто вызвал pop).

Вы, наверное, заметили это bи cдо сих пор в памяти. Я просто хочу заверить вас, что это не опечатки. Мы вернемся к этому в ближайшее время.

Жизнь без стекового указателя

Давайте посмотрим, что произойдет, если у нас нет указателя стека. Начиная с нажатия снова:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Хм, хм ... если у нас нет указателя стека, то мы не можем переместить что-то по адресу, на который он указывает. Возможно мы можем использовать указатель, который указывает на основание вместо вершины.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

Ооо Поскольку мы не можем изменить фиксированное значение базы стека, мы просто перезаписали его a, нажав bв то же место.

Ну, почему бы нам не отследить, сколько раз мы толкнули. И нам также нужно следить за тем временем, когда мы появились.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Ну, это работает, но на самом деле это очень похоже на ранее, за исключением того, *pointerчто дешевле pointer[offset](без дополнительной арифметики), не говоря уже о том, что это меньше, чтобы напечатать. Это кажется потерей для меня.

Давай попытаемся снова. Вместо использования стиля строки Pascal для поиска конца коллекции на основе массива (отслеживания количества элементов в коллекции), давайте попробуем стиль строки C (сканирование от начала до конца):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

Возможно, вы уже догадались о проблеме здесь. Неинициализированная память не гарантируется равной 0. Поэтому, когда мы ищем вершину для размещения a, мы в конечном итоге пропускаем кучу неиспользуемой области памяти, в которой есть случайный мусор. Точно так же, когда мы сканируем наверх, мы в конечном итоге пропускаем намного дальше, чем aмы только что нажали, пока мы, наконец, не находим другое место в памяти, которое только что 0произошло, и возвращаемся назад и возвращаем случайный мусор непосредственно перед этим.

Это достаточно легко исправить, нам просто нужно добавить операции Pushи Popубедиться, что вершина стека всегда обновляется, чтобы быть помеченной знаком 0, и мы должны инициализировать стек с таким терминатором. Конечно, это также означает, что мы не можем иметь 0(или любое другое значение, которое мы выбираем в качестве терминатора) в качестве фактического значения в стеке.

Кроме того, мы также изменили операции O (1) на операции O (n).

TL; DR

Указатель стека отслеживает вершину стека, где происходит все действие. Есть способы как-то избавиться от этого ( bp[count]и topпо сути все еще остаются указателем стека), но оба они оказываются более сложными и медленными, чем просто наличие указателя стека. А незнание того, где находится вершина стека, означает, что вы не можете использовать этот стек.

Примечание. Указатель стека, указывающий на «нижнюю часть» стека времени выполнения в x86, может быть ошибочным, поскольку весь стек времени выполнения переворачивается вверх ногами. Другими словами, основание стека размещается по высокому адресу памяти, а верхушка стека переходит в более низкие адреса памяти. Указатель стека делает точку на кончик стека , где происходит все действие, только что наконечник находится на более низком , чем адрес памяти основания стека.

Указатель стека используется (с указателем фрейма) для стека вызовов (перейдите по ссылке на википедию, где есть хорошая картинка).

Стек вызовов содержит кадры вызовов, которые содержат адрес возврата, локальные переменные и другие локальные данные (в частности, разлитое содержимое регистров; формальные).

Читайте также о хвостовых вызовах (некоторые хвостовые рекурсивные вызовы не нуждаются в каком-либо кадре вызова), обработке исключений (например, setjmp & longjmp , они могут включать в себя одновременное получение нескольких стековых кадров), сигналах и прерываниях и продолжениях . См. Также соглашения о вызовах и двоичные интерфейсы приложений (ABI), в частности ABI x86-64 (который определяет, что некоторые формальные аргументы передаются регистрами).

Кроме того, закодируйте некоторую простую функцию (и) в C, затем используйте ее gcc -Wall -O -S -fverbose-asm для компиляции и посмотрите на сгенерированный .s файл ассемблера.

Аппель написал старую статью 1986 года, в которой утверждалось, что сборка мусора может выполняться быстрее, чем выделение стека (с использованием стиля продолжения-передачи в компиляторе), но это, вероятно, неверно на современных процессорах x86 (особенно из-за эффектов кэширования).

Обратите внимание, что соглашения о вызовах, ABI и расположение в стеке различаются в 32-разрядной версии i686 и 64-разрядной версии x86-64. Кроме того, соглашения о вызовах (и кто отвечает за выделение или выталкивание кадра вызова) могут отличаться для разных языков (например, C, Pascal, Ocaml, SBCL Common Lisp имеют разные соглашения о вызовах ....)

Кстати, последние расширения x86, такие как AVX , накладывают все большие ограничения на выравнивание указателя стека (IIRC, кадр вызова на x86-64 хочет быть выровнен до 16 байтов, то есть двух слов или указателей).

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

Если вы объявляете локальные переменные в функции, стек хранится там, где они хранятся. Кроме того, если вы вызываете другую функцию, в стеке хранится адрес возврата, поэтому он может вернуться к функции, в которой вы находились, когда закончится вызов, и продолжить с того места, где он остановился.

Без SP структурированное программирование, как мы знаем, было бы по существу невозможным. (Вы можете обойтись без него, но это в значительной степени потребует реализации его собственной версии, так что это не большая разница.)

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

Указатель стека ссылается на самое низкое звено цепи и используется процессором, чтобы «увидеть», где находится это самое низкое звено, так что звенья могут быть добавлены или удалены без необходимости перемещения всей цепочки от потолка вниз.

В некотором смысле, внутри процессора x86, стек перевернут, но при этом используется нормальная терминология стековой терминологии, поэтому нижняя ссылка называется вершиной стека.

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

Этот ответ относится конкретно к в указатель стека текущего потока (исполнения) .

В процедурных языках программирования поток обычно имеет доступ к стеку ¹ для следующих целей:

• Поток управления, а именно «стек вызовов».
  • Когда одна функция вызывает другую функцию, стек вызовов запоминает, куда вернуться.
  • Стек вызовов необходим, потому что именно так мы хотим, чтобы «вызов функции» вел себя - «чтобы он продолжал с того места, где мы остановились» .
  • Существуют другие стили программирования, которые не имеют вызовов функций в середине выполнения (например, разрешено указывать следующую функцию только при достижении конца текущей функции) или вообще не имеют вызовов функций (только с использованием переходов и условных переходов ). Эти стили программирования могут не нуждаться в стеке вызовов.
• Параметры вызова функции.
  • Когда функция вызывает другую функцию, параметры могут быть помещены в стек.
  • Для вызывающего и вызываемого абонентов необходимо соблюдать те же правила, что и для того, кто отвечает за очистку параметров из стека после завершения вызова.
• Локальные переменные, которые живут в вызове функции.
  • Обратите внимание, что локальная переменная, принадлежащая вызывающей стороне, может быть сделана доступной для вызываемой стороны путем передачи указателя на эту локальную переменную вызываемой стороне.

Примечание ¹ : посвящено использованию потока, хотя его содержимое полностью читаемо - и разбивается - другими потоками.

В программировании на ассемблере, C и C ++, все три цели могут быть выполнены одним и тем же стеком. В некоторых других языках некоторые цели могут выполняться отдельными стеками или динамически выделяемой памятью.

Вот намеренно упрощенная версия того, для чего используется стек.

Представьте себе стопку как стопку карточек. Указатель стека указывает на верхнюю карту.

Когда вы вызываете функцию:

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

На этом этапе код в функции выполняется. Код скомпилирован, чтобы знать, где каждая карта относительно вершины. Таким образом, он знает, что переменная xявляется третьей картой сверху (т. Е. Указатель стека - 3) и что параметр yявляется шестой картой сверху (т. Е. Указатель стека - 6).

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

Когда функция возвращается, обратная операция просто:

• Найдите маркерную карту и выбросьте все карты над ней. (т.е. установите указатель стека на сохраненный адрес.)
• Восстановите регистры с ранее сохраненных карт и выбросьте их. (т.е. вычесть фиксированное значение из указателя стека)
• Запустите код с адреса на карте сверху, а затем выбросьте его. (т.е. вычтите 1 из указателя стека.)

Стек теперь вернулся в состояние, в котором он был до вызова функции.

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

Это упрощенно для пояснительных целей. На практике параметры и локальные параметры могут быть помещены в регистры как оптимизация, и указатель стека, как правило, будет увеличиваться и уменьшаться на размер слова машины, а не на единицу. (Чтобы назвать пару вещей.)

Современные языки программирования, как вы хорошо знаете, поддерживают концепцию вызовов подпрограмм (чаще всего называемых «вызовами функций»). Это значит, что:

1. В середине некоторого кода вы можете вызывать некоторые другие функции в вашей программе;
2. Эта функция явно не знает, откуда она была вызвана;
3. Тем не менее, когда его работа завершена и она завершена return, управление возвращается к точной точке, в которой был инициирован вызов, со всеми действующими значениями локальной переменной, такими как, когда вызов был инициирован.

Как компьютер отслеживает это? Он ведет постоянную запись о том, какие функции ожидают какие вызовы для возврата. Эта запись является стек и так как это такой важный, мы обычно называем его стек.

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