While recently reviewing some basic data structures and algorithms, I wondered what the best implementation for a queue in Javascript is, since there is no built–in queue. I decided to compare three different implementations by running some empirical tests.

I also wanted to get some practice with D3 and making data visualizations in React, so I used this to get some actual data to visualize. Be sure to check out the plots below!

Quick Queue Refresher

A queue is a data structure that stores and retrieves data in a first–in, first–out manner. It supports an enqueue operation to add an item to the queue, and a dequeue operation to retrieve the next item in the queue.

While not strictly part of the definition, the expectation is that these enqueue and dequeue operations take a constant amount of time, meaning they take the same amount of time regardless of what’s being added to or retrieved from the queue.

Queues can also support other operations, like checking if it is empty, peeking at the next item, and getting the total number of items in the queue.

Implementations tested

I looked at three implementations based on arrays, plain objects, and (singly) linked lists. I required the implementations to all have the same interface, meaning that an item can be added to a queue with queue.enqueue(item) and the next item can be retrieved with queue.dequeue().

One benefit of this is that the same test code can be used for all the implementations.

Array implementation

The simplest implementation is probably just using a built-in array and the push and unshift array methods. Here’s the array implementation I used:

const buildArrayQueue() => ({
  items: [],
  isEmpty() {
    return this.items.length === 0
  },
  enqueue(item) {
    this.items.push(item)
  },
  dequeue() {
    if (!this.isEmpty()) {
      return this.items.unshift()
    } else {
      throw new Error('Cannot dequeue empty queue')
    }
  }
})

The function buildArrayQueue returns a queue object that is essentially a wrapper around an array (this.items) and its push and unshift methods.

Linked list implementation

The linked list implementation below uses an object to maintain references to the next node (this.head) and the last node (this.tail). Calling queue.enqueue(item) creates a node nextNode containing item as its value and adds it to the tail of the list, checking for the edge case where the queue is empty. queue.dequeue() returns the item from the next node in the list, throwing an error if the queue is empty.

const buildLinkedListQueue => ({
  head: null,
  tail: null,
  isEmpty() {
    return this.head === null
  },
  enqueue(item) {
    const nextNode = { val: item, next: null }
    if (this.isEmpty()) {
      this.head = nextNode
      this.tail = nextNode
    } else {
      this.tail.next = nextNode
      this.tail = nextNode
    }
  },
  dequeue() {
    if (!this.isEmpty()) {
      const nextItem = this.head.val
      this.head = this.head.next
      return nextItem
    } else {
      throw new Error('Cannot dequeue empty queue')
    }
  }
})

Object implementation

The following object implementation is like a mix between the array and linked list implementations. buildObjectQueue returns an object that assigns each item an integer key. It keeps track of the the index of the next item in line with this.head, and it keeps track of the index of where to put the next item enqueued with this.tail.

const buildObjectQueue = () => ({
  head: 0,
  tail: 0,
  isEmpty() {
    return this.head === this.tail
  },
  enqueue(item) {
    this[this.tail] = item
    this.tail++
  },
  dequeue() {
    if (!this.isEmpty()) {
      const nextItem = this[this.head]
      this.head++
      if (this.head === this.tail) {
        this.head = 0
        this.tail = 0
      }
      return nextItem
    } else {
      throw new Error("Cannot dequeue empty queue")
    }
  },
})

Tests

To keep things simple, I decided to simply measure the time it took for a queue to enqueue an item and also to dequeue an item. To see how the times scale with how large the queue is, I ran the same tests when the queues had one hundred items to ten million items and each power of ten in between, i.e., six orders of magnitude.

Here’s the important part of the code used to test the queue implementations:

const randomInt = (min, max) =>
  Math.floor(Math.random() * (max - min + 1) + min)

function testQueue(queue, queueSize) {
  // initialize queue
  for (let i = 0; i < queueSize; i++) {
    queue.enqueue(randomInt(0, 100000))
  }

  // test enqueue time
  const randInt = randomInt(0, 100000)
  const enqueueStart = process.hrtime.bigint()
  queue.enqueue(randInt)
  const enqueueEnd = process.hrtime.bigint()

  // test dequeue time
  const dequeueStart = process.hrtime.bigint()
  queue.dequeue()
  const dequeueEnd = process.hrtime.bigint()

  return [enqueueEnd - enqueueStart, dequeueEnd - dequeueStart]
}

The function testQueue initializes queue with queueSize random integers between zero and one hundred thousand, and then measures the time before and after a call to queue.enqueue and queue.dequeue using Node’s process.hrtime.bigint (the tests were run with Node version 14.15.2).

process.hrtime.bigint returns a time relative to an arbitrary time in the past and is thus used to measure differences in time. It returns the time in nanoseconds, i.e., in billionths of a second, as a bigint. You can read the docs here.

The actual code running the tests is

const numIterations = 400
const queueSizes = [100, 1000, 10000, 100000, 1000000, 10000000]

for (let queueSize of queueSizes) {
  const arrayTimes = []
  const linkedListTimes = []
  const objectTimes = []

  for (let i = 0; i < numIterations; i++) {
    objectTimes.push(testQueue(buildObjectQueue(), queueSize))
    arrayTimes.push(testQueue(buildArrayQueue(), queueSize))
    linkedListTimes.push(testQueue(buildLinkedListQueue(), queueSize))
  }

  /* 
    code to write data to file
  */
}

At each queueSize, I ran testQueue for each implementation four hundred times, using a new queue object each time.

Predictions

I expected the enqueue times to be mostly independent of the size of the queue for all the implementations since the operations in all the enqueue implementations are constant-time operations.

I also expected the dequeue times to be independent of queue size, except for the array implementation. This is because it uses the array method Array.unshift.

The unshift method takes an item and adds it to the array, putting it at index 0. But this then forces all the elements already in the array to be shifted down by one. This means that the whole unshift operation takes time proportional to the number of elements in the array. For example, unshift should take about ten times longer on an array with one thousand elements than an array with one hundred elements.

Reindexing array elements should be a fast operation, so this effect should be significant only at large array sizes. In addition, we also have to add the overhead time for function calls and whatnot.

Putting this all together, I expect the array dequeue times $t$ to be related to the queue size $n$ by the equation

for some numbers $a$ and $b$. $a$ represents the unshift effect, and $b$ represents the constant overhead time costs. Hopefully you recognize this as the equation for a straight line: $y = mx + b$.

Results

Below is an interactive data visualization of the test results. You can choose what data is shown and what kind of plot to show it in by clicking the options below the plot.

Note I rescaled the units from nanoseconds to microseconds. I’ve chosen outliers to be anything either one and a half times the interquartile range above the 75th percentile or one and a half times the interquartile range below the 25th percentile, where the interquartile range is the difference between the 75th and 25th percentiles.

To better see how the enqueue and dequeue times scale with queue size, I’ve plotted the median times for each queue size below.

Because the queue sizes span six orders of magnitude, I’ve actually plotted the logarithm base ten of the enqueue and dequeue times¹ against the logarithm base ten of the queue size $n$ to make the plots look nicer.

So for example, $\log_{10} n = 7$ means $n = 10^7$, which is ten million, and $\log_{10} n = 4$ means $n = 10^4,$ which is ten thousand. More generally, $\log_{10} t = x$ means $t = 10^x$.

Median enqueue times

The median enqueue times are somewhat constant over the six orders of magnitude of queue sizes, but there is a slight increase. They range from about 0.25 microseconds to about 1.5 microseconds. More on this increase below. For each queue size they are roughly the same for all three implementations.

Median dequeue times

The median dequeue times for the linked list and object implementations show a similar slight increase as the median enqueue times. The array implementation times very gradually increase and then start to rapidly increase.

Thoughts

Looking at the data, the results agree with my predictions for the most part. Some quick observations:

1. I noticed that in many of the scatterplots there seems to be a noticeable decrease in times over the first fifty or so iterations. I suspect this might be due to under-the-hood optimizations by the compiler caused by the many repeated calls to enqueue and dequeue (we say these methods, which are functions really, become “hot”), but I wasn’t quite sure how to check this.

2. In basically all the datasets we see some large outliers. These outliers I think are likely due to OS interruptions and the garbage collector.

Median array dequeue times

I predicted earlier that the array implementation median dequeue times should follow a linear behavior $t = an + b$ for large queue size $n$. Looking at the graph, the points don’t exactly follow a straight line, but this is because I took the logarithms of $t$ and $n$, meaning I actually plotted $\log t$ versus $\log n$.

To see that this graph indeed shows the behavior I expected, let’s take the logarithm of both sides of the equation for a straight line $t = an + b$:

Remember that $a$ is some number that represents the reindexing effect when using unshift and that this effect is small, so $a$ should be a pretty small number. This means that for relatively small queue sizes $n$, the product $an$ is a lot smaller than $b$, so $\log t = \log (an + b) \approx \log(b)$ , which is constant. In other words, for small queue sizes, $\log t$ should be roughly constant.

On the other hand, once $n$ gets large enough that the product $an$ is much greater than $b$, then

where the last equality follows from the property of logarithms that $\log (xy) = \log x + \log y$. Since we’re plotting $\log t$ versus $\log n$, this approximate equation for $\log t$ has the same form as the equation for a straight line $y = mx + c$, where $y$ is $\log t$, slope $m$ is 1, $x$ is $\log n$, and $c$ is $\log a$. This means that for large queue sizes, the graph of $\log t$ should be approximately linear.

We see both these behaviors for small and large queue sizes. Fitting by eye, $a \approx 0.34$ and $b \approx 489.5$ seem to fit the data well (try entering “plot log base 10 (0.34 *10^n + 489.5) between n = 2 and n = 7” on Wolfram Alpha to see for yourself).

But I should point out that the times for the array dequeue times don’t actually exactly follow the equation $t = an+b$. This was an example of asymptotic analysis. What this equation really represents is the small and large $n$ behavior combined in a concise notation.

The enqueue and other dequeue times

Turning to the linked list and object dequeue times, as well as the enqueue times for all three implementations, to be honest I’m not quite sure why there is a slight increase as the queue size $n$ increases. It seems there might be some sort of $\log n$ dependence?

At first I thought, well, we’re using Node, which uses Chrome’s V8 Javascript engine, and I remembered reading about how V8 uses an optimization technique known as hidden classes for fast object property accesses and that adding properties to already-existing objects causes hidden class transitions.

I checked whether the classes were changing as items were enqueued and dequeued using V8’s %HaveSameMap function and no, there were no hidden class transitions.²

I was particularly surprised that the object implementation had no hidden class transitions, since it relies on explicitly adding and removing properties to the queue object. Reading the article on hidden classes linked above, it turns out that integer properties are treated differently than noninteger properties, so that adding integer properties does not cause hidden class transitions.

Then I looked into how the enqueue times changed for a given queue as the queue size grew up to one million items as well as the dequeue times as the queue is dequeued. Since checking the times after enqueueing and dequeueing each item would give me two million data points, which is far more than I need or want, I recorded the times after every one thousand items.