Awaiting the end of a process.nextTick loop

Question

Context

I am writing a nodejs application that involves some heavy calculations. The underlying algorithm involves a lot of iteration and recursion. A quick summary of my code might look like this:

// 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
  };

};

In most cases I would expect the max value to never be more than 9,000 or 10,000, and in some cases, it may be far less. As I said, this is a calculation heavy application, and I am trying to find the right approach to performing the calculations in a way that will not crash the machine the app is running on.

First issue - `Maximum call stack size exceeded error`

Even though what you see above is not an infinite loop, it quickly hits the Maximum call stack size exceeded error (for obvious reasons).

Here is a codesandbox demonstrating that issue. Click the button to make the api call which runs the function. If max is low enough, we get the expected behavior - heavyCalculation runs recursively, populates Calculator.records, and then when the limit is hit, the full results gets sent back to the front end. The logs look like this:

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();
      });
    }
  };

This solves the max call stack size exceeded issue, but creates another problem. Rather than run heavyCalculation recursively, and then waiting until that recursion hits the limit, it runs the function once, then sends the response to the front end with records containing only a single entry, then continues the recursion. The same occurs when wrapping the call in setImmediate, i.e. setImmediate(this.heavyCalculation()). The logs look like this:

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 demonstrating the issue

As before, click the button to make the api call which fires the function, and you can see what's happening in the codesandbox nodejs terminal.

How can I properly manage the event loop such that my recursive function does not create a stack overflow, but fires in the proper order? Can I leverage process.nextTick? How can I separate the call stack for each iteration of the recursive function, but still wait for the end of the loop before returning the response?

Bonus question:

What I've posted is obviously a simplified version of my app. In reality, anotherCalculationMethod is in and of itself a complicated function with its own deep call stack. It iterates over a series of arrays, which may also grow to be quite large (on the order of thousands). Say it iterates over Calculator.records, and Calculator.records grows to be several thousand items large. Within a single iteration of heavyCalculation, how can I apply the same flow logic that might solve the main question to avoid the same issue happening within a subroutine like anotherCalculationMethod?

user_1243641 · Answer

I know this is only dummy code, but from what I see, there is simply no reason for the recursion. I am a big fan of recursion, even in JS. But as you're seeing, it has real limitations in the language.

Also, recursion is closely tied to functional programming with its insistence on immutable data and lack of side-effects. Here your recursive function is not returning anything -- a major warning sign. And it's only job seems to be to call another method and use the result to add to this.records.

To me, a while loop makes much more sense here.

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

Update

A comment asked how to do this with process.nextTick. As eol points out, the way to deal with that is to use Promises or the syntactic sugar of async/await. Once you mix asynchronous processing in, all code it touches will also need to be asynchronous. That's just the nature of the beast, and it was at least touched on in the article mentioned.

And it looks as though your queue is controlled simply by a max size value, in which case, what eol suggested would work fine.

But there are other cases where the current iteration might add work to your queue, and you want to continue until there is no more work to do. Think of spidering a website. You want to follow all the relevant links, and all the links from those pages, and all the links from those, as deep as necessary, but to load each page only once, regardless of how many links there are to it. That can use a fairly similar process, just managing a queue of those to visit and a set of those already visited. Here's an example, with a dummy replacement for fetch and an extremely naive model where all links are followed. (I also skip HTML scraping; let's not go there!)

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}

This fetches all the items that can be found recursively linked starting with id of 1. (If we started with id of 8, we would only get 8 and 3, but with 1 we get all our hard-coded data except for 8.)

The important point to note is that the calls to fetch are asynchronous, and so spider itself is asynchronous, but we can work in a mostly synchronous manner internally, using await

user_3761628 · Answer

To answer your question regarding "how to wait for the next tick": You can pass a callback-function to the calculation function and wrap it in a promise, which you then can await, e.g.:

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);
        }
    }

In your request handler you can call it like this:

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);

But: You have to keep in mind that although the use of process.nextTick solves the stackoverflow problem, it comes with a price. I.e. you block the event-loop from moving on to the next phase and that means, for example, that node will not be able to serve other incoming requests to your server. Those requests and actually all other callbacks that are ready to be pushed to the call-stack have to wait until your calculation has finished.

You can e.g. use setTimeout as an alternative in order to solve this, but if you have to rely on such heavy calculations, you might be better off with worker-threads and moving those calculations there.