Running CPU-Bound Tasks

Get familiar with CPU-bound synchronous tasks and learn how to use CPU-bound algorithms to solve this issue.

The totalSales() API that we implemented previously was (intentionally) expensive in terms of resources and took a few hundred milliseconds to run. Nonetheless, invoking the totalSales() function didn’t affect the ability of the application to process concurrent incoming requests. Invoking an asynchronous operation always causes the stack to unwind back to the event loop, leaving it free to handle other requests.

But what happens when we run a synchronous task that takes a long time to complete and that never gives the control back to the event loop until it has finished? This kind of task is also known as a CPU-bound task because its main characteristic is that it’s heavy on CPU utilization rather than being heavy on I/O operations.

Let’s immediately work on an example to see how these types of tasks behave in Node.js.

Solving the subset sum problem

Let’s now choose a computationally expensive problem to use as a base for our experiment. A good candidate is the subset sum problem, which decides whether a set (or multiset) of integers contains a non-empty subset that has a sum equal to zero. For example, if we have the [1, 2, –4, 5, –3] set as input, then the subsets satisfying the problem are [1, 2, –3] and [2, –4, 5, –3].

The simplest algorithm is the one that checks every possible combination of subsets of any size and has a computational cost of O(2n)O(2^n), or in other words, it grows exponentially with the size of the input. This means that a set of 20 integers would require up to 1,048,576 combinations to be checked, which should help test our assumptions. For our example, we’re going to consider the following variation of the subset sum problem: given a set of integers, we want to calculate all the possible combinations whose sum is equal to a given arbitrary integer, not just zero.

Now, let’s work to implement the algorithm. First, let’s create a new subsetSum.js named module. We’ll start with creating a SubsetSum named class.

Get hands-on with 1200+ tech skills courses.