Изучая программирование, мы очень скоро сталкиваемся с концепцией локальных и глобальных переменных. Всё логично и просто: локальные переменные существуют только внутри функции или функционального блока, а глобальные, как и положено, существуют всё время и доступны из любого места.
Почему, например, все переменные не могут быть глобальными? Да вполне себе могут. И я так раньше делал, а почему, напишу в конце.
Проблема же будет в том, что все эти глобальные переменные скопятся в эдакое большое множество, в котором будет трудно ориентироваться. Либо на каждый отдельный случай надо мучительно заводить переменную с уникальным именем, либо надо тщательно следить, какая переменная в каком месте программы занята, чтобы их переиспользовать.
Локальные переменные избавляют нас от таких сложностей. Их можно создать и использовать прямо по месту, а затем уничтожить. У них могут быть одни и те же имена, потому что они доступны только локально.
Получается, что это вполне себе логичное изобретение. Однако же это не совсем изобретение, а скорее неотъемлемая часть того, как устроена программа. Даже если бы нам были не нужны локальные переменные, они всё равно появились бы, и вот почему.
Наивный компьютер
В предыдущих материалах, посвящённых адресации, моделировалась ситуация, когда мы самостоятельно изобретаем компьютер, чтобы понять, какие проблемы нужно при этом решить. В основном это касалось выделения адресов памяти. Продолжим в том же духе.
В случае с глобальными переменными всё должно быть просто. Программа занимает кусок памяти, а вся остальная память свободна. Компилятор может посчитать все глобальные переменные в программе и заранее выделить адрес свободной памяти под каждую из них.
Такая структура очень проста, только вся память под переменные будет выделена сразу. На деле это вообще не страшно, ведь мы не держим в программе миллиарды глобальных переменных. Разве что это могут быть очень большие массивы, но если надо работать с ними, то и память под них потребуется в любом случае.
Проблема здесь в другом.
Рекурсия
Рассмотрим пару функций, которые делают цикл (это язык типа JS, но на деле неважно какой):
Обе они используют глобальную переменную i. Пока эти функции запускаются отдельно друг от друга, проблем нет. После того, как одна функция закончила работу, переменная переиспользуется другой функцией.
Но как только из функции f1() нужно вызвать f2(), возникает проблема. Функция f2() должна начать использовать переменную i, но функция f1() ещё не закончила её использовать.
Выйти из ситуации можно, назначив каждой функции свою собственную глобальную переменную, которая больше нигде не используется:
Конечно, это становится уже неудобно, но вопрос сейчас не в удобстве, а в том, можно ли это сделать на нашем примитивном уровне. Да, можно.
Но что, если функции f1() надо вызывать саму себя? Это будет рекурсивная функция.
Рассмотрим такой пример.
Функция печатает значения из массива arr. Но если значение, в свою очередь, является массивом, то функция вызывает сама себя, чтобы напечатать этот массив.
Что здесь не так? Пока сосредоточимся на первой проблеме. Вызывая сама себя, функция переиспользует собственный счётчик i, теряя его текущее значение. Поэтому цикл не может продолжаться нормальным образом.
При этом мы не можем назначить функции уникальный счётчик. Ведь она вызывает саму себя.
Нам надо обеспечить уникальность переменной счётчика не только для функции, но и для каждого конкретного вызова этой функции.
Можно ли это сделать, имея в распоряжении только глобальные переменные? Да, нам нужно просто сохранять и восстанавливать текущие счётчики где-нибудь в массиве, например. Сделаем глобальный массив для хранения и индекс, который будет текущим местом сохранения в массиве:
vars = [ ... тут резервируется сколько-то памяти ... ];
v_index = 0;
Теперь перед каждым новым вызовом функции будем сохранять её текущий счётчик i в массив vars, а после вызова восстанавливать обратно:
Переменная i переиспользуется, но её значения остаются корректными между вызовами функций, потому что сохраняются и восстанавливаются. По факту реальные счётчики функций лежат в массиве vars, и каждый из них действительно уникален, так как имеет собственный индекс в массиве.
Обратим внимание, что счётчики в массиве vars актуальны только пока работают функции. Если, к примеру, функция рекурсивно вызвала сама себя 10 раз, то в массиве будет лежать 10 счётчиков. Когда вызовы завершаются, счётчиков становится 9, 8, 7... и наконец 0. Массив полностью освобождается для переиспользования.
Таким образом мы, действуя наивно, всё-таки пришли к концепции локальных переменных, которые существуют только во время выполнения функции.
Займёмся второй проблемой. Так как массив arr глобальный, то функция при каждом рекурсивном вызове будет перебирать его с нуля. Нам же нужно, чтобы рекурсивный вызов перебирал не массив arr, а тот его элемент, который в свою очередь является массивом.
Но сделать этого мы опять же не можем, так как имя массива arr уже жёстко прошито в функции. Выйти из положения мы можем тем же самым путём. Что, если заводить новую переменную для каждого элемента массива? Сделаем ещё один глобальный массив и индекс для хранения:
arr_elements = [ ... тут резервируется сколько-то памяти ... ];
ae_index = 0;
А функция теперь будет брать нужный массив из arr_elements:
Первоначально мы помещаем в arr_elements исходный массив arr. Это первый элемент для вывода. В дальнейшем, по мере нахождения новых массивов, они будут добавляться в arr_elements по очереди. Функция теперь смотрит не на переменную arr, а на переменную arr_elements[ae_index]. По факту мы получили множественные версии переменной arr, которые уникальны для каждого вызова и опять же получаются локальными.
Можно выдохнуть и считать, что рекурсия на глобальных переменных, в общих чертах, работает. Но теперь обратим внимание на очевидные оптимизации.
Когда функция вызывает другую функцию (в том числе саму себя), то она не может закончиться раньше, чем закончится этот другой вызов. Вызовы получаются вложенными друг в друга как матрёшки. Каждый новый вызов помещается наверх стопки уже существующих. Вместе с вызовом в эту стопку помещаются и те переменные, которые мы для него создаём.
Ура, мы изобрели классический LIFO-стек!
Давайте больше не будем сдерживаться и перепишем функцию с использованием единого стека:
Теперь надо внимательно следить за порядком помещения элементов в стек: элемент массива помещается туда последним (LI – Last In), чтобы при следующем вызове функции оказаться на вершине стопки (FO – First Out). Этого и ожидает функция.
Так как работа с arr переделана на работу с чистым стеком, можно также убрать зависимость от имени переменной i:
Переписывать всё очень громоздко, но суть, думаю, понятна. Теперь функция вместо использования глобальной переменной i (и её сохранения и восстановления) просто выделяет себе ещё один элемент на стеке, а потом освобождает его. При этом, так как переменная-счётчик теперь занимает верхушку стека, нужный функции параметр находится под ней, то есть для доступа к нему требуется индекс [st_index - 1].
Нетрудно видеть, что на этот раз переменная-счётчик стала истинно локальной: она создаётся только в функции, и больше нигде, и ею же освобождается.
Синтаксический сахар
Осталось совсем чуть-чуть до нормальной программы. Просто представим, что когда мы пишем такое:
var i
Компилятор будет понимать, что это равносильно следующим действиям:
- st_index++;
- далее везде, где написано i, подставлять stack[st_index]
- в конце функции сделать st_index-- и забыть о предыдущих пунктах
Теперь мы можем переписать программу так:
for (var i = 0; i < stack[st_index - 1].length; i++) ...
И вот у нас уже привычная локальная переменная i.
Стековый фрейм
Возникает другая проблема. Предположим, мы создали локальную переменную i, некоторое время ею попользовались, а затем решили создать ещё одну локальную переменную j. Теперь j будет лежать на верхушке стека stack[st_index], доступ к i будет выглядеть как stack[st_index - 1], а к параметру функции как stack[st_index - 2]. То есть когда мы в стеке создаём новую переменную, смещения всех предыдущих сдвигаются назад на 1.
Как же с ними быть? Если в один времени переменная i имеет смещение stack[st_index], а в другой уже stack[index - 1], то очевидно невозможно пользоваться ею.
Компилятор поступает так же, как для глобальных переменных: заранее подсчитывает, сколько всего локальных переменных встречается в функции. И сразу резервирует под них место на стеке:
bp_index = st_index;
st_index += 12;
В данном случае индекс стека сдвигается сразу на 12, то есть резервируется место под 12 локальных переменных. Есть ещё один нюанс: так как индекс стека в принципе всё время куда-то сдвигается, то для отсчёта смещений для локальных переменных берётся фиксированный индекс, который условно называется BP (Base Pointer).
В приведённом выше примере bp_index сохраняет индекс верхушки стека на момент вызова функции. Теперь относительно этого фиксированного индекса можно получать доступ к любым локальным переменным: параметр функции будет находиться в stack[bp_index], переменная i в stack[bp_index + 1], переменная j в stack[bp_index + 2], и так далее, и эти смещения уже никак не будут зависеть от появления или исчезновения других локальных переменных.
Подобным образом выделенный кусок стека называется стековым фреймом, иначе говоря, кадром. Освобождается он тоже одним куском:
st_index -= 12;
Естественно, что bp_index в данном случае также глобальный и поэтому каждая функция будет его переиспользовать, но фишка в том, что bp_index можно сохранять и восстанавливать... прямо в том же самом стеке!
А что, можно было?
То, что мы сделали руками, уже есть в готовом виде и собственно называется стеком программы :) Это заранее выделенная область памяти с заранее настроенным индексом, который хранится в регистре процессора под условным названием SP (Stack Pointer). А индекс фрейма хранится в регистре с условным названием BP.
И если посмотреть текст программы, транслированный на язык ассемблера, то там вместо имён переменных мы как раз и увидим смещения вроде [bp+4] или [bp-8]. Они могут быть положительные или отрицательные, это зависит только от того, как именно организован стек и с какого места и в какую сторону идёт отсчёт индексов.
Вот, скажем, тестовая функция с локальными переменными i, j, k:
А вот eё ассемблерный код:
Здесь rsp и rbp это 64-битные версии 16-битных регистров sp и bp. Стек здесь растёт в сторону уменьшения адресов, т.е. от конца памяти к началу, поэтому относительно его верхушки смещения отрицательные. Верхушка стека фиксируется в rbp – это начало фрейма. Далее каждая переменная получает своё смещение относительно rbp. Фрейм, таким образом, существует и имеет размер 16 байт (вместе с сохранённым в стеке rbp), но к указателю стека ничего не прибавляется, так как эта функция больше ничего не вызывает.
Посмотрим, что будет, если добавить в функцию вызов самой себя:
Бессмысленный код, но в ассемблерном тексте появилось кое-что новое:
А именно, от указателя стека отнимается 16, это и есть размер фрейма. Вложенный вызов функции будет использовать стек через 16 байт от текущего указателя rbp.
Инструкция leave это сокращение для инструкций восстановления указателя стека и rbp. Поэтому здесь нет явных add rsp, 16 и pop rbp.
Передача параметров
Осталось рассмотреть передачу параметров в функцию. Мы уже сделали это, воспользовавшись стеком. То есть положили элемент массива в стек, вызвали функцию, а она взяла этот элемент из стека. С помощью синтаксических соглашений можно преобразовать подобные вызовы в такой вид:
print_array(arr[i]);
Это будет означать: положи arr[i] в стек и вызови функцию print_array().
Далее, сама функция будет описана так:
function print_array(arr) { ... }
Это будет означать: функция должна взять из верхушки стека элемент и считать его локальной переменной с условным именем arr.
И вот финальный вид нашей функции:
Заметим, что совпадение имени arr в вызове функции и в описании функции абсолютно ничего не значит. Мы можем передавать в функцию глобальную переменную arr[i], но в самой функции она будет считаться локальной переменной с условным названием arr, или с любым другим, какое напишем:
function print_array(xxx) { ... }
Это просто переменная, которая сейчас лежит на вершине стека, независимо от её имени. Ну и, не совсем на вершине, так как при вызове функции в стек кладётся ещё и адрес возврата, но это уже детали, которые легко учесть.
Данный пример легко расширить для любого числа параметров:
function test(x, y, z) { ... }
Параметр x будет на вершине стека, параметр y под ним (смещение +1), а z под y (смещение +2). Или в обратном порядке. Смотря как их клали в стек. Этим заведует компилятор.
Тут нужно заметить, что хотя передача параметров через стек это классический случай, компиляторы по возможности оптимизируют процесс, передавая значения через свободные регистры.
Почему я использовал глобальные переменные
Потому что я был дремуч :)
Мне казалось, что глобальные переменные это очень просто и быcтро, ведь они существуют постоянно. В то же время введение каждой новой локальной переменной вызывало у меня ощущение, что компьютер должен затрачивать какие-то специальные усилия, чтобы её создать, а потом избавиться от неё. Казалось, что это будет медленнее. Особенно если эта переменная например находится внутри цикла. Она что, на каждом шаге цикла будет создаваться, или как? Неясность в этом вопросе (и нежелание разобраться до конца) порождала повышенную осторожность и использование если не глобальных, то по крайней мере внешних по отношению к циклу переменных.
На деле же, как мы видим, ничего подобного не происходит. В любом локальном контексте существует стековый фрейм, где локальные переменные точно так же зарезервированы заранее, как и глобальные.
Каждая из них имеет свой локально-постоянный адрес, который получается через смещение вроде [rbp-4]. Единственное, что здесь может вызвать сомнения, это как раз использование смещений. Ведь если сравнить доступ к просто адресу, или к адресу, к которому нужно прибавить смещение, интуитивно покажется, что второй вариант медленнее.
На самом деле такие операции хорошо оптимизированы, так что бояться нечего.
Есть накладные расходы, вроде создания стекового фрейма и последующего восстановления, но это уже совсем мелочи. В отдельных случаях можно ими обеспокоиться, конечно. Но мои случаи были явно не такими :)
