JavaScript: Стек вызовов и магия его размера

Привет, Хабровчане!

Большинство разработчиков, которые использовали рекурсию для решения своих задач, видели такую ошибку:

 RangeError: Maximum call stack size exceeded. 

Но не каждый разработчик задумывался о том, а что означает "размер стэка вызовов" и каков же этот размер? А в чем его измерять?

Думаю, те, кто работают с языками, напрямую работающими с памятью, смогут легко ответить на этот вопрос, а вот типичный фронтэнд разработчик скорее всего задает себе подобные вопросы впервые. Что-ж, попробуем разобраться!

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

О чем ты вообще, автор?

Для статьи важно понимание таких понятий как Execution Stack, Execution Context. Если вы не знаете, что это такое, то советую об этом почитать. На данном ресурсе уже было достаточно хороших статей на эту тему. Пример - https://habr.com/ru/company/ruvds/blog/422089/

Когда возникает эта ошибка?

Разберем на простом примере - функция, которая рекурсивно вызывает сама себя.

const func = () => {
    func();
}

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

А что если подглядеть, сколько же раз выполнилась функция перед тем, как возникла ошибка?

На данном этапе код запускается в Chrome DevTools последней версии на март 2021. Результат будет различаться в разных браузерах. В дальнейшем в статье я упомяну об этом.

Для эксперимента будем использовать вот такой код:

let i = 0;

const func = () => {
  i++;

  func();
};

try {
  func();
} catch (e) {
  // Словили ошибку переполнения стэка и вывели значение счетчика в консоль
  console.log(i);
}

Результатом вывода в консоль стало число в 13914. Делаем вывод, что перед тем, как переполнить стэк, наша функция вызвалась почти 14 тысяч раз.

Магия начинается тогда, когда мы начинаем играться с этим кодом. Допустим, изменим его вот таким образом:

let i = 0;

const func = () => {
  let someVariable = i + 1;
  i++;

  func();
};

try {
  func();
} catch (e) {
  console.log(i);
}

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

Почему же так? Что изменилось? Как понять, посмотрев на функцию, сколько раз она может выполниться рекурсивно?!

Магия раскрыта

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

let i = 0;

const func = () => {
  let a = i + 1;
  let b = a + 1;
  let c = b + 1;
  let d = c + 1;
  let e = d + 1;
  i++;

  func();
};

try {
  func();
} catch (e) {
  console.log(i);
}

По этой логике, значение счетчика должно стать еще меньше. Выдыхая, видим вывод - 8945. Ага, оно стало еще меньше. Значит, мы на правильном пути. Хочу привести небольшую аналогию, чтобы даже самым маленьким стало понятно.

Execution Stack (Call Stack) - это емкость с водой. Изначально она пустая. Так получилось, что эта емкость с водой стоит прямо на электрической проводке. Как только емкость переполнится, вода проливается на провода, и мы видим ошибку в консоли. При каждом новом рекурсивном вызове функции в стэк падает капелька воды. Само собой, чем капелька воды крупнее, тем быстрее наполнится стэк.

Емкости бывают разные по размеру. И размер емкости в данном примере - это размер коллстэка. А точнее - количество байт, которое он максимально может в себе удержать. Как гласит статья про Call Stack (Execution Stack), которую я приложил в начале, на каждый вызов функции создается Execution Context - контекст вызова функции (не путать с this). И упрощая, в нем, помимо разных "подкапотных" штук, содержатся все переменные, которые мы объявили внутри функции. Как Execution Context, так и каждая переменная внутри него имеют определенный размер, который они занимают в памяти. Сложив эти два размера мы и получим "размер" капли, которая капает в кувшин при каждом рекурсивном вызове функции.

У нас уже достаточно много данных. Может быть, поэкспериментируем еще? А давайте попробуем вычислить, какой размер коллстэка в движке, который использует Chrome?

Математика все-таки пригодилась

Как мы выяснили, у нас есть две неизвестные, которые составляют размер функции (капельки, которая падает в емкость). Это размер самого Execution Stack, а так же сумма размеров всех переменных внутри функции. Назовем первую N, а вторую K. Сам же неизвестный размер коллстэка обозначим как X.

В итоге - количество байт, которое занимает функция (в упрощенном виде) будет:

SizeOfVar в данном случае - количество байт, которые занимает переменная в памяти.

Учитывая, что мы знаем количество вызовов первой функции, в теле которой не объявляются переменные, размер коллстэка можно выразить как:

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

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

Выглядит неплохо. У нас тут две неизвестные переменные - N и SizeOfVar. Если N мы не можем откуда-то узнать, то что насчет SizeOfVar? Заметим, что во всех функциях, которые фигурировали выше, переменные хранили значение с типом "number", а значит, нужно просто узнать, сколько же байт в памяти занимает одна такая переменная.

С помощью великого гугла получаем ответ - "Числа в JavaScript представлены 64-битными значениями с плавающей запятой. В байте 8 бит, в результате каждое число занимает 64/8 = 8 байт." Вот она - последняя неизвестная. 8 байт. Подставляем ее в наше уравнение и считаем, чем равно N.

Упрощаем:

Если выразить отсюда N, то получим ответ: N равно приблизительно 72. В данном случае 72 байтам.

Теперь, подставив N = 72 в самое первое уравнение, получим, что размер коллстэка в Chrome равен... 1002128 байтов. Это почти один мегабайт. Не так уж и много, согласитесь.

Мы получили какое-то число, но как убедиться, что наши расчеты верны и число правильное? А давайте попробуем с помощью этого числа спрогнозировать, сколько раз сможет выполниться функция, внутри которой будет объявлено 7 переменных типа 'number'. 

Считаем: Ага, каждая функция будет занимать (72 + 7 * 8) байт, это 128. Разделим 1002128 на 128 и получим число... 7829! Согласно нашим расчетам, такая функция сможет рекурсивно вызваться именно 7829 раз! Идем проверять это в реальном бою...

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

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

Отличная работа!

Важное примечание

Размер стэка разнится от браузера к браузеру. Возьмем простейшую функцию из начала статьи. Выполнив ее в Сафари получим совершенно другую цифру. Целых 45606 вызовов. Функция с пятью переменными внутри выполнилась бы 39905 раз. В NodeJS числа очень близки к Chrome по понятным причинам. Любопытный читатель может проверить это самостоятельно на своем любимом движке JavaScript. 

А что с непримитивами?

Если с числами все вроде бы понятно, то что насчет типа данных Object? 

let i = 0;

const func = () => {
  const a = {
    key: i + 1,
  };
  i++;

  func();
};

try {
  func();
} catch (e) {
  console.log(i);
}

Простейший пример на ваших глазах. Такая функция сможет рекурсивно вызваться 12516. Это практически столько же, сколько и функция с одной переменной внутри. Тут в дело вступает механизм хранения и передачи объектов в JS'е - по ссылке. Думаю, большинство уже знают об этом.

А что с этим? А как поведет себя вот это? А что с *?

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

Итоги:

• Количество рекурсивных вызовов функции до переполнения стэка зависит от самих функций.

• Размер стэка измеряется в байтах.

• Чем "тяжелее" функция, тем меньше раз она может быть вызвана рекурсивно.

• Размер стэка в разных движках различается.

Вопрос особо любознательным: А сколько переменных типа "number" должно быть объявлено в функции, чтобы она могла выполниться рекурсивно всего два раза, после чего стэк переполнится?

Let's block ads! (Why?)