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

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

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

 RangeError: Maximum call stack size exceeded. 

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

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

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

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

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

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 байтам, а размер коллстэка — чуть меньше одного мегабайта.

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

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

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

let i = 0;

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

  func();
};

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

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

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

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

Итоги:

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

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

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

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

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