Что такое call stack какие ключевые слова вы знаете
JavaScript: Стек вызовов и магия его размера
Большинство разработчиков, которые использовали рекурсию для решения своих задач, видели такую ошибку:
Но не каждый разработчик задумывался о том, а что означает «размер стэка вызовов» и каков же этот размер? А в чем его измерять?
Думаю, те, кто работают с языками, напрямую работающими с памятью, смогут легко ответить на этот вопрос, а вот типичный фронтэнд разработчик скорее всего задает себе подобные вопросы впервые. Что-ж, попробуем разобраться!
Многие полагают, что браузер ограничивает нас именно в количестве вызовов, но это не так. В данной статье я покажу на простых примерах, как это работает на самом деле.
О чем ты вообще, автор?
Когда возникает эта ошибка?
Если попытаться вызвать такую функцию, то мы увидим в консоли/терминале ошибку, о которой я упомянул выше.
А что если подглядеть, сколько же раз выполнилась функция перед тем, как возникла ошибка?
На данном этапе код запускается в Chrome DevTools последней версии на март 2021. Результат будет различаться в разных браузерах. В дальнейшем в статье я упомяну об этом.
Для эксперимента будем использовать вот такой код:
Результатом вывода в консоль стало число в 13914. Делаем вывод, что перед тем, как переполнить стэк, наша функция вызвалась почти 14 тысяч раз.
Магия начинается тогда, когда мы начинаем играться с этим кодом. Допустим, изменим его вот таким образом:
Единственное, что мы добавили, это объявление переменной someVariable в теле функции. Казалось бы, ничего не поменялось, но число стало меньше. На этот раз функция выполнилась 12523 раз. Что более чем на тысячу меньше, чем в прошлом примере. Чтобы убедиться, что это не погрешность, пробуем выполнять такой код несколько раз, но видим одни и те же результаты в консоли.
Почему же так? Что изменилось? Как понять, посмотрев на функцию, сколько раз она может выполниться рекурсивно?!
Магия раскрыта
У нас уже достаточно много данных. Может быть, поэкспериментируем еще? А давайте попробуем вычислить, какой размер коллстэка в движке, который использует Chrome?
Математика все-таки пригодилась
Как мы выяснили, у нас есть две неизвестные, которые составляют размер функции (капельки, которая падает в емкость). Это размер самого Execution Stack, а так же сумма размеров всех переменных внутри функции. Назовем первую N, а вторую K. Сам же неизвестный размер коллстэка обозначим как X.
Учитывая, что мы знаем количество вызовов первой функции, в теле которой не объявляются переменные, размер коллстэка можно выразить как:
И, для второго случая, возьмем функцию, внутри которой было объявлено пять переменных.
Если выразить отсюда N, то получим ответ: N равно приблизительно 72. В данном случае 72 байтам.
Теперь, подставив N = 72 в самое первое уравнение, получим, что размер коллстэка в Chrome равен. 1002128 байтов. Это почти один мегабайт. Не так уж и много, согласитесь.
Мы получили какое-то число, но как убедиться, что наши расчеты верны и число правильное? А давайте попробуем с помощью этого числа спрогнозировать, сколько раз сможет выполниться функция, внутри которой будет объявлено 7 переменных типа ‘number’.
Считаем: Ага, каждая функция будет занимать (72 + 7 * 8) байт, это 128. Разделим 1002128 на 128 и получим число. 7829! Согласно нашим расчетам, такая функция сможет рекурсивно вызваться именно 7829 раз! Идем проверять это в реальном бою.
Размер стэка разнится от браузера к браузеру. Возьмем простейшую функцию из начала статьи. Выполнив ее в Сафари получим совершенно другую цифру. Целых 45606 вызовов. Функция с пятью переменными внутри выполнилась бы 39905 раз. В NodeJS числа очень близки к Chrome по понятным причинам. Любопытный читатель может проверить это самостоятельно на своем любимом движке JavaScript.
А что с непримитивами?
Если с числами все вроде бы понятно, то что насчет типа данных Object?
А что с этим? А как поведет себя вот это? А что с *?
Как вы заметили, экспериментировать можно бесконечно. Можно придумать огромное количество кейсов, которые будут прояснять эту ситуацию глубже и глубже. Можно ставить эксперименты при разных условиях, в разных браузерах, на разных движках. Оставляю это на тех, кого эта тема заинтересовала.
Итоги:
Количество рекурсивных вызовов функции до переполнения стэка зависит от самих функций.
Размер стэка измеряется в байтах.
Чем «тяжелее» функция, тем меньше раз она может быть вызвана рекурсивно.
Размер стэка в разных движках различается.
Вопрос особо любознательным: А сколько переменных типа «number» должно быть объявлено в функции, чтобы она могла выполниться рекурсивно всего два раза, после чего стэк переполнится?
Контекст выполнения и стек вызовов в JavaScript
Если вы — JavaScript-разработчик или хотите им стать, это значит, что вам нужно разбираться во внутренних механизмах выполнения JS-кода. В частности, понимание того, что такое контекст выполнения и стек вызовов, совершенно необходимо для освоения других концепций JavaScript, таких, как поднятие переменных, области видимости, замыкания. Материал, перевод которого мы сегодня публикуем, посвящён контексту выполнения и стеку вызовов в JavaScript.
Контекст выполнения
Контекст выполнения (execution context) — это, если говорить упрощённо, концепция, описывающая окружение, в котором производится выполнение кода на JavaScript. Код всегда выполняется внутри некоего контекста.
▍Типы контекстов выполнения
В JavaScript существует три типа контекстов выполнения:
Стек выполнения
Стек выполнения (execution stack), который ещё называют стеком вызовов (call stack), это LIFO-стек, который используется для хранения контекстов выполнения, создаваемых в ходе работы кода.
Когда JS-движок начинает обрабатывать скрипт, движок создаёт глобальный контекст выполнения и помещает его в текущий стек. При обнаружении команды вызова функции движок создаёт новый контекст выполнения для этой функции и помещает его в верхнюю часть стека.
Движок выполняет функцию, контекст выполнения которой находится в верхней части стека. Когда работа функции завершается, её контекст извлекается из стека и управление передаётся тому контексту, который находится в предыдущем элементе стека.
Изучим эту идею с помощью следующего примера:
Вот как будет меняться стек вызовов при выполнении этого кода.
Состояние стека вызовов
Когда вышеприведённый код загружается в браузер, JavaScript-движок создаёт глобальный контекст выполнения и помещает его в текущий стек вызовов. При выполнении вызова функции first() движок создаёт для этой функции новый контекст и помещает его в верхнюю часть стека.
Когда функция first() завершает работу, её контекст извлекается из стека и управление передаётся глобальному контексту. После того, как весь код оказывается выполненным, движок извлекает глобальный контекст выполнения из текущего стека.
О создании контекстов и о выполнении кода
До сих пор мы говорили о том, как JS-движок управляет контекстами выполнения. Теперь поговорим о том, как контексты выполнения создаются, и о том, что с ними происходит после создания. В частности, речь идёт о стадии создания контекста выполнения и о стадии выполнения кода.
▍Стадия создания контекста выполнения
Перед выполнением JavaScript-кода создаётся контекст выполнения. В процессе его создания выполняются три действия:
Привязка this
В глобальном контексте выполнения this содержит ссылку на глобальный объект (как уже было сказано, в браузере это объект window ).
В контексте выполнения функции значение this зависит от того, как именно была вызвана функция. Если она вызвана в виде метода объекта, тогда значение this привязано к этому объекту. В других случаях this привязывается к глобальному объекту или устанавливается в undefined (в строгом режиме). Рассмотрим пример:
Лексическое окружение
Проще говоря, лексическое окружение — это структура, которая хранит сведения о соответствии идентификаторов и переменных. Под «идентификатором» здесь понимается имя переменной или функции, а под «переменной» — ссылка на конкретный объект (в том числе — на функцию) или примитивное значение.
В лексическом окружении имеется два компонента:
Лексическое окружение можно представить в виде следующего псевдокода:
Окружение переменных
Окружение переменных (Variable Environment) — это тоже лексическое окружение, запись окружения которого хранит привязки, созданные посредством команд объявления переменных ( VariableStatement ) в текущем контексте выполнения.
Так как окружение переменных также является лексическим окружением, оно обладает всеми вышеописанными свойствами лексического окружения.
Рассмотрим примеры, иллюстрирующие то, что мы только что обсудили:
Схематичное представление контекста выполнения для этого кода будет выглядеть так:
Только что мы только что описали, называется «поднятием переменных» (Hoisting). Объявления переменных «поднимаются» в верхнюю часть их лексической области видимости до выполнения операций присвоения им каких-либо значений.
▍Стадия выполнения кода
Это, пожалуй, самая простая часть данного материала. На этой стадии выполняется присвоение значений переменным и осуществляется выполнение кода.
Итоги
Только что мы обсудили внутренние механизмы выполнения JavaScript-кода. Хотя для того, чтобы быть очень хорошим JS-разработчиком, знать всё это и не обязательно, если у вас имеется некоторое понимание вышеописанных концепций, это поможет вам лучше и глубже разобраться с другими механизмами языка, с такими, как поднятие переменных, области видимости, замыкания.
Уважаемые читатели! Как вы думаете, о чём ещё, помимо контекста выполнения и стека вызовов, полезно знать JavaScript-разработчикам?
Что такое call stack?
Когда-то был оператор goto, и программы выглядели так
Мы что-то проверяем, если проверка успешна, вызываем какое-то действие. Затем возвращаемся назад.
Но такой вариант оказался неудобным, если это какое-то действие нужно вызывать из разных мест, а потом возвращаться именно в эти разные места. Поэтому сейчас используется не goto, а call (вызов), который кладет в стек адрес текущего места выполнения и переходит в подпрограмму. В конце подпрограммы по команде return, он берет из стека адрес и по нему возвращается назад.
Так как в стек можно положить что-то еще, то можно внутри вызванной подпрограммы вызвать другую подпрограмму, и рекурсивно вызывать столько раз сколько нужно. Потом все call-ы будут красиво закрыты return-ами в обратном порядке.
В данном варианте у нас работает так:
1. из основной части main, вызывается program1 (в стек кладется адрес этой)
2. из вызванного program1 вызывается program3 (в стек добавляется адрес этой команды, там уже две)
3. из program3 мы возвращаемся, беря последнее значение из стека (возвращаемся в program1)
4. снова возвращаемся, беря адрес из стека и попадаем в main
5. тоже самое с вызовом program2-program3-program2-main
Стек обычно растет сверху вниз, каждая команда return берет самый последний нижний адрес и возвращается по нему, что позволяет создавать множество вложенных вызовов, и рекурсивно с ними работать.
Но не нужно забывать, что стек не бесконечен. десять или сто вызовов вообще ни о чем на современных компах, но миллион или миллиард, умножить на размер адреса (например 4 байта), может занять мегабайты и гигабайты.
Чтобы при остановке выполнения (на точке останова или при выбросе исключения) узнать, в какой функции (и возможно с номером строчки кода) произошла остановка, со вложенностью.
Call stack trace of exception:
Английский не очень хорошо знаю,
Простое объяснение рекурсии и стека вызовов
Перевод статьи «Recursion and the Call Stack Explained By Reading A Book».
Рекурсия это один из наиболее потрясающих принципов во всех языках программирования.
Нерекурсивные функции (другими словами, функции, которые вы использовали в прошлом), запускались единожды при каждом вызове и возвращали результат благодаря инструкции возврата return.
А вот рекурсивная функция, вызванная единожды, может затем вызывать сама себя неопределенное число раз, прежде чем скомбинирует результат всех вызовов и вернет его по инструкции return.
Выглядит это примерно так.
Рекурсия замечательна тем, что отдельная функция может вызываться от одного до бесконечного числа раз благодаря простой инструкции.
Но вместе с тем довольно сложно придумать для этой ситуации аналогию из окружающего мира. И находить аналогии становится еще сложнее, когда мы затрагиваем концепцию стека вызовов (о ней мы еще поговорим).
Кто-то предлагает в качестве аналогии набор коробок, внутри которых спрятаны другие коробки:
Другие предлагают представить себе матрешку:
Но этот пример бесполезен для понимания стека вызовов.
В этой руководстве мы рассмотрим два популярных примера рекурсии. Также мы создадим визуальный язык для понимания функции и стека вызовов — это поможет нам разобраться в многократных вызовах функции, идущих подряд.
Чтобы разобраться в концепциях этой статьи, нужно иметь базовое понимание функций в JavaScript.
Пример 1 — факториалы
Факториалы это самый распространенный пример рекурсии. Вероятно, вы знакомы с понятием факториалов по курсу алгебры.
Факториал числа 3 записывается как 3! и означает 3*2*1, что равно 6.
Это можно выразить при помощи цикла for, где обновление переменной будет происходить вне цикла:
Но с той же целью мы можем использовать и рекурсию. Вместо того чтобы создавать цикл, обновляющий переменную вне своей области видимости, мы можем применить рекурсию и сделать n-1 вызовов, где n — искомый факториал.
Я сначала покажу, как это выглядит в виде кода, а затем мы оценим, как это работает.
Этот код позволяет достигнуть того же результата, что и код, приведенный выше.
Но если вы посмотрите на строку 5, вы заметите, что инструкция return упоминает саму функцию.
Так когда же эта функция вернет итоговое значение? Как нам связать 4 вызова функции, чтобы в итоге вернулось значение 24?
Вот как раз здесь нам и пригодится стек вызовов. Он определяет правила для порядка возврата этих вызовов функций.
Но теперь у нас две концепции — рекурсия и стек вызовов — налагаются одна на другую. Это сложно.
Чтобы визуализировать стек вызовов, давайте представим, сто он строится слева направо. Каждый раз при добавлении блока он добавляется на левом конце стека и сдвигает остальные блоки вправо.
Итак, проходя нашу рекурсивную функцию, мы генерируем стек:
Стек вызовов создается внизу гифки. В конце у нас остается 1*2*3*4, что дает 24.
Этот стек состоит из четырех вызовов функции, и ни один из них не запускается, пока функция не вернет 1. Они остаются в стеке, пока не будет добавлено последнее значение, в данном случае — 1.
Это потому, что каждый из первых трех вызовов в стеке включает ссылку на следующий вызов.
Итак, когда num=4, функция возвращает 4*getFactorial(3). Конечно, функция не может вернуть точное значение, пока мы не узнаем значения getFactorial(3). Вот поэтому нам и нужен стек вызовов!
Рекурсия позволяет функции вызываться бесконечное число раз подряд. При этом обновляется стек вызовов. Итоговое значение возвращается после запуска последнего вызова.
Стек вызовов обновляется слева направо, после чего вы можете прочесть все вызовы в порядке их отработки. Самый последний вызов обрабатывается первым, а первый —последним.
Но наша гифка не слишком хороша для показа отношений между вызовами. Поэтому вот еще одна, обновленная версия, показывающая, как вызовы связана между собой инструкцией return:
Пример 2 — разделение строки
Первый пример был математическим, он напоминает задачу из курса алгебры. Факториалы хороши, но есть и другие примеры рекурсии, не связанные с математикой. В этом разделе мы разберем, как можно использовать рекурсию для манипуляций со строкой.
Стоит задача: развернуть строку.
То есть, нужно вернуть строку, где буквы строки, переданной в качестве input, будут записаны в обратном порядке.
Это тоже можно сделать при помощи цикла for, но мы воспользуемся рекурсией.
Давайте подумаем, как нам развернуть слово «cat».
При каждом вызове функции нам нужно отделить первую (или последнюю) букву в строке, а затем вырезать ее из строки. При повторном запуске функции мы опять берем первую (или последнюю) букву.
В конечном итоге стек вызовов позволит нам вернуть буквы в нужном порядке.
Давайте разберем его, как мы делали в первом примере.
Опять-таки, хотя благодаря гифке все кажется простым, если мы хотим действительно понять эти вызовы функции, нам нужно углубиться в итоговую инструкцию return.
Этот пример имеет одно важное отличие от предыдущего: мы осуществляем конкатенацию строки, а не умножение.
Поэтому порядок строк в этой инструкции return имеет большое значение, ведь он определяет порядок дальнейшего объединения.
Поскольку это не серия операций умножения, здесь немного проще понять стек вызовов. Вот как это выглядит:
Когда мы строим стек вызовов так, как показано на гифке, у нас есть определенный порядок вызовов рекурсивной функции и фрагментов строки. Этот порядок очень важен.
Когда мы осуществим все вызовы в стеке, этот порядок позволит нам воссоздать строку в обратном порядке.
СОДЕРЖАНИЕ
Описание
Функции стека вызовов
В зависимости от языка, операционной системы и машинной среды стек вызовов может служить дополнительным целям, в том числе, например:
Локальное хранилище данных
Вместо статической ссылки ссылки на включающие статические кадры могут быть собраны в массив указателей, известный как отображение, которое индексируется для определения местоположения желаемого кадра. Глубина лексической вложенности подпрограммы является известной константой, поэтому размер отображения подпрограммы является фиксированным. Также известно количество содержащихся прицелов, которые необходимо пересечь, индекс в отображении также фиксирован. Обычно отображение процедуры располагается в собственном стековом фрейме, но Burroughs B6500 реализовал такое отображение аппаратно, которое поддерживало до 32 уровней статической вложенности. Записи отображения, обозначающие содержащие области, берутся из соответствующего префикса отображения вызывающего абонента. Внутренняя процедура, которая рекурсивно создает отдельные кадры вызова для каждого вызова. В этом случае все статические ссылки внутренней подпрограммы указывают на один и тот же контекст внешней подпрограммы. Другое состояние возврата Помимо адреса возврата, в некоторых средах могут быть другие состояния машины или программного обеспечения, которые необходимо восстановить при возврате подпрограммы. Сюда могут входить такие вещи, как уровень привилегий, информация об обработке исключений, арифметические режимы и так далее. При необходимости его можно сохранить в стеке вызовов, как и адрес возврата.
Состав
Подобную диаграмму можно нарисовать в любом направлении, если понятно расположение вершины и, следовательно, направление роста стопки. Кроме того, независимо от этого, архитектуры различаются в зависимости от того, растут ли стеки вызовов в сторону более высоких адресов или в сторону более низких адресов. Логика схемы не зависит от выбора адресации.
Фрейм стека наверху стека предназначен для выполняющейся в данный момент процедуры. Кадр стека обычно включает как минимум следующие элементы (в порядке отправки):
Указатели стека и фрейма
Расположение всех других полей в кадре может быть определено либо относительно верха кадра, как отрицательные смещения указателя стека, либо относительно верха нижнего кадра, как положительные смещения указателя кадра. Местоположение самого указателя кадра должно быть определено как отрицательное смещение указателя стека.
Сохранение адреса во фрейме звонящего
В большинстве систем стековый фрейм имеет поле, содержащее предыдущее значение регистра указателя фрейма, значение, которое он имел во время выполнения вызывающей стороны. Например, кадр стека DrawLine будет иметь ячейку памяти, содержащую значение указателя кадра, которое DrawSquare использует (не показано на диаграмме выше). Значение сохраняется при входе в подпрограмму и восстанавливается при возврате. Наличие такого поля в известном месте в фрейме стека позволяет коду последовательно обращаться к каждому фрейму под фреймом выполняющейся в данный момент подпрограммы, а также позволяет подпрограмме легко восстанавливать указатель фрейма на фрейм вызывающей стороны непосредственно перед его возвратом.
Лексически вложенные подпрограммы
Языки программирования, поддерживающие вложенные подпрограммы, также имеют поле в кадре вызова, которое указывает на кадр стека последней активации процедуры, которая наиболее точно инкапсулирует вызываемого, то есть непосредственную область действия вызываемого. Это называется ссылкой доступа или статической ссылкой (поскольку она отслеживает статическое вложение во время динамических и рекурсивных вызовов) и предоставляет подпрограмме (а также любым другим подпрограммам, которые она может вызывать) доступ к локальным данным своих инкапсулирующих подпрограмм при каждом вложении. уровень. Некоторые архитектуры, компиляторы или варианты оптимизации хранят по одной ссылке для каждого уровня включения (а не только непосредственно включающего), так что глубоко вложенные подпрограммы, которые обращаются к поверхностным данным, не должны пересекать несколько ссылок; эту стратегию часто называют «демонстрацией».
Перекрывать
Использовать
Обработка звонков на сайт
Обработка записи подпрограммы
Для архитектур с набором команд, в которых инструкция, используемая для вызова подпрограммы, помещает адрес возврата в регистр, а не помещает его в стек, пролог обычно сохраняет адрес возврата, помещая значение в стек вызовов, хотя, если вызываемый подпрограмма не вызывает никаких других подпрограмм, она может оставить значение в регистре. Точно так же могут быть переданы значения текущего указателя стека и / или указателя кадра.
Если используются указатели кадра, пролог обычно устанавливает новое значение регистра указателя кадра из указателя стека. Затем можно выделить пространство в стеке для локальных переменных путем постепенного изменения указателя стека.
Язык программирования Forth допускает явную намотку стека вызовов (называемого там «стеком возврата»).
Обработка возврата
Когда подпрограмма готова к возврату, она выполняет эпилог, отменяющий шаги пролога. Обычно это восстанавливает сохраненные значения регистров (например, значение указателя фрейма) из фрейма стека, выталкивает весь фрейм стека из стека, изменяя значение указателя стека, и, наконец, выполняет переход к инструкции по адресу возврата. Согласно многим соглашениям о вызовах элементы, извлекаемые из стека эпилогом, включают в себя исходные значения аргументов, и в этом случае обычно нет дополнительных манипуляций со стеком, которые должны выполняться вызывающей стороной. Однако с некоторыми соглашениями о вызовах ответственность за удаление аргументов из стека после возврата лежит на вызывающей стороне.
Размотка
При применении продолжения стек (логически) разматывается, а затем перематывается вместе со стеком продолжения. Это не единственный способ реализовать продолжения; например, используя несколько явных стеков, приложение продолжения может просто активировать свой стек и намотать значение, которое нужно передать. Язык программирования Scheme позволяет выполнять произвольные переходы в определенных точках при «раскручивании» или «перемотке» стека управления при вызове продолжения.
Осмотр
Стек вызовов иногда можно проверить во время работы программы. В зависимости от того, как программа написана и скомпилирована, информация в стеке может использоваться для определения промежуточных значений и трассировки вызовов функций. Это использовалось для генерации детализированных автоматических тестов, а в таких случаях, как Ruby и Smalltalk, для реализации первоклассных продолжений. Например, GNU Debugger (GDB) реализует интерактивную проверку стека вызовов работающей, но приостановленной программы C.
Регулярное взятие выборок из стека вызовов может быть полезно при профилировании производительности программ, потому что, если указатель подпрограммы появляется в данных выборки стека вызовов много раз, это, вероятно, узкое место кода и должно быть проверено на наличие проблем с производительностью.