Блог

Контекст

Я пишу приложение nodejs, которое включает в себя некоторые сложные вычисления. Базовый алгоритм включает в себя множество итераций и рекурсии. Краткое изложение моего кода может выглядеть примерно так:

 // routes.js - express.js routes

router.get('/api/calculate', (req, res) => {

  const calculator = new Calculator();
  calculator.heavyCalculation();
  console.log('About to send response');
  res.send(calculator.records);

});
 

 // Calculator.js

class Calculator {

  constructor() {
    this.records = [];
  }

  heavyCalculation() {
    console.log('About to perform a heavy calculation');
    const newRecord = this.anotherCalculationMethod();
    this.records.push(newRecord);

    if (records.length < max) {
      this.heavyCalculation();
    }
  };

  anotherCalculationMethod() {
    // more logic and deeper function calls 
    // to methods on this and other class instances
  };

};
 

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

Первый выпуск — Maximum call stack size exceeded error

Даже несмотря на то, что то, что вы видите выше, не является бесконечным циклом, это быстро приводит к Maximum call stack size exceeded ошибке (по очевидным причинам).

Вот кодовое поле, демонстрирующее эту проблему. Нажмите кнопку, чтобы выполнить вызов api, который запускает функцию. Если max он достаточно низкий, мы получаем ожидаемое поведение — heavyCalculation запускаем рекурсивно, заполняем Calculator.records, а затем, когда лимит достигнут, полные результаты отправляются обратно на интерфейс. Журналы выглядят так:

 About to perform a heavy calculation
About to perform a heavy calculation
About to perform a heavy calculation
// repeats max times
About to send response
 

But if you set the max variable to be high enough, you’ll exceed the stack limit, and the app crashes.

Trying to solve the issue with process.nextTick or setImmediate

I read the article The Call Stack is Not an Infinite Resource — How to Avoid a Stack Overflow in JavaScript, and opted to try some methods there. I liked the idea of using process.nextTick , as it would help dicretize each step in the recursive loop of heavyCalculation . Adjusting the method, I tried this:

   heavyCalculation() {
    // ...

    if (records.length < max) {
      process.nexTick(() => {
        this.heavyCalculation();
      });
    }
  };
 

Это решает проблему превышения максимального размера стека вызовов, но создает еще одну проблему. Вместо того, чтобы выполнять heavyCalculation рекурсивно, а затем ждать, пока эта рекурсия не достигнет предела, она запускает функцию один раз, затем отправляет ответ на внешний интерфейс, records содержащий только одну запись, а затем продолжает рекурсию. То же самое происходит при обертывании вызова setImmediate , т. Е. setImmediate(this.heavyCalculation()) . Журналы выглядят так:

 About to perform a heavy calculation
About to send response
About to perform a heavy calculation
About to perform a heavy calculation
About to perform a heavy calculation
// repeats max - 1 times
 

Codesandbox, демонстрирующий проблему

Как и прежде, нажмите кнопку, чтобы выполнить вызов api, который запускает функцию, и вы сможете увидеть, что происходит в терминале codesandbox nodejs.

Как я могу правильно управлять циклом событий таким образом, чтобы моя рекурсивная функция не создавала переполнение стека, а срабатывала в правильном порядке? Могу ли я использовать process.nextTick ? Как я могу отделить стек вызовов для каждой итерации рекурсивной функции, но все равно дождаться конца цикла, прежде чем возвращать ответ?

Бонусный вопрос:

То, что я опубликовал, очевидно, является упрощенной версией моего приложения. На самом деле, anotherCalculationMethod это сама по себе сложная функция со своим собственным глубоким стеком вызовов. Он перебирает серию массивов, которые также могут вырасти до довольно больших (порядка тысяч). Допустим , он повторяется Calculator.records и Calculator.records увеличивается до нескольких тысяч элементов. В рамках одной итерации heavyCalculation , как я могу применить ту же логику потока, которая могла бы решить главный вопрос, чтобы избежать той же проблемы, возникающей в такой подпрограмме, как anotherCalculationMethod ?

Чтобы ответить на ваш вопрос относительно «как дождаться следующего тика»: вы можете передать функцию обратного вызова функции расчета и завернуть ее в обещание, которое вы затем можете ожидать, например:

 heavyCalculation(cb) {
        console.log("About to perform a heavy calculation");
        const newRecord = this.anotherCalculationMethod();
        this.records.push(newRecord);

        if (this.records.length < max) {            
            process.nextTick(() => {
               this.heavyCalculation(done);
            });
        } else {
            cb(this.records);
        }
    }
 

В обработчике вашего запроса вы можете назвать его так:

 const result = await new Promise((resolve, reject) => {
    calculator.heavyCalculation((result) => {
        resolve(result);
    });
});
console.log("about to send calculator.records, which has length:", result);
res.json(result);
 

Но:
Вы должны иметь в виду, что, хотя использование process.nextTick решает проблему стекового потока, оно имеет свою цену. Т. Е. вы блокируете цикл событий от перехода к следующему этапу, и это означает, например, что узел не сможет обслуживать другие входящие запросы на ваш сервер. Эти запросы и фактически все другие обратные вызовы, которые готовы к отправке в стек вызовов, должны подождать, пока ваш расчет не будет завершен.

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

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

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

Для меня while здесь гораздо больше смысла в цикле.

 heavyCalculation() {
  while (this.records.length < max) {
     console.log('About to perform a heavy calculation');
     const newRecord = this.anotherCalculationMethod();
     this.records.push(newRecord);
  }
};
 

Обновить

В комментарии спрашивалось, как это сделать process.nextTick . Как указывает eol, способ справиться с этим-использовать обещания или синтаксический сахар async / await . Как только вы добавите асинхронную обработку, весь код, к которому она прикасается, также должен быть асинхронным. Такова природа этого зверя, и об этом, по крайней мере, говорилось в упомянутой статье.

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

Но есть и другие случаи, когда текущая итерация может добавить работу в вашу очередь, и вы хотите продолжать, пока больше не останется работы. Подумайте о создании веб-сайта с помощью пауков. Вы хотите перейти по всем соответствующим ссылкам, и по всем ссылкам с этих страниц, и по всем ссылкам с них, по мере необходимости, но загружать каждую страницу только один раз, независимо от того, сколько на нее ссылок. Это может использовать довольно похожий процесс, просто управляя очередью тех, кого нужно посетить, и набором тех, кого уже посетили. Вот пример с фиктивной заменой fetch и чрезвычайно наивной моделью, в которой используются все ссылки. (Я также пропускаю очистку HTML; давайте не будем туда заходить!)

 const spider = async (id) => {
  const queue = [id], 
        processed = []
  const items = {}
  while (queue .length > 0) {
    const id = queue .pop ()
    const item = await fetch (`http://dummy.url/item/${id}`)
    items [id] = item
    processed .push (id)
    item .links .forEach (id => processed .includes (id) || queue .push (id))
  }
  return items
}

spider (1)
  .then (console .log)
  .catch (console .warn) 

 .as-console-wrapper {max-height: 100% !important; top: 0} 

 <script>/* Dummy version of `fetch` */ const fetch = ((data) => (url, t = url .slice (url.lastIndexOf('/')   1), item = data .find (({id}) => id == t)) => new Promise ((res, rej) => item ? res (item) :rej (`Item ${t} not found`)))([
  /* using this data */
  {id: 1, name: 'foo', links: [2, 3]}, 
  {id: 2, name: 'bar', links: [4]}, 
  {id: 3, name: 'baz', links: []}, 
  {id: 4, name: 'qux', links: [5]}, 
  {id: 5, name: 'corge', links: [6]}, 
  {id: 6, name: 'grault', links: [1, 2]}, 
  {id: 8, name: 'waldo', links: [3]}
])</script> 

При этом извлекаются все элементы, которые можно найти рекурсивно связанными, начиная с id of 1 . (Если бы мы начали с id of 8 , мы бы получали только 8 и 3 , но с 1 помощью мы получаем все наши жестко закодированные данные, за исключением 8 .)

Важно отметить, что вызовы fetch асинхронны, и поэтому spider сами по себе асинхронны, но мы можем работать в основном синхронно внутри, используя await