As we discussed in Chapter 1, About Node.js we’ll be using an inefficient algorithm to calculate Fibonacci numbers to explore how to mitigate performance problems, and along the way, we’ll learn how to build a simple REST service to offload computation to the backend server.
The Fibonacci numbers are the following integer sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Each Fibonacci number is the sum of the previous two numbers in the sequence. This sequence was discovered in 1202 by Leonardo of Pisa, who was also known as Fibonacci. One method to calculate entries in the Fibonacci sequence is using the recursive algorithm, which we discussed in Chapter 1, About Node.js. We will create an Express application that uses the Fibonacci implementation and along the way, we will get a better understanding of Express applications, as well as explore several methods to mitigate performance problems in computationally intensive algorithms.
Let’s start with the blank application we created in the previous step. We named that application Fibonacci for a reason—we were thinking ahead!
In app.js, make the following changes to the top portion of the file:
const express = require(‘express’);
const hbs = require(‘hbs’);
const path = require(‘path’);
const favicon = require(‘serve-favicon’);
const logger = require(‘morgan’);
const cookieParser = require(‘cookie-parser’);
const bodyParser = require(‘body-parser’);
const indexRouter = require(‘./routes/index’);
const fibonacciRouter = require(‘./routes/fibonacci’);
const app = express();
// view engine setup
app.set(‘views’, path.join( dirname, ‘views’));
app.set(‘view engine’, ‘hbs’);
hbs.registerPartials(path.join( dirname, ‘partials’));
app.use(logger(‘dev’));
app.use(bodyParser.json());
app.use(bodyParser.urlencoded({ extended: false }));
app.use(cookieParser());
app.use(express.static(path.join( dirname, ‘public’)));
app.use(‘/’, indexRouter);
app.use(‘/fibonacci’, fibonacciRouter);
Most of this is what express-generator gave us. The var statements have been changed to const for that little teensy bit of extra comfort. We explicitly imported the hbs module so that we could do some configuration. We also imported a router module for Fibonacci, which we’ll see in a minute.
For the Fibonacci application, we don’t need to support users and so we have deleted the routing module. The routes/fibonacci.js module, which we’ll show next, serves to query a number for which we’ll calculate the Fibonacci number.
In the top-level directory, create a file, math.js, containing the following extremely simplistic Fibonacci implementation:
exports.fibonacci = function(n) {
if (n === 0) return 0;
else if (n === 1 || n === 2) return 1;
else return exports.fibonacci(n-1) + exports.fibonacci(n-2);
};
In the views directory, look at the file named layout.hbs, which was created by express-generator:
<!DOCTYPE html>
<html>
<head>
<title>{{title}}</title>
<link rel=’stylesheet’ href=’/stylesheets/style.css’ />
</head>
<body>
{{{body}}}
</body>
</html>
This file contains the structure that we’ll use for the HTML pages. Going by the Handlebars syntax, we can see that {{title}} appears within the HTML title tag. This means that when we call res.render, we should supply a title attribute. The {{{body}}} tag is where the view template content lands. Change views/index.hbs to just contain the following:
<h1>{{title}}</h1>
{{> navbar}}
<p>Welcome to {{title}}</p>
This serves as the front page of our application. It will be inserted in place of {{{body}}} in views/layout.hbs. The marker, {{> navbar}}, refers to a partially named navbar object. Earlier, we configured a directory named partials to hold partials. Now, let’s create a file, partials/navbar.html, containing the following:
<div class=’navbar’>
<p><a href=’/’>home</a> | <a href=’/fibonacci’>Fibonacci’s</a></p>
</div>
This will serve as a navigation bar that’s included on every page. Create a file, views/fibonacci.hbs, containing the following code:
<h1>{{title}}</h1>
{{> navbar}}
{{#if fiboval}}
<p>Fibonacci for {{fibonum}} is {{fiboval}}</p>
<hr/>
{{/if}}
<p>Enter a number to see its’ Fibonacci number</p>
<form name=’fibonacci’ action=’/fibonacci’ method=’get’>
<input type=’text’ name=’fibonum’ />
<input type=’submit’ value=’Submit’ />
</form>
If fiboval is set, this renders a message that for a given number (fibonum), we have calculated the corresponding Fibonacci number. There is also an HTML form that we can use to enter a fibonum value.
Because it is a GET form, when the user clicks on the Submit button, the browser will issue an HTTP GET method to the /fibonacci URL. What distinguishes one GET method on /fibonacci from another is whether the URL contains a query parameter named fibonum. When the user first enters the page, there is no fibonum number and so there is nothing to calculate. After the user has entered a number and clicked on Submit, there is a fibonum number and so something to calculate.
In routes/index.js, change the router function to the following:
router.get(‘/’, function(req, res, next) {
res.render(‘index’, {
title: “Welcome to the Fibonacci Calculator”
});
});
The anonymous object passed to res.render contains the data values we provide to the layout and view templates. We’re now passing a new welcome message.
Then, finally, in the routes directory, create a file named fibonacci.js, containing the following code:
const express = require(‘express’);
const router = express.Router();
const math = require(‘../math’);
router.get(‘/’, function(req, res, next) {
if (req.query.fibonum) {
// Calculate directly in this server
res.render(‘fibonacci’, {
title: “Calculate Fibonacci numbers”,
fibonum: req.query.fibonum,
fiboval: math.fibonacci(req.query.fibonum)
});
} else {
res.render(‘fibonacci’, {
title: “Calculate Fibonacci numbers”,
fiboval: undefined
});
}
});
module.exports = router;
This route handler says it matches the / route. However, there is a route handler in index.js that matches the same route. We haven’t made a mistake, however. The router object created by this module becomes fibonacciRouter when it lands in app.js. Refer back to app.js and you will see that fibonacciRouter is mounted on /fibonacci. The rule is that the actual URL path matched by a router function is the path that the router is mounted on plus the path given for the router function. In this case, that is /fibonacci plus /, and for a URL, that equates to /fibonacci.
The handler checks for the existence of req.query.fibonum. Express automatically parses the HTTP request URL and any query parameters will land in req.query.
Therefore, this will trigger a URL such as /fibonacci?fibonum=5.
If this value is present, then we call res.render(‘fibonacci’) with data including fibonum, the number for which we want its Fibonacci number, and fiboval, the corresponding Fibonacci number. Otherwise, we pass undefined for fiboval. If you refer back to the template, if fiboval is not set, then the user only sees the form to enter a fibonum number. Otherwise, if fiboval is set, both fibonum and fiboval are displayed.
The package.json file is already set up, so we can use npm start to run the script and always have debugging messages enabled. Now, we’re ready to do this:
$ npm start
> fibonacci@0.0.0 start /Users/david/chap04/fibonacci
> DEBUG=fibonacci:* node ./bin/www
fibonacci:server Listening on port 3000 +0ms
As this suggests, you can visit http://localhost:3000/ and see what we have:
This page is rendered from the views/index.hbs template. Simply click on the Fibonacci’s link to go to the next page, which is, of course, rendered from the views/fibonacci.hbs template. On that page, you’ll be able to enter a number, click on the Submit button, and get an answer (hint—pick a number below 40 if you want your answer in a reasonable amount of time):
We asked you to enter a number less than 40. Go ahead and enter a larger number, such as 50, but go take a coffee break because this is going to take a while to calculate. Or, proceed on to reading the next section, where we will start to discuss the use of computationally intensive code.
1. Computationally intensive code and the Node.js event loop
This Fibonacci example is purposely inefficient to demonstrate an important consideration for your applications. What happens to the Node.js event loop when long computations are run? To see the effect, open two browser windows, each viewing the Fibonacci page. In one, enter the number 55 or greater, and in the other, enter 10. Note how the second window freezes, and if you leave it running long enough, the answer will eventually pop up in both windows. What’s happening in the Node.js event loop is blocked from processing events because the Fibonacci algorithm is running and does not ever yield to the event loop.
Since Node.js has a single execution thread, processing requests depends on request handlers quickly returning to the event loop. Normally, the asynchronous coding style ensures that the event loop executes regularly.
This is true even for requests that load data from a server halfway around the globe because the asynchronous request is non-blocking and control is quickly returned to the event loop. The naïve Fibonacci function we chose doesn’t fit into this model because it’s a long-running blocking operation. This type of event handler prevents the system from processing requests and stops Node.js from doing what it’s meant to do—namely, to be a blisteringly fast web server.
In this case, the long-response-time problem is obvious. The response time to calculate a Fibonacci number quickly escalates to the point where you can take a vacation to Tibet, become a Lama, and perhaps get reincarnated as a llama in Peru in the time it takes to respond! However, it’s also possible to create a long-response-time problem without it being as obvious as this one. Of the zillion-and-one asynchronous operations in a large web service, which one is both blocking and takes a long time to compute the result? Any blocking operations like this will cause a negative effect on the server throughput.
To see this more clearly, create a file named fibotimes.js, containing the following code:
const math = require(‘./math’);
for (var num = 1; num < 80; num++) {
let now = new Date().toISOString();
console.log(`${now} Fibonacci for ${num} = ${math.fibonacci(num)}`);
}
Now, run it. You will get the following output:
$ node fibotimes.js
2020-01-06T00:26:36.092Z Fibonacci for 1 = 1
2020-01-06T00:26:36.105Z Fibonacci for 2 = 1
2020-01-06T00:26:36.105Z Fibonacci for 3 = 2
2020-01-06T00:26:36.105Z Fibonacci for 4 = 3
2020-01-06T00:26:36.105Z Fibonacci for 5 = 5
…
2020-01-06T00:26:36.106Z Fibonacci for 10 = 55
2020-01-06T00:26:36.106Z Fibonacci for 11 = 89
2020-01-06T00:26:36.106Z Fibonacci for 12 = 144
2020-01-06T00:26:36.106Z Fibonacci for 13 = 233
2020-01-06T00:26:36.106Z Fibonacci for 14 = 377
…
2020-01-06T00:26:37.895Z Fibonacci for 40 = 102334155
2020-01-06T00:26:38.994Z Fibonacci for 41 = 165580141
2020-01-06T00:26:40.792Z Fibonacci for 42 = 267914296
2020-01-06T00:26:43.699Z Fibonacci for 43 = 433494437
2020-01-06T00:26:48.985Z Fibonacci for 44 = 701408733
…
2020-01-06T00:33:45.968Z Fibonacci for 51 = 20365011074
2020-01-06T00:38:12.184Z Fibonacci for 52 = 32951280099
^C
This quickly calculates the first 40 or so members of the Fibonacci sequence, but after the 40th member, it starts taking a couple of seconds per result and quickly degrades from there. It is untenable to execute code of this sort on a single-threaded system that relies on a quick return to the event loop. A web service containing code like this would give a poor performance to the users.
There are two general ways to solve this problem in Node.js:
- Algorithmic refactoring: Perhaps, like the Fibonacci function we chose, one of your algorithms is suboptimal and can be rewritten to be faster. Or, if it is not faster, it can be split into callbacks dispatched through the event loop. We’ll look at one method for this in a moment.
- Creating a backend service: Can you imagine a backend server that is dedicated to calculating Fibonacci numbers? Okay, maybe not, but it’s quite common to implement backend servers to offload work from frontend servers, and we will implement a backend Fibonacci server at the end of this chapter.
With that in mind, let’s examine these possibilities.
1.1. Algorithmic refactoring
To prove that we have an artificial problem on our hands, here is a much more efficient Fibonacci function:
exports.fibonacciLoop = function(n) {
var fibos = [];
fibos[0] = 0;
fibos[1] = 1;
fibos[2] = 1;
for (let i = 3; i <= n; i++) {
fibos[i] = fibos[i-2] + fibos[i-1];
}
return fibos[n];
}
If we substitute a call to math.fibonacciLoop in place of math.fibonacci, the fibotimes program runs much faster. Even this isn’t the most efficient implementation; for example, a simple, prewired lookup table is much faster at the cost of some memory.
Edit fibotimes.js as follows and rerun the script. The numbers will fly by so fast that your head will spin:
for (var num = 1; num < 8000; num++) {
let now = new Date().toISOString();
console.log(`${now} Fibonacci for ${num} =
${math.fibonacciLoop(num)}`);
}
Sometimes, your performance problems will be this easy to optimize, but other times, they won’t.
The discussion here isn’t about optimizing mathematics libraries but about dealing with inefficient algorithms that affect event throughput in a Node.js server. For that reason, we will stick with the inefficient Fibonacci implementation.
It is possible to divide the calculation into chunks and then dispatch the computation of those chunks through the event loop. Add the following code to math.js:
module.exports.fibonacciAsync = function(n, done) {
if (n === 0) done(undefined, 0);
else if (n === 1 || n === 2) done(undefined, 1); else {
setImmediate(() => {
exports.fibonacciAsync(n-1, (err, val1) => {
if (err) done(err);
else setImmediate(() => {
exports.fibonacciAsync(n-2, (err, val2) => {
if (err) done(err);
else done(undefined, val1+val2);
});
}
};
});
});
});
This converts the fibonacci function from a synchronous function into a traditional callback-oriented asynchronous function. We’re using setImmediate at each stage of the calculation to ensure that the event loop executes regularly and that the server can easily handle other requests while churning away on a calculation. It does nothing to reduce the computation required; this is still the inefficient Fibonacci algorithm. All we’ve done is spread the computation through the event loop.
In fibotimes.js, we can use the following:
const math = require(‘./math’);
(async () => {
for (var num = 1; num < 8000; num++) {
await new Promise((resolve, reject) => {
math.fibonacciAsync(num, (err, fibo) => {
if (err) reject(err);
else {
let now = new Date().toISOString();
console.log(‘${now} Fibonacci for ${num} = ${fibo}’);
resolve();
}
})
})
}
})().catch(err => { console.error(err); });
We’re back to an inefficient algorithm, but one where calculations are distributed through the event loop. Running this version of fibotimes.js demonstrates its inefficiency. To demonstrate it in the server, we need to make a few changes.
Because it’s an asynchronous function, we will need to change our router code. Create a new file, named routes/fibonacci-async1.js, containing the following code:
const express = require(‘express’);
const router = express.Router();
const math = require(‘../math’);
router.get(‘/’, function(req, res, next) {
if (req.query.fibonum) {
// Calculate using async-aware function, in this server
math.fibonacciAsync(req.query.fibonum, (err, fiboval) => {
if (err) next(err);
else {
res.render(‘fibonacci’, {
title: “Calculate Fibonacci numbers”,
fibonum: req.query.fibonum,
fiboval: fiboval
});
}
});
} else { res.render(‘fibonacci’, {
title: “Calculate Fibonacci numbers”,
fiboval: undefined
});
}
});
module.exports = router;
This is the same code as earlier, just rewritten for an asynchronous Fibonacci calculation. The Fibonacci number is returned via a callback function, and even though we have the beginnings of a callback pyramid, it is still manageable.
In app.js, make the following change to the application wiring:
// const fibonacci = require(‘./routes/fibonacci’);
const fibonacci = require(‘./routes/fibonacci-async1’);
With this change, the server no longer freezes when calculating a large Fibonacci number. The calculation, of course, still takes a long time, but at least other users of the application aren’t blocked.
You can verify this by again opening two browser windows in the application. Enter 60 in one window, and in the other, start requesting smaller Fibonacci numbers. Unlike with the original fibonacci function, using fibonacciAsync allows both windows to give answers, although if you really did enter 60 in the first window, you might as well take that three-month vacation to Tibet:
It’s up to you and your specific algorithms to choose how best to optimize your code and handle any long-running computations you may have.
We’ve created a simple Express application and demonstrated that there is a flaw that affects performance. We’ve also discussed algorithmic refactoring, which just leaves us to discuss how to implement a backend service. But first, we need to learn how to create and access a REST service.
Source: Herron David (2020), Node.js Web Development: Server-side web development made easy with Node 14 using practical examples, Packt Publishing.