как найти переменные и делается ли это за постоянное время

Question

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

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

Это приводит к предположению, что глобальная переменная является самой медленной в использовании, поскольку она должна пройти весь путь до последней области видимости. Таким образом, он имеет вычислительное время от a * n (a = среднее количество переменных на область, n = количество областей). Если теперь я предполагаю, что мой код является рекурсивным и в рамках рекурсивных вызовов функций для глобальной переменной (допустим, я определил переменную const PI = 3.1416 и я использую ее в каждой рекурсии), то он будет проходить ее снова в обратном направлении для каждого отдельного вызова и если моя рекурсивная функция требует 1000 рекурсий, то она делает это 1000 раз.

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

Answer 1

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

Память - это форма хранения, в которой каждой ячейке присваивается номер, ячейка называется слово , а число называется адрес .
Набор адресов называется адресное пространство , адресное пространство обычно представляет собой диапазон адресов или объединение диапазонов адресов.

Компилятор предполагает, что данные программы будут загружены по определенному адресу, скажем X , и что после X (то есть X достаточно памяти) +1, X + 2, X + 3, ..., все существует) для всех данных.
Переменные затем располагаются последовательно, начиная с X и далее, задачей компилятора является сохранение связи между адресом X + k и переменной экземпляр .
Обратите внимание, что переменная может создаваться более одного раза, дважды вызывая функцию или рекурсия - оба примера этого.
В первом случае два экземпляра могут иметь один и тот же адрес X + k , поскольку они не перекрываются во времени (к тому времени, когда второй экземпляр жив, первый более).
Во втором случае два экземпляра перекрываются во времени и должны использоваться два адреса.

Итак, мы видим, что время жизни переменной влияет на то, как выполняется сопоставление между именем переменной и ее адресом (a.k.a. выделение переменной).
Две общие стратегии:

• Стек
  Мы начинаем с адреса X + b и размещаем новые экземпляры по последовательным адресам X + b + 1, X + b + 2 и т. Д.
  Текущий адрес (например, X + b + 54) хранится где-то (это указатель стека).
  Когда мы хотим освободить переменную, мы возвращаем указатель стека (например, от X + b + 54 до X + b + 53).
  Мы видим, что невозможно освободить переменную, которая не выделена последней.
  Это обеспечивает быстрое выделение / освобождение очень и, естественно, соответствует потребности в функциональном кадре, который содержит локальные переменные: когда вызывается функция, новые переменные распределяются, а когда она заканчивается, они удаляются.
  Из того, что мы отметили выше, мы видим, что если f вызывает g (то есть f является родителем g ), то переменные f не может быть освобожден раньше, чем g .
  Это опять-таки естественно соответствует семантике функций.

• Куча
  Эта стратегия динамически выделяет экземпляр переменной по адресу X + o .
  Среда выполнения резервирует блок адресов и управляет их статусом (свободен, занят), когда его просят, он может дать свободный адрес и пометить его как занятый.
  Это полезно для выделения объекта, размер которого зависит, например, от пользовательского ввода.

• Куча (статическая)
  Некоторые переменные имеют продолжительность жизни программы, но их размер и число известны как время компиляции.
  В этом случае компилятор просто назначает каждому экземпляру уникальный адрес X + i .
  Они не могут быть освобождены, они загружаются в память вместе с кодом программы и остаются там до тех пор, пока программа не будет выгружена.

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

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

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