Области памяти. Стек.

Давайте подробнее поговорим о том, что это значит, когда говорят, что "структуры в Swift хранятся на стеке". Что это вообще такое?

Стек как структура данных

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

Это структура, которая работает по принципу LIFO (Last-In-First-Out), т.е. последний вошел, первый вышел. Для визуализации этой идеи обычно приводят пример с тарелками или стопками:

Стек поддерживает такие методы, как:

push: для добавления элемента наверх стека
pop: для удаления элемента сверху стека
peek: просматривает верхний элемент
count: возвращает количество элементов в стеке

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

Применение концепции стека

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

(4 * 2 / (3 + 1)) = 2

А теперь представим его немного в другом виде:

divide(multiply(4, 2), sum(3, 1))

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

static func / (lhs: Self, rhs: Self) -> Self

Но для простоты понимания мы распишем их как самостоятельные функции, а также разнесём вызовы по строкам. Это могло бы выглядеть так:

func calculate() -> Int {
    let a = multiply(4, 2)
    let b = sum(3, 1)
    let result = divide(a, b)
    return result
}

func divide(_ a: Int, _ b: Int) -> Int {
    return a / b
}
func multiply(_ a: Int, _ b: Int) -> Int {
    return a * b
}
func sum(_ a: Int, _ b: Int) -> Int {
    return a + b
}

Теперь проследим логику выполнения программы, и как в ней используется стек.

На вход мы получаем вызов самой функции calculate. Блок кода этой функции складывается на верх стека. Это значит, что сейчас выполняются инструкции, описанные внутри этого блока.
Программа будет выполнять инструкции в порядке их вызова. Первым нам нужно вычислить аргумент a. Так мы сразу натыкаемся на вызов функции multiply. Теперь уже на верх нашего стека добавляется блок функции multiply, и он начинает выполняться.
Предположим, что функция multiply не совершает дополнительных действий. Она завершает расчёт и должна выполнить return. В этот момент блок этой функции убирается с вершины стека, теперь сверху снова calculate. Но что более важно, родительская функция должна продолжить выполняться с того места, где остановилась (запомните этот момент).
Все оставшиеся блоки выполнятся таким же образом. И в конце уже сама функция calculate уберётся с вершины стека и вернёт управление коду, который её вызвал.

Таким образом, мы можем сделать вывод, что стек позволяет нам всё время держать контекст выполняемых функций, сохраняя порядок их вызова.

Стек вызовов (Call Stack)

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

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

По сути своей стек фреймы это участки памяти. Поскольку Swift строго типизированный язык, то под каждую функцию рассчитывается определенный размер стек фрейма. Размер всего стека константная величина. Как раз, если блоки стек фреймов превысят эту величину, случается легендарная ошибка переполнения стека (stack overflow).

Сами фреймы должны нести в себе следующую информацию:

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

Вершина стека смещается всё время, пока идёт вызов: память то занимается, то отпускается. Указатель вершины стека (stack pointer) нужен, чтобы знать, где эта вершина сейчас.

От текущей вершины до предыдущего стек фрейма нельзя отступить одним и тем же шагом, т.к. размеры стек фреймов отличаются. Для этого и нужен указатель фрейма (frame pointer). Он хранит место предыдущего стек фрейма, и возврат идёт по нему.

Переменные лежат в своих стек фреймах. Пока фрейм на вершине стека, его переменные и видны. Это и есть то, что мы называем областью видимости функции.

Вывод

Когда утверждается, что value type хранится на стеке, это означает, что он располагается в участке памяти, выделенном для стек фрейма.

Не забывайте, что стек, куча и код программы: все лежат в оперативной памяти. При запуске под стек резервируется место для каждого потока отдельно (но об этом в другой раз). Размер стек фрейма компилятор считает заранее, а память под него занимается в момент вызова функции.