Running benchmark tests

Before we run the benchmark, it is important to understand our intention of comparing our queue with native arrays. We are not trying to prove that the queue is faster than arrays and that's why we should be using them. At the same time, we do not want to use something, that is ridiculously slow. The goal of these tests is to help us understand where queues lie with respect to native data structures and whether we can rely on them to provide a performant custom data structure if needed.

Now, let's run some benchmark tests to compare a circular dequeue and an array. We will use benchmark.js to set up and run our benchmark tests. The setup is pretty straightforward; we will be comparing the circular dequeue API with a regular array's native operations. 

To start with the testing, let's first include the benchmark node module in our project. To install it, run the following command on your Terminal in the project root:

npm install benchmark --save-dev

Once it is installed, we are ready to create our test suite. Create a tests folder and add a file called benchmark.js under it. To create a test suite, we will first set up the data. As discussed earlier, we will compare our CircularDequeue against an array:

var Benchmark = require("benchmark");
var suite = new Benchmark.Suite();
var CircularDequeue = require("../utils/circular-dequeue.js");

var cdQueue = new CircularDequeue();
var array = [];

for(var i=0; i < 10; i++) {
    cdQueue.push(i);
    array.push(i);
}

Here, we start off with a small dataset in both the circular dequeue and array. This will allow the arrays to be dense and thus allow V8 engine will run in fast mode and apply internal optimizations.

Now, we can go ahead and add tests to our testing suite:

suite
   .add("circular-queue push", function(){
        cdQueue.push(cdQueue.shift());
   })
   .add("regular array push", function(){
        array.push(array.shift());
   })
   .add("circular-queue pop", function(){
        cdQueue.pop();
   })
   .add("regular array pop", function(){
        array.pop();
   })
   .add("circular-queue unshift", function(){
        cdQueue.unshift(cdQueue.shift());
   })
   .add("regular array unshift", function(){
        array.unshift( array.shift());
   })
   .add("circular-queue shift", function(){
        cdQueue.shift();
   })
   .add("regular array shift", function(){
        array.shift();
   })
   .on("cycle", function(e) {
       console.log("" + e.target);
   })
   .run();

One thing to note in the previous tests is that we always couple two operations together, as follows: 

.add("regular array push", function(){
      array.push(array.shift());
});

If we do not do a shift() method before doing the push() method and push a number instead, for example, 1 or 2, then we will quickly run into an out of memory error, as the number of iterations of the tests internally is too large for the arrays to handle; circular queues, on the other hand, will be fine because of their circular nature: they would just overwrite the previous values.

Now, add the test to your package.json scripts for an easier access:

"scripts": {
    "start": "node index.js",
    "test": "node tests/benchmark.js"
},

To run the benchmark test suite, run the following command:

npm run test

The result will be as follows:

As you can note from the preceding screenshot, the push and the unshift for the circular queues are much faster than the native push and unshift operations, whereas the pop and shift operations are almost 30% slower. 

Now, let's make the arrays sparse so that we force V8 to run the array methods in dictionary mode (this can be a real use case for some and also a possibility sometimes when dealing with arrays of mixed data types):

var i = 1000;

while(i--){
    cdQueue.push(i);
    array.push(i);
}

When we run similar tests but with sparse arrays, the results are as follows:

You can see that the performance greatly varies from that of the fast mode for the push() operation, whereas the other pretty much remains the same. This is a great way to understand the consequences of adopting a particular coding practice. You will need to understand the requirements of your application and pick the right tool for the right job accordingly.

For example, when memory is a priority, we will use the simple queue instead, which works with WeakMap(), instead of regular array. We can create two new tests, which we can run separately to track their individual memory usage:

suite
   .add("regular array push", function(){
        array.push(array.shift());
   })
   .on("cycle", function(e) {
        console.log("" + e.target);
        console.log(process.memoryUsage());
   })
   .run();

It produces the following result:

We can note from the preceding screenshot that it logs the result of our test run, which is the ops/sec, and also logs the total memory usage of that cycle.

Similarly, we can run the benchmark for a remove operation on the simple queue, which is very similar to what we did with the shift operation:

suite
   .add("simple queue push", function(){
        simpleQueue.add(simpleQueue.remove());
   })
   .on("cycle", function(e) {
        console.log("" + e.target);
        console.log(process.memoryUsage());
   })
   .run();

This produces the following result:

You can see that the simple queue is obviously slower than the array by a factor of 4, but what is important here is to note that the heapUsed for both scenarios. This is another factor that lets you decide when and how to pick a particular type of data structure.