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?

CodePudding user response：

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

CodePudding user response：

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.