Стек вызовов - это не бесконечный ресурс - как избежать переполнения стека в JavaScript

Стек вызовов - это не бесконечный ресурс - как избежать переполнения стека в JavaScript

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

Стек вызовов - это не бесконечный ресурс. Это особенно верно при выполнении глубокой рекурсии. Вызовы функций внутри функций помещаются в стек вызовов выше, что означает, что каждый рекурсивный вызов находится в стеке вызовов, ожидая своего выполнения.

Размер стека вызовов не фиксирован в Javascript, но он не велик. Давайте посмотрим на тривиальный пример:

let ct = 0;
const MAX = 100_000
const recurse = () => {
  if (++ct > MAX) return
  recurse()
}
try {
  recurse()
} catch (e) {
  console.error({ ct, e })
}

Если я запустил это в Node.js, я получу следующий результат:

{
  ct: 15711,
  e: RangeError: Maximum call stack size exceeded
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:4:17)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
      at recurse (/home/jlowery2663/projects/stacksmash/overflow.js:6:3)
}

На 15711-й итерации происходит переполнение стека. Ниже приведены некоторые уловки, чтобы этого не произошло.

setTimeout

Функция setTimeout планирует вызов функции, который будет обрабатываться циклом событий в некоторый будущий момент времени. Истинной рекурсии в этом случае не происходит: внутренняя «рекурсивная» функция будет выполняться, но к тому времени внешняя функция вернется и, следовательно, больше не будет находиться в очереди сообщений о событиях (той, которая сообщает циклу событий, что делать, и когда это делать).

Метод setTimeout принимает два параметра: функцию и время задержки (в миллисекундах). Задержка может составлять ноль миллисекунд, поэтому выполнение функции может происходить «немедленно». Давай попробуем:

let ct = 0;
const MAX = 100_000
const recurse = (cb) => {
  if (++ct > MAX) {
    return cb(ct)
  }
  setTimeout(() => recurse(cb), 0)
}
try {
  const then = process.hrtime.bigint();
recurse((ct) => {
    const now = process.hrtime.bigint();
    const nanos = now - then
    const runtime = Number(nanos) / 1_000_000_000
    ct--
    console.log({ ct, runtime });
  })
} catch (e) {
  console.error({ ct, e })
}

Эта программа выводит время выполнения и количество итераций. Результаты:

{ct: 100000, runtime: 144.47516928 }

Таким образом, это позволяет избежать переполнения стека вызовов, но как-то медленно, не так ли?

setImmediate

Несмотря на то, что setTimeout может принимать 0 мс в качестве второго аргумента, это не так быстро, как вызов setImmediate:

let ct = 0;
const MAX = 100_000
const recurse = (cb) => {
  if (++ct > MAX) {
    return cb(ct)
  }
  setImmediate(() => recurse(cb))
}
try {
  const then = process.hrtime.bigint();
recurse((ct) => {
    const now = process.hrtime.bigint();
    const nanos = now - then
    const runtime = Number(nanos) / 1_000_000_000
    ct--
    console.log({ ct, runtime });
  })
} catch (e) {
  console.error({ ct, e })
}

Время выполнения этой программы намного, намного быстрее, чем у предыдущей:

{ ct: 100000, runtime: 0.295789227 }

Доля секунды вместо 144+! Почему?

Функция, выполняемая с помощью setImmediate, не запланирована, как с setTimeout. Вместо этого он выполняется сразу после выполнения всех обработчиков ввода / вывода. Обработка цикла событий в JavaScript хорошо объяснена в другом месте, например, здесь, и этот пост посвящен тому, как избежать переполнения стека вызовов.

nextTick

При выполнении в среде Node.js есть еще один доступный ресурс, позволяющий избежать переполнения стека: process.nextTick (). Объект process является глобальным, как и window в браузере. Метод nextTick выполняет функцию при первой возможности, минуя очередь сообщений о событиях.

let ct = 0;
const MAX = 100_000
const recurse = (cb) => {
  if (++ct > MAX) {
    return cb(ct)
  }
  process.nextTick(() => recurse(cb))
}
try {
  const then = process.hrtime.bigint();
recurse((ct) => {
    const now = process.hrtime.bigint();
    const nanos = now - then
    const runtime = Number(nanos) / 1_000_000_000
    ct--
    console.log({ ct, runtime });
  })
} catch (e) {
  console.error({ ct, e })
}

Результат:

{ ct: 100000, runtime: 0.109725787 }

Таким образом, nextTick на 60–70% быстрее, чем setImmediate для этого тривиального примера кода.

зацикливание

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

Однако иногда рекурсия может быть глубоко вложенной. Скажем, функция A вызывает функцию B вызывает функцию C, которая может снова вызвать функцию B или функцию A. Теперь у вас есть рекурсия A- ›B-› C- ›B | A, и преобразование этого типа рекурсии в петлю может быть не так просто.

Вместо прямого вызова функций основной цикл может вызывать функцию через переменную. Переменная функции устанавливается при каждом вызове функции, и ответственность за вызов каждой функции ложится на конструкцию цикла:

let ct = 0;
const MAX = 100_000
const A = () => {
  fp = B;
}
const B = () => {
  fp = A;
}
let fp = B;
const then = process.hrtime.bigint();
for (; ;) {
if (++ct > MAX) {
    const now = process.hrtime.bigint();
    const nanos = now - then;
const runtime = Number(nanos) / 1_000_000_000
    ct--
    console.log({ ct, runtime });
    break;
  }
  fp()
  continue;
}

В этом цикле нет функций, вызывающих функции, но каждая функция должна знать и контролировать, какая функция будет выполняться следующей, с помощью переменной функции fp. Это дает самые быстрые результаты:

{ ct: 100000, runtime: 0.015974012 }

Итак, у вас есть четыре способа избежать страшного переполнения стека.