Comparing performance

Earlier, we saw how we can simply swap out a simple queue for a priority queue and not worry about the functional change that it might cause; similarly, we can swap out priority queues for a higher-performant variant of them: circular dequeues.

Before we start working on a comparison, we will need to discuss circular queues and why we need them. 

The difference between a circular queue and a simple queue is that the back of the queue is followed by the front of the queue. That being said, they are not functionally different. They still perform the same operations, and produce the same results; you might be wondering where exactly they differ and what's the point if the end result is the same.

In JavaScript arrays, memory locations are contiguous. So, when creating a queue and performing operations such as remove(), we will need to worry about moving the remaining elements to point to the updated front instead of null, thus increasing the number of operations; it is a memory hit too, unless your queue has an unlimited/dynamic number of slots.

Now, imagine a circular queue—because of its circular nature, this queue has a fixed number of memory locations, and when an element is removed or added, you get to reuse memory locations and reduce the number of operations that are performed, which makes it faster than a regular queue.

Before we can make a similar judgment over the performance of this queue against native arrays in JavaScript, let's take a look under the hood of Chrome's JavaScript engine V8 and check whether it really matters in our case. The reason why we are considering this is because of the frequently overlooked concept of sparse and dense arrays in JavaScript, although this is an under-the-hood implementation and could keep changing every now and then. Most of the time, JavaScript arrays are dense and can easily become sparse if not handled properly. A simple way to test this is to create an array, as follows:

• Consider example 1:

const a = [undefined, undefined, 10];

When you log it, you see the same:

[undefined, undefined, 10];

Now, create an array like this:

• Consider example 2:

const b = [];
b[3] = 10; // hole as we missed out index 0,1,2

When you log it, you get the same result:

[undefined x 3, 10];

This is interesting, as it shows the difference between the dense (example 1) and sparse (example 2) behavior of JavaScript arrays. When you create these dense arrays, the elements of the array are known to be of specific values, and these values are known at the time of initialization, which gives JavaScript the option of keeping these values in contiguous memory.

The V8 code for the JavaScript array implementation has the following comment, which makes for another interesting observation that is in line with what we have discussed so far

// The JSArray describes JavaScript Arrays
// Such an array can be in one of two modes:
//           - fast, backing storage is a FixedArray and length <= elements.length();
//           Please note: push and pop can be used to grow and shrink the array.
//         - slow, backing storage is a HashTable with numbers as keys.
class JSArray: public JSObject {

So, arrays internally are treated differently based on the type and size of data that is being saved in the array. As a rule of thumb, always create an empty array using an array literal and incrementally assign values to elements starting from the 0 index while leaving no gaps or holes in the array. This keeps the array fast, and it does not go into the dictionary mode unless the sheer size of the data demands it.

A double-ended circular queue, also known as circular dequeue, is also similar to a simple queue, except that the add() and remove() can be done from either the front or the back of the queue.

This is basically the same API as your array, and we can build an example of the class that would provide this functionality, but let's go one better and take a look at how we can implement everything we discussed previously using a circular queue and make it as performant as possible:

First, we will make an assumption that this queue has a limited size; it can be extended later to be of a dynamic nature, but that's not a concern right now. Until now, WeakMap() has been used as the in-memory data store in which we persisted the data necessary for the queue, but when it comes to performance it just adds another layer of retrieval to our data structure, so we will move over to a standard array in this case, as that is what we will be comparing against in our benchmark tests anyway. Translating this into some code, we can get our CircularDequeue, as follows:

var CircularDequeue = (()=> {
    class CircularDequeue {
        constructor() {
            // pseudo realistic 2^x value
            this._size = 1024;
            this._length = 0;
            this._front = 0;
            this._data = [];
        }

        push (item) {
            // get the length of the array
            var length = this._length;

            // calculate the end
            var i = (this._front + length) & (this._size - 1);

            // assign value to the current end of the data
            this._data[i] = item;

            // increment length for quick look up
            this._length = length + 1;

            // return new length
            return this._length;
        }

        pop () {
            // get the length of the array
            var length = this._length;

            // calculate the end
            var i = (this._front + length - 1) & (this._size - 1);

            // copy the value to return
            var ret = this._data[i];

            // remove the value from data
            this._data[i] = undefined;

            // reduce length for look up
            this._length = length - 1;

            // return value
            return ret;
       }

       shift () {
            // get the current front of queue
            var front = this._front;

            // capture return value
            var ret = this._data[front];

            // reset value in the data
            this._data[front] = undefined;

            // calculate the new front of the queue
            this._front = (front + 1) & (this._size - 1);

            // reduce the size
            this._length = this._length - 1;

            // return the value
            return ret;

        }

        unshift (item) {
            // get the size
            var size = this._size;

            // calculate the new front
            var i = (((( this._front - 1 ) & ( size - 1) ) ^ size ) -
            size );

            // add the item
            this._data[i] = item;

            // increment the length
            this._length = this._length + 1;

            // update the new front
            this._front = i;

            // return the acknowledgement of the addition of the new
            item
            return this._length;
        }
    }

    return CircularDequeue;
})();

module.exports = CircularDequeue;

Of course, this is only one way of implementing a circular dequeue; you can get better performance by adding the properties to the class's constructor itself instead of wrapping them inside an IIFE (that is, avoid scope chain lookups ) and also further simplify the code if you are using TypeScript, which allows private class members as discussed with stacks.